哈希表小结
对hash table 早有耳闻，今天稍微整理总结一下。
何谓 hash table
hash table的中文名称为哈希表，又叫散列表。哈希实现了一种映射，将键值key通过某种计算映射为Hash(key)值。可以这样说，散列表是用hash映射定义的一种数据结构。
将大范围的数据，映射到一个较小的范围，是不是很爽，可以节省空间。这种角度的hash，更侧重于查找。
另外，如果一个映射，可以从输入可以很容易地计算得到输出，但是根据输出结果却很难推导出其输入，这是不是很安全的一种映射（单向函数）。这种角度的hash，更侧重于安全。
本文更关注于查找用途的hash。
注意事项
冲突
我们期望key->hash(key)是唯一的映射，当不同的key，得到同一个hash(key)值时，称为冲突。这是我们不希望的，需要解决。
均匀性
映射后数据在某个空间上的分布最好是均匀的，不均匀的分布，在某些情况下是起坏作用的。比如，我们想将数据均匀分布到不同的桶内。
hash 函数
直接定址法
这种方法，不会出现冲突的情况。
数字分析法
如果知道所有可能的关键字，可以取关键字的部分值来作为哈希值。比如月日时秒值作为哈希值。
平方取中法
将关键字平方后的中间几位作为哈希值。
适合不知道关键字的所有情况，取的位数由哈希表长确定。为什么取中间几位，是因为乘法算数时，结果的中间值是跟乘数的各位都有关系的。
折叠法
将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希值。
这个跟平方取中法有点异曲同工。
随机数法
给每个key，随机生成某范围内的数作为哈希值。
除留余数法
取关键字被某个不大于散列表表长m的数p除后所得的余数为散列值。
其他hash方法的分类：http://zhaohaolin.iteye.com/blog/1874420
一些hash函数的总结（建议看看）：http://www.burtleburtle.net/bob/hash/doobs.html
冲突的解决方法
冲突必须要解决，第一个彻底点直接换hash函数，这种方法比较粗暴，并且不是特别实际；第二个，对冲突的hash值进行处理。
开放定址法
其中
增量序列的取法：线性探测；平方探测；伪随机探测。
线性探测：
？问题？冲突，是累积所有的冲突么？还是对某一个hash值，冲突的次数？是累积所有冲突次数。
平方探测：
伪随机探测：
缺点：散列的开放定址法，可以解决冲突，但是解决的过程中会造成一片区域有值，其他任何映射到该区域的关键字，都要多次查找才可以得到hash值，这是一种正反馈，会造成严重的后果，浪费大量时间，性能下降，必须避免。NOTICE：散列表的长度最好为质数。
？疑惑？查找某个key时，是如何查找的呢？计算hash(key)固然可以提供一个位置，但是冲突的时候，是将那些key存储到其他位置的，对于出现冲突的词，要去哪个位置找呢？还是记录下来所有key的hash值，只需要根据这个对应关系，就可以找到位置值了。但是这样，又会有一个问题，查找这个key-pos的对应关系，还需要花时间，这个时间是不是很长呢？同时另一个问题也会产生，既然我要存储这个key-pos对应关系，我还扯啥hash函数啊，直接key来了，就给他分配个位置得了，然后记录下来，还搞毛线hash啊。
难道是将冲突过的词表示到另一个地方（以key-pos存储），未知的key先check一下这个冲突表（进行一次小规模比较），对于不冲突的key，则是计算其hash值，直接查找对应位置（这种方法是可行的，
还是说，先计算hash值，查找对应位置，如果对应位置没有值，则说明没有这个key嘛；如果有值，且刚好符合条件，则是key嘛；有值但不符合条件，则按照冲突的方式来找可能的位置，可能的位置遍历一下，则获得了有无的结果（这种方法也是可行的也是常用的，hash表合理的话，则会节省很多时间，
单独链表法
将散列到同一个存储位置的所有元素存储到一个链表中，数组或者栈中。
很明显，这个链表的查找是要耗费时间的，如果冲突太多，维持这个链表的价值也就不大了。
?问题? hash最大的价值在于一个key对应一个hash值吧，若是冲突的key用单独链表法共享一个hash值，又有什么用呢？其实，并不是公用一个地址，而是将同一个hash值冲突的key放到了一个链表里存储，这样大家的位置也有了。查找时，只要是得到这个冲突的hash值，都需要在这个链表里查找。
（在我的感觉里，hash直接提供了一个位置，我们的所有信息，都以数组Arr的方式存储，有key即可计算hash(key)，然后Arr[hash(key)]就得到了key_info。）上述的单链表法，以存储key为主，不是单纯地只计算地址。
双散列
再散列
对产生冲突key，将其hash值，重复hash，直到不再冲突。特点：不易产生聚集现象。
建立一个公共溢出区
这是比较省心的方法，将所有冲突的key都单独放到另一块区域存储。
?疑惑?有人发博文讲暴雪的hash算法（用来文件打包管理），说用三个hash值确定位置，但是没看懂，明明是一个hash值做位置，另外两个做验证。后来仔细想了下，暴雪的hash应用场景，是在已知一个庞大的字符串数组，问一个未知字符串是否存在其中。这样就可以解释了，先将庞大的字符串数组以hash方式存储起来（文本位置用hash值，文本内容用两个hash值表示），这样再去查找未知的字符串，一个hash值确定存储位置，另两个hash值作为key字符串的表示，不用进行字符串的比较，从而节省了时间。暴雪hash方法牛逼的地方有两个，一个是hash函数好，另一个是字符串内容用两个hash值来表示和校验，节省存储空间和比较时间。
我们看到，冲突是hash面临的最大问题，如果冲突过于严重，那么hash查找的价值也就不大了，怎么衡量什么冲突情况下的hash是科学可接受的呢？定义变量载荷因子：散列表装满程度的表示，
构建hash表的基本流程
最好提前预估一下载荷因子，限制在０.７以下。
1. 初始化hash表。表长度，表内容。
2. 存储hash表。
2.1 依次输入key，计算hash(key)。
2.2 无冲突的，直接存储key的信息。
2.3 有冲突的，解决冲突（并检查是否存储过该key），存储key的信息。
2.4 解决冲突失败的，返回错误。
未知key在已经构建的hashtable的查找，是与2.2和2.3处理方法相近，变存储为查找即可。
应用及问题
存储及快速查询
前面已经讲了很多了，此处略。
分配及负载均衡
主要应用于服务器分配，关键在于如何均匀分配，并避免数据迁移过多当增删节点时。
上代码，普通hash，一致性hash，改进的一致性hash。
#!/usr/bin/python
#-*- coding:utf-8 -*-
import hashlib
import struct
import bisect
##refrence##
##--struct--## https://docs.python.org/2/library/struct.html
##--hashlib--## https://docs.python.org/3/library/hashlib.html
##--bisect--## https://docs.python.org/2/library/bisect.html
ITEMS=1000000
NODES=100
def _hash(key):
# return the hash value before % COMPUTION #
# NOTICE: hexdigest() will bodong big #
# NOTICE: digest() will bodong small #
h = hashlib.md5(str(key)).digest()
r = struct.unpack_from(">I", h)[0]
return r
# normal-hash as following #
def normal_hash(NODES):
node_stat = [0 for i in range(NODES)]
#print len(node_stat)
#print node_stat[0:10]
for item in range(ITEMS):
h = _hash(item)
n = h % NODES
node_stat[n] += 1
_ave = ITEMS / NODES
_max = max(node_stat)
_min = min(node_stat)
print "ave is ITMES/NODES : " + str(_ave)
print "max node : " + str(_max) + "\t"+ "bodong is : " + str(float(_max - _ave)/float(_ave)*100)
print "min node : " + str(_min) + "\t"+ "bodong is : " + str(float(_ave - _min)/float(_ave)*100)
## test code ##
#normal_hash(NODES)
# if NODES increase or descrease #
# the hash value will change very different #
def compare(NODES1, NODES2):
diff = 0
for item in range(ITEMS):
h1 = _hash(item)
h2 = _hash(item)
n1 = h1 % NODES1
n2 = h2 % NODES2
if n1 != n2: diff += 1
print "NODE1 is : " + str(NODES1)+"\t"+"NODES2 is : " + str(NODES2)
print "all data is : "+str(ITEMS)+"\t" + "different is :" + str(diff)
print "different ratio is : " + str(float(diff)/float(ITEMS))
print "########### compute the difference of normal-hash using different nodes ###############"
## test code ##
#compare(NODES, NODES+1)
#compare(NODES, NODES-1)
#compare(NODES, NODES*2)
## 从结果可以看出来，normal-hash 对节点变化是很明显的 ##
## how to modify the big difference ##
## consist hash is a way to solve above problem ##
def consist_hash(NODES):
# the idea is simple #
# first, project the hash(node) into a circle ring #
# second, project the hash(key) into hash kongjian #
# third, find the left(right) hash(node) point and set it as suitable node ##
ring = []
for item in range(NODES):
h = _hash(item)
ring.append(h)
ring.sort()
## 个人感觉sort之后波动会更大 ##
## 只是将节点映射到hash值上，只要key们找挨着的映射节点即可 ##
#print "ring is :"
#print ring
node_stat = [0 for i in range(NODES)]
for item in range(ITEMS):
h = _hash(item)
n = bisect.bisect_left(ring, h) % NODES
#if item > 101 and item < 106:
# print "h is : " + str(h)
# print "bisect.bisect_left(ring, h) : " + str(bisect.bisect_left(ring, h))
# print "result of %NODES is : " + str(n)
node_stat[n] += 1
_ave = ITEMS / NODES
_max = max(node_stat)
_min = min(node_stat)
print "ave is ITMES/NODES : " + str(_ave)
print "max node : " + str(_max) + "\t"+ "bodong is : " + str(float(_max - _ave)/float(_ave)*100)
print "min node : " + str(_min) + "\t"+ "bodong is : " + str(float(_ave - _min)/float(_ave)*100)
## test code ##
#consist_hash(NODES)
def diff_nodes_for_consist_hash(NODES1, NODES2):
# compute the difference of consist-hash using different nodes #
ring = []
new_ring = []
for n in range(NODES1):
ring.append(_hash(n))
ring.sort()
for n in range(NODES2):
new_ring.append(_hash(n))
new_ring.sort()
change = 0
for item in range(ITEMS):
h = _hash(item)
n = bisect.bisect_left(ring, h) % NODES1
new_n = bisect.bisect_left(new_ring, h) % NODES2
if new_n != n:
change += 1
print "NODES1 is : " + str(NODES1) +"\t" + "NODES2 is : " + str(NODES2)
print("Change: %d\t(%0.2f%%)" % (change, change * 100.0 / ITEMS))
print "############ compute the difference of consist-hash using different nodes: ##########"
## test code ##
#diff_nodes_for_consist_hash(NODES, NODES-1)
#diff_nodes_for_consist_hash(NODES, NODES+1)
#diff_nodes_for_consist_hash(NODES, NODES*2)
## 从结果得出，一致性hash对节点少量增加的情况是比较适合的 ## 节点减少和增加很多，数据
映射到节点的变化很大 ##
## 另外，一致性哈希的分布不均匀也是个很大的问题，这也影响了后面的节点变化敏感性 ##
## 怎么搞呢？虚节点方法 ##
def virtual_consist_hash(NODES, VIRTUAL_NODES):
## use vitual-nodes * real-nodes as %-num, the hash-value will be more uniform ##
## the vitual-nodes and real-nodes need a function ##
ring = [] # to save the complete hash kongjian #
virtual2real = {} # to save the vitual-real projection #
# how from virtual to real #
# 虚拟节点越多越好，意味着越均匀，所以尽量每个真实节点都有一堆虚拟节点 #
for r_node in range(NODES):
for v in range(VIRTUAL_NODES):
h = _hash(str(r_node)+str(v)) ##构造一个由虚拟和真实节点组成>的字符串来映射到hash空间##
ring.append(h)
#v_node = h % (VIRTUAL_NODES*NODES) 如果这里直接用 虚拟节点 >与 真实节点映射，会冲突出错 #
virtual2real[h] = r_node ##这样的话，就给每个真实节点对应了VIRTUAL_NODES个虚拟节点##
## NOTICE: 一共有NODES*VIRTUAL_NODES个虚拟节点 #
## NOTICE: 这里的每个真实节点映射多少个虚拟节点，可以根据实际情况用权重来调节
## 比如，负载能力强的可以多分配虚拟节点 ##
ring.sort()
node_stat = [0 for i in range(NODES)]
for item in range(ITEMS):
h = _hash(item)
## 计算 向左最靠近的 虚拟节点的hash位置值，并且“取模”来获得长度范围内
的 虚拟节点值##
n = bisect.bisect_left(ring, h) % (NODES*VIRTUAL_NODES)
#bisect.bisect_left(ring, h) # 计算向左最靠近的虚拟节点的hash值 的位>置 #
#ring[n] 才是 最靠近的虚拟节点的 hash值 #
node_stat[virtual2real[ring[n]]] += 1
_ave = ITEMS / NODES
_max = max(node_stat)
_min = min(node_stat)
print "ave is ITMES/NODES : " + str(_ave)
print "max node : " + str(_max) + "\t"+ "bodong is : " + str(float(_max - _ave)/float(_ave)*100)
print "min node : " + str(_min) + "\t"+ "bodong is : " + str(float(_ave - _min)/float(_ave)*100)
## test code ##
#virtual_consist_hash(100, 10)
#virtual_consist_hash(100, 100)
#virtual_consist_hash(100, 1000)
## 从结果中可以粗略看出，当每个真实节点对应的虚拟节点越多时，数据分布时越均匀 ##
## 但是，虚拟节点意味着更多的内存和计算 ##
def diff_nodes_for_vir_con_hash(NODES1, NODES2, VIRTUAL_NODES):
# 比较在不同的真实节点下，节点上数据是否有很大变化 #
ring = []
hash2node = {}
ring2 = []
hash2node2 = {}
for n in range(NODES1):
for v in range(VIRTUAL_NODES):
h = _hash(str(n) + str(v))
ring.append(h)
hash2node[h] = n
ring.sort()
for n in range(NODES2):
for v in range(VIRTUAL_NODES):
h = _hash(str(n) + str(v))
ring2.append(h)
hash2node2[h] = n
ring2.sort()
change = 0
for item in range(ITEMS):
h = _hash(str(item))
n = bisect.bisect_left(ring, h) % (NODES1*VIRTUAL_NODES)
n2 = bisect.bisect_left(ring2, h) % (NODES2*VIRTUAL_NODES)
if hash2node[ring[n]] != hash2node2[ring2[n2]]:
change += 1
print "node1 is : " + str(NODES1)+"\t"+"node2 is : " + str(NODES2)+"\t"+"virtual nodes above :"+str(VIRTUAL_NODES*NODES1)
print("Change: %d\t(%0.2f%%)" % (change, change * 100.0 / ITEMS))
## test code ##
#diff_nodes_for_vir_con_hash(NODES, NODES+1, NODES)
#diff_nodes_for_vir_con_hash(NODES, NODES-1, NODES)
#diff_nodes_for_vir_con_hash(NODES, NODES+1, NODES*100)
#diff_nodes_for_vir_con_hash(NODES, NODES-1, NODES*100)
#diff_nodes_for_vir_con_hash(NODES, NODES*2, NODES*100)
#diff_nodes_for_vir_con_hash(NODES, NODES*10, NODES*100)
## 从结果可以,少量添加或者减少时，改变的不多 ##
## 相比较而言，增加节点要比减少节点，变化更少 ##
- 文章
- 推荐
- 热门新闻