散列/哈希

本文首先发表在： http://coderbee.net/index.php/algorithm/20130919/479 

 

散列一般也叫哈希。散列表也叫哈希表。本位将介绍散列表的基本知识、一致性哈希、哈希碰撞攻击及Java里的哈希实现。

 

介绍

散列表是普通数组概念的推广，在最坏情况下查找一个元素需要O(n)，在一些合理假设下，查找一个元素的期望时间为O(1)。

 

在散列表中，不是直接把关键字用作数组下标，而是根据关键字计算出下标。

 

散列函数：作用就是根据关键字计算出数组下标。

 

碰撞（collision）：多个关键字映射到同一个数组下标位置。

 

槽：一般把散列表的数组的一个存储单元（元素）叫做槽。

 

简单一致性散列：（Simple uniform hashing）假设任何元素散列到m个槽中的每一个的可能性是相同的，且与其他元素已被散列到什么位置上独立无关，这个假设称为简单一致性散列。

 

直接寻址表

当关键字的集合较小时，直接把对象放在表的槽中，节省空间；通常不需要存储对象的关键字域，因为如果有了一个对象在表中的下标，就可以得到它的关键字。由于没有存储关键字，就必须有某种方法来确定某个槽是否为空。

 

在直接寻址的方式下，具有关键字k的元素被存放在槽k中。

 

散列表

在散列表中，具有关键字k的元素存放h(k)中，也就是通过散列函数h来确定存储的槽位。

 

使用散列函数的问题是两个关键字可能映射到同一个槽上，也就是发生碰撞。通过精心设计的随机散列函数可以尽量减少碰撞。

 

通过链接法解决碰撞

在链接法（chaning）中，把散列到同一槽中的所有元素都放在一个链表中。

从图可知，插入和搜索的时间与链表的长度成正比。

 

查找时，首先要计算出关键字对应的槽，然后遍历链表匹配元素。

 

散列函数

一个好的散列函数应（近似地）满足简单一致性散列的假设。一种好的做法是以独立于数据中可能存在的任何模式的方式导出散列值。

 

除法散列法

通过取关键字k除以m的余数，来将关键字k映射到m个槽的某一个去。散列函数为：h(k) = k mod m。m一般取与2的整数幂不太接近的质数。

 

乘法散列法

用关键字k乘上常数A（0<A<1），并抽取出kA的小数部分，用m乘以这个值，再取结果的底(floor)。散列函数为： h(k) = floor(m * (k*A mod 1))。

 

全域散列

universal hashing：随机地选择散列函数，使之独立于要存储的关键字。

 

全域散列的基本思想是在执行开始时，就从一族仔细设计的函数中，随机地选择一个作为散列函数。

 

开放寻址法

在开放寻址法（open addressing）中，所有的元素都存放在散列表里。即每个表项或包含动态集合的一个元素，或包含NIL。当查找一个元素时，要检查所有的表项，直到找到所需的元素或者最终发现元素不在表中。

不像在链接法中，这里没有链表，也没有元素存放在散列表外。

 

在开放寻址法中，当要插入一个元素时，可以连续地检查（或称探查）散列表的各项，直到找到一个空槽来防止待插入的关键字为止。如果需要，会检查所有的槽。

 

探查方法一般有三种：线性探查、二次探查、双重探查。

 

一致性哈希

假如有N台cache 服务器（简称 cache），那么如何将一个对象object映射到N个cache上呢？很可能会采用类似下面的通用方法计算object的hash值，然后均匀的映射到到N个cache ；hash(object)%N。

 

这样的话，如果有一台cache当机，映射关系变为：hash(object)%(N-1)；新增一台cache时，映射关系变为：hash(object)%(N+1)。这两种情况都会导致对象被映射到不同的缓存，从而导致缓存失效。一致性哈希就是解决这类场景的。

 

单调性

单调性（ Monotonicity ）：是指如果已经有一些内容通过哈希映射到相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

 

consistent hashing 是一种 hash 算法，简单的说，在移除 / 添加一个 cache 时，它能够尽可能小的改变已存在 key 映射关系，尽可能的满足单调性的要求。

 

假设有一个哈希空间，一致性哈希需要把对象和cache映射到这个缓存空间去。

圆圈表示哈希空间，是固定的，独立于cache 和 对象；蓝色的结点表示cache；红色的结点表示对象。

 

一致性哈希算法的巧妙之处在于：对于一个对象object，通过给定的哈希算法得到它的的哈希值hashCode，这个hashCode对应在哈希 空间的一个点，但这个hashCode不直接对应一个cache；为了找到这个hashCode对应的cache，需要按一种固定的顺序（比如顺时针）在 哈希空间上查找它cache，查找到的第一个cache即为这个对象所对应的cache。相当于二次散列。

 

要注意的是：通过hashCode在哈希空间查找cache时，找到的第一个cache就是对象所对应的cache，不会查找后续的cache，这就确保了一致性哈希算法具有访问局部性的特性。

 

假如哈希空间上的查找顺序为顺时针的：

• 当新增一个cache D时，它映射到key2和key3之间，那么受影响的对象只局限在：cache D和它的上一个cache结点（即cache B） 之间的对象，这些对象会被映射到新cache上去；cache B之前和cache D之后的对象都不会受影响。

• 当移除一个ceche B时，B和A之间的对象会被映射到B的下一个结点C上去。B和C之间的及A之前的对象也不会受影响。

更多详细介绍可参考：一致性hash算法 – consistent hashing

 

哈希碰撞攻击

哈希碰撞攻击是指：对于使用链接法解决碰撞的散列表实现，通过精心构建一组对象，使这些对象映射到同一个槽位，从而使散列表退化为一个链表，由于链表的操作效率平均比散列表低，从而导致散列表的性能下降，进而让整个应用程序的性能以级数下降。

 

关于通过哈希碰撞攻击的可以参考这篇文章：Hash Collision DoS 问题

 

Java里的散列

java.util.HashMap类是JDK里的散列表实现，它的实现方式是槽+链表，也就是用链接法解决碰撞。

它的散列算法是除法散列的思想，与大多数教科书里讲的不同是，它的槽的长度是2的整数次幂，而不是一个质数；且用按位与运算代替除法：

//  计算给定哈希值h所对应的槽下标
static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

h是对象的哈希值，length是槽的长度。这样做主要是出于性能的考虑。

 

对于哈希碰撞攻击，java.util.HashMap类从JDK1.8开始会在链表的长度达到某个阀值时，将散列表的实现转换为一个定制的红黑树。

 

如果对了解更多，当然应该通过google去查找更多资料。