（点击上方公众号，可快速关注）

来源：taozj

taozj.org/201611/data-structure-and-algorithm-(1)-hash.html

如有好文章投稿，请点击 → 这里了解详情

散列技术常常用于键－值关系的数据结构中，比如数据库索引、map、缓存等地方，其是通过在记录(值)的存储位置和其关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。散列技术的实现方式决定了其最适合的求解问题是查找与给值相等的记录(是否存在及其位置)，而对于其他查找不适合：比如某个关键字对应很多记录的情况、范围查找、查找最值等。

1.1 散列函数

散列函数可以说是散列数据结构的核心，最直接的感受就是好的散列函数能够让记录能够在hash表中分布均匀(uniform distribution)，当然用于相似性查找的特殊hash类别不考虑在内。此外，在我们平常习惯性的思维中，认为只要满足X != Y，则f(X)!=f(Y)就是好的满足条件的hash函数，比如常用的CRC函数，其实如果将这类函数用在hash中，大多数情况下要比精心设计的hash函数冲突的可能性更大，会影响到hash的效率和性能。

1.1.1 散列函数通常具备条件

(1). 散列均匀分布：

由于空间的限制散列表不可能无限的大，而散列冲突的几率会因为空间的限制而增大，这个时候就需要一个perfect的散列函数来作为弥补，通常设计一个好的均匀分布的散列函数是比较困难的，这也是很多散列函数专家努力的方向。

在绝大多数场合下，散列表的容量都设计成2的指数长度大小，而算出来的散列值通常采用掩码的方式快速得到散列表的索引值，所以此时的散列函数可以设计优化成在二进制的各个bit位为随机分布就可以了。不过murmur的作者也说了，好的hash函数不应当假定其用户采用’hash % tablesize’的方式来hash-to-table-index，只是作为一种常用的习惯性方法而已。

(2). 计算简单高效：

hash值不应当过于的复杂，hash计算的吞吐量也是hash函数的一个重要衡量标准，除了在设计中不要用过于复杂的计算操作外，实用新式CPU的高效运算指令也是提升性能的一个方面。

1.1.2 简单常用构造散列函数的方法

(1). 直接定值法：就是利用元素的关键码设计成某个线性函数的形式，比如

f = a × key + b;

其计算简单而且不会冲突，但是需要事先知道关键码的在小范围连续分布比较适用；

(2). 数字分析法：抽取部分数字进行诸如：反转、左环位移、右环位移、前两数与后两数相加等各种操作，其也主要用于事先知道关键字分布且关键字位数较多且若干位分布比较均匀的情况；

(3). 平方取中法：关键字位数不多的情况，先对关键字平方计算，然后取其中的某些固定位组合；这其实在实际中常用的方法，采用先放大再抽取的方式，是一种伪随机数的生成方法；

(4). 折叠法：将数字串平均分几个部分后重叠(移位法)对齐或者折叠(分界法)对齐后求和，通常用在关键字位数较多的情况下；

(5). 除留余数法：也是最常用的，mod取模缩减散列空间，这个操作可以直接针对关键字，或者是其他操作后的中间结果；若散列表表长为m，通常p为小于或等于表长的最小质数或包含不小于20的质因子的合数，因为这样产生hash冲突的可能性要少的多；

(6). 乘余取整法：

f(key) = { Z × (a × key % 1) }

a通常取黄金分割数0.6180339，%1表示取结果的小数部分，Z为散列表的容量；

(7). 随机数法：f(key) = random(key)，适合于关键字长度不等的情况。

1.2 散列表的冲突处理

散列表的冲突处理主要分为闭散列法和开散列法，闭散列法也称为开放定址法。

1.2.1 闭散列法（开放定址法）

当插入元素的时候，一旦发生了散列冲突，就去寻找下一个空的散列地址供插入，而查找的时候逐个查找，直到碰到开放的地址查找失败。闭散列法是通过将冲突的元素以一定的模式存储在原散列的空间中。

之所以叫做闭散列法，就是因为冲突的元素没有开辟额外的存储空间，还是在原先hash表的空间范围之内。

(1). 线性探测法：将散列表看作是一个循环向量，若初始地址是f(key)=d，则依照顺序d、d+1、d+2…的顺序取查找，即f(key)=(f(key)+1)mod N;

(2). 二次探测法：基本思路和线性探测法一致，只是搜索的步长和方向更加的多样，会交替以两个方向，步长为搜索次数的平方来查找；

(3). 双重散列法：通常双重散列法是开放地址中最好的方法，其通过提供hash()和rehash()两个函数，前者产生冲突的时候，定制化后者rehash()重新寻址，其机制比前面两种固定格式的要灵活的多；

开放定址法一般用于冲突极少的情况，同时因为没有用到指针，所以对于数据的传输是友好的。

1.2.1 开散列法

与前面闭散列法对应的开散列法，一般也叫作拉链法或者链地址法，通过将冲突的元素组织在链表中，采用链表遍历的方式查找。链地址法和上面的开放定址法最大的优势是解决方法直观，实现起来简单，尤其在删除元素的时候此处只是简单的链表操作，但是前面需要考虑后面可能有元素，处理会比较复杂。同事开散列法可以存储超过散列表容量个数的元素。

(1). 链地址法：相同散列值的记录放到同一个链表中，他们在同一个Bucket中；

(2). 公共溢出法：将所有的冲突都放到一个公共的溢出表中去，适用于冲突情况很小的时候。

除了使用传统的链表，还可以使用dynamic array的方式存储，分配的时候也可以预分配多个，以保证对CPU的缓存优化友好。

1.3 散列表的装填因子

装填因子=填入表中的记录个数/散列表的长度，实践中无论设计多好的散列函数，当装填因子超过0.7后散列表的性能就会因为散列冲突开始下降，当填入表的记录越多，装填因子就越大，产生冲突的可能性也就越大。此时可以考虑增加hash表的容量，以维持查找的性能，而且更重要的是常常在实践中，是事先不知道需要管理元素的个数的，所以动态增加散列表的容量是必须的。

修改散列表容量会导致之前元素寻址失效，这个过程也成为resize(rehash)的过程，Java的HashMap在loadfactor>3/4，以及Python的dict在loadfactor>2/3的时候就会自动触发resize。实践中常常使用的方法有：

1.3.1 整体拷贝所有元素

最直观明了简单粗暴的方式，通常会double散列表的容量，然后将所有元素全部散列拷贝到新的表中，然后释放旧的表，没有什么特别的技术含量。
还有，有的散列库提供shrink的功能，这样就可以当loadfactor小到某个程度的时候缩减散列表的容量，释放节约内存。不过如果散列表元素动态变化较大的情况，这种反复的申请和释放对性能、缓存等有极大的破坏作用，所以很多时候shrink只是个请求，并不保证会真正实施。

1.3.2 增量修改

对于元素数量多，实时性要求高的应用，通常是增量递进式的resize的，这种方式resize的步骤一般是：

(1). resize的时候分配新的hash表，同时保留旧的hash表；
(2). 当每次查找和删除的时候，同时对这两张表做操作；每次插入的时候，只对新hash表操作；
(3). 每次插入的时候，同时移动 r 个元素从旧hash表到新hash表；
(4). 当所有元素从旧hash表被移走后，resize结束，释放旧的hash表；

如果想看具体的实现，建议去读读memcached的代码，里面有这种增量resize的操作。

1.3.3 其他方法

还有就是设计的hash-to-table-index的操作和是和散列表的容量是无关的等情况，在分布式缓存中一致性hash等会涉及到，有时间再展开吧。

1.4 散列表和二叉树的对比

散列表和二叉树两者原理完全不同，使用情况也各有千秋，为此C++标准对于基本的数据类型(multi_)set、(multi_)map也建立了有序和无序两个版本。还有就是在比如MySQL/Mariadb数据库建立索引的时候，就有BTree索引和Hash索引的类型：前者算是有序索引，索引记录都是按照顺序排列(数据库由于通常记录会比较多，BTree是为这种类型优化的数据结构，减少对磁盘IO的访问次数，其不是通过二叉树实现的)。

两者的选型和区别主要考虑到以下情况：

(1). 二叉树是有序容器类，散列表是无须容器类，前者可以用于比较、范围查找类的检索，后者属于只能用于检索是否存在的情况；

(2). 虽然自平衡二叉树访问效率平均为O(logn)，但是随着元素数目n的增加性能也会下降，所以对于数据量大的情况还是倾向于效率更高的O(1)代表的散列表；

(3). 在多线程的环境下，二叉树的操作往往要锁住整个数据结构，而散列表可以对每个bucket建立一个互斥锁，所以在并发率高的情况下，散列表的性能更加；

(4). 超大数据集下，分布式缓存hash有成熟的案例，二叉树？嘿嘿，从来没听过。

C++和Boost有unordered的散列库，而针对C就需要自己寻找散列实现。在memcached中有Jenkins和Murmur两种散列函数可选，Nginx使用的是Murmur散列函数，而最近几年原Jenkins的作者推出了SpookyHash，而Google也发布了Murmur的改进型CityHash。如果有空余时间的人可以把这些新型的hash func封装好给memcached和Nginx提PR，哈哈。

2.1 Jenkins

在整个Hash中占据重要的地位，其作者Bob Jenkins几十年钻研Hash，发表了无数相关论文，不容小觑吧。

2.2 Murmur

当前使用的比较广泛，而且速度也比较快，尤其它提供32bit和64bit的输出版本，能够提供原生的高性能。

2.3 CityHash和SpookyHash

SpookyHash是Jenkins的作者Bob Jenkins发布的最新散列函数，而CityHash乃是大厂Google所出，且由Murmur作者Austin Appleby进行Review的。

SpookyHash只提供128bit的结果，而CityHash提供64bit、128bit、256bit的输出。

所以新版的Hash输出的位数增多了，如果你需要32bit的散列值，那么Murmur由于是原生支持，性能会是最好的；而据Austin Appleby透露(其就职于Google)现在Google的所有产品都是基于64bit架构的，其将来也必定是大势所趋啊。

再次重申，如果想了解Hash的实现、使用和维护，就去读memcached的源码。我暂且还不知道C是否有现成的hash库可供使用，不过C++的用户就幸福许多了，标准库的unordered_模板容器开箱既用，而且对resize、loadfactor也提供了访问和调整的接口，十分方便。

不过，标准库下面C++只提供了对内置数据类型、std::string、智能指针类型定义了hash操作，而如果自己使用的key_type不是这些类型，就需要手动定义这些操作。

3.1 在容器中指明容器模板的Hash和KeyEqual模板参数

如果自定义类型需要放在unordered_(multi)set/map容器中时候，这些无须容器都是用hash的方法存放的，可以在定义声明容器对象的时候指定模板参数中的Hash和KeyEqual参数模板就可以了，前者用以从将要保存到容器Key的类型中提取计算出一个size_t的散列值，当然通常的方法是用自定义类型中某些标准std::hash支持的成员类型求得一个散列值，也可以尝试前面介绍得到的那么多散列函数计算出自己规则的size_t尺寸的散列值；而对于KeyEqual操作，如果该类型支持operator==运算符就可以不提供这个参数，我想可能是在hash冲突的时候被调用到。

size_t hasher(const Sales_data& sd) {   
    return std::hash<string>()(sd.isbn());    
}   
bool eqOp(const Sales_data &lhs, const Sales_data &rhs) {   
  return lhs.isbn() == rhs.isbn();    
}   

using SD_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>;   
SD_multiset bookstore(42, hasher, eqOp);

3.2 模板特例化得方法

这个是治本的方法，让后面的std::hash真正认得我们的自定义类型。根据C++的规则，模板特例化必须在模板的原名字空间中，所以这里需要打开std名字空间，进行类型的模板特例化声明，然后进行定义实现操作：

namespace std {   
template <>   
struct hash<Sales_data> {    
  typedef size_t result_type;   
  typedef Sales_data argument_type;   
  size_t operator()(const Sales_data& s) const;   
}   

size_t hash<Sales_data>::operator() (const Sales_data& s) const{   
  return hash<string>()(s.book) ^ hash<double>()(s.revenue);    
}   
} //关闭std名字空间

在C++类实现中，成员变量通常都是private的，所以上面的特例化成员通常要声明为类型的友元friend才能正常工作

emplate <typename T> class std::hash; //前置声明   
class Sales_data {   
friend class std::hash<Sales_data>;   
 ... };

本文完！

参考

• CityHash: new hash function by Google (faster than Murmur)

• Hash table

• State of the hash functions, 2012

• CPP reference

觉得本文有帮助？请分享给更多人

关注「算法爱好者」，修炼编程内功