哈希表介绍
哈希表(也称散列表,hash table),是根据键值直接访问其对应的数据存储位置的一种数据结构。若使用数组或者链表来存储元素则在比较某个元素时,数组或链表需要循环进行比较,而通过哈希表只需要计算出对应的哈希位置取出对应的值进行比较或判断在否。
其有以下几种特性:
- 若关键字为k,则其值存放在f(k)[散列函数]的存储位置上。
- 对不同的关键字可能得到同一散列地址，即k1≠k2而f(k1)=f(k2),这种现象称为冲突。
- 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数,以便减少冲突。
构造哈希函数的方法
一个好的哈希函数能够提升查找效率减少哈希地址冲突带来的额外处理开销,常用的哈希函数有以下几种:
直接地址
H(key) = key 或 H(key) = a*key + b，其中a和b为常数
平方取中法
先计算出关键字值的平方，然后取平方值中间几位作为散列地址。假如有以下关键字序列{421，423，436}，平方之后的结果为{177241，178929，190096}，那么可以取中间的两位数{72，89，00}作为Hash地址。
折叠法
将关键字拆分成几部分，然后将这几部分组合在一起，以特定的方式进行转化形成Hash地址。假如知道图书的ISBN号为8903-241-23，可以将address(key)=89+03+24+12+3作为Hash地址。
除留取余法
如果知道Hash表的最大长度为m，可以取不大于m的最大质数p，然后对关键字进行取余运算，address(key)=key%p。在这里p的选取非常关键，p选择的好的话，能够最大程度地减少冲突，p一般取不大于m的最大质数。当关键字是整数时候比较好的避免冲突。
数字分析法
假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
随机数法
选择一个随机函数，把关键字的随机函数值作为它的哈希值,通常当关键字的长度不等时用这种方法。当关键字是小数的时候比较好的避免地址冲突。
解决哈希冲突
基于哈希的数据结构有着接近常量的时间即0(1)[基于数据]的时间复杂度,对于大量数据的查询效率极为高效。哈希的查找效率因数基本和哈希函数是否均匀,处理冲突的方法,哈希表的加载因子有关。
开放地址法
当发生冲突时,从当前位置向后按某种策略遍历哈希表。当发现可用的空间的时候,则插入元素。开放地址有一次探测(hs=(h(key)+i) ％ m,0 ≤ i ≤ m-1)、二次探测(hi=(h(key)+i*i) ％ m，0 ≤ i ≤ m-1)和双重哈希(hs=(h(key)+i*h1(key)) ％ m,0 ≤ i ≤ m-1)。
一次探测
探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1]，…，直到 T[m-1]，此后又循环到 T[0]，T[1]，…，直到探查到 有空余地址 或者到 T[d-1]为止。
二次探测
探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1^2]，T[d+2^2]，T[d+3^2],…，等，直到探查到 有空余地址 或者到 T[d-1]为止。缺点是无法探查到整个散列空间。
双重哈希
探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+h1(d)], T[d + 2*h1(d)]，…，等。该方法使用了两个散列函数 h(key) 和 h1(key)，故也称为双散列函数探查法。定义 h1(key) 的方法较多，但无论采用什么方法定义，都必须使 h1(key) 的值和 m 互素，才能使发生冲突的同义词地址均匀地分布在整个表中，否则可能造成同义词地址的循环计算。该方法是开放定址法中最好的方法之一。
开放定址在解决当前冲突的情况下同时可能会导致新的冲突，而开链不会有这种问题。
链地址法(又开链法)
开链的思想是哈希表中的每个元素都是一个类似链表或者其他数据结构的 head。当出现冲突时，我们就在链表后面添加元素。这也就意味着，如果某一个位置冲突过多的话，插入的时间复杂段将退化为 O(N)。
开链相比于开放定址局部性较差，在程序运行过程中可能引起操作系统的缺页中断，从而导致系统颠簸。
再哈希法
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。很多语言或者工具包再哈希的内部实现是使用了两个数组，其中一个作为备用。如果当前哈希表的负载因子（元素个数/哈希表容量大小）过大或者过小时，就将数据切换到备用数组里。
建立一个公共溢出区
假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]为溢出表用以存储发生冲突的记录。，凡是和基本表发生冲突的元素，一律填入溢出表。
一次性哈希算法
在分布式的系统中我们希望能把数据进行分布式存储,这样能极大的提升整体性能,但是需要保证相同的缓存key请求总是能被负载到同一台机器。我们可以使用简单的hash算法,对于每次访问，可以按如下算法计算其哈希值：
h = Hash(key) % n
字符串到正整数的哈希映射函数。这样，如果我们将服务器数量n分别编号为0、1、2，那么就可以根据上式和key计算出服务器编号h，然后去访问。
这样做虽然能解决问题,但是存在扩展性不好的缺点,如果增加或删除一台机器势必需要哈希值得重新计算导致大量的key会被重定位到不同的服务器从而造成大量的缓存不命中。
简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0 - 232-1（即哈希值是一个32位无符号整形）,整个空间按顺时针方向组织。0和232-1在零点中方向重合。将数据key使用相同的函数H计算出哈希值h，通根据h确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。
虚拟节点
一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。使得大量数据会访问到同一台机器上,为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。数据定位算法不变，只是多了一步虚拟节点到实际节点的映射。