哈希表（Hash Table，也叫散列表），是根据关键码值 (Key-Value) 而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
在Java中HashMap就是使用的哈希表。
在HashMap中实际存储数据时在一个数组中，在插入时如果放入key，通过(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)获取hash，在数据存入table时，通过(n - 1) & hash获取数据应该存入数组下角位置。如果该位置存在数据，在JDK1.8之前是通过一个链表存入，如果重复就会吧数据放入该链表后，在JDK1.8里面是先通过链表存储，如果链表长度超过TREEIFY_THRESHOLD8通过红黑树来存储的数据。在取值时通过比较值来判断获取的key是否是传入当然key。
在转换树时，通过判断MIN_TREEIFY_CAPACITY64，超过才会转换为树，为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。
在插入数据时，如果数据满了，当然不可能每次都放入链表或树中，这样在数据量较多的时候，会严重影响效率。在HashMap中有个扩容因子DEFAULT_LOAD_FACTOR，当插入数据后，数据大于该扩容因子，那么会把数据进行2倍的扩容，在扩容时，如果红黑树的长度小于UNTREEIFY_THRESHOLD6则会退化采用链表，同时把原有的数据重新插入。
理想状态下哈希表的节点中，元素的数量遵守泊松分布。当负载因子为 0.75 时，泊松公式中 λ 约等于 0.5，因此箱子中元素个数和概率的关系如下：
| 数量 |
概率 |
| 0 |
0.60653066 |
| 1 |
0.30326533 |
| 2 |
0.07581633 |
| 3 |
0.01263606 |
| 4 |
0.00157952 |
| 5 |
0.00015795 |
| 6 |
0.00001316 |
| 7 |
0.00000094 |
| 8 |
0.00000006 |
当数量为8时，概率极低，如果出现数量为8的情况，那么可能是因为hash函数设计导致问题，所以需要避免因为哈希函数导致性能问题，对链表转换为红黑树。
在插入数据时，获取key的hash需要满足散列结果应当具有同一性（输出值尽量均匀）和雪崩效应（微小的输入值变化使得输出值发生巨大的变化）。这样就能减少出现hash碰撞的情况。
通过python实现简单版hashmap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| class HashMap:
def __init__(self):
self.table = [None] * 10
self.size = 0
self.threshold = 1.5
def put(self, key, val):
add_node = self.__put_val(self.table, key, val)
if add_node:
self.size += 1
if self.size * self.threshold >= self.threshold * len(self.table):
self.resize()
def __put_val(self, table, key, val):
add_node = False
key_hash = self.key_hash(key)
node = table[key_hash]
if node is None:
table[key_hash] = LinkedNode(key_hash, key, val)
add_node = True
else:
while True:
if node.key == key:
node.val = val
break
if node.next is None:
node.next = LinkedNode(key_hash, key, val)
add_node = True
break
else:
node = node.next
return add_node
def get(self, key):
key_hash = self.key_hash(key)
node = self.table[key_hash]
val = None
while True:
if node is not None:
if node.key == key:
val = node.val
break
else:
node = node.next
else:
break
return val
def key_hash(self, key):
return key % len(self.table)
def resize(self):
new_table = [None] * len(self.table) * 2
for node in self.table:
while True:
if node is not None:
self.__put_val(new_table, node.key, node.val)
node = node.next
else:
break
self.table = new_table
class LinkedNode:
def __init__(self, hash, key, val):
self.hash = hash
self.key = key
self.val = val
self.next = None
|
上述只是简单实现，在计算hash时直接通过取模来获取。
上述使用hashmap有个缺点在于，如果数据量非常大，那么每次扩容迁移数据都得花费不少时间，因为要把旧数据迁移到新的数组中。
redis hash扩容
在上述扩容过程中比较慢，特别是数据量大时，但是在redis中hash扩容采用了另外一种机制。
在redis中时间存储简单理解为：redis中存储有两个数组，数组ht[0]，存储原本的数据，数组ht[1]用于扩容，同时有个字段rehashidx用来标识扩容进度。扩容如下：
1、先创建一个比ht[0]更大的table ht[1]
2、将ht[0]中的数据一步步迁移到ht[1]中
3、迁移完毕后，将ht[0]中数据清除，释放内存，将ht[1]替换为ht[0]
在扩容过程中，并不是一次性完成。避免因为服务器阻塞导致性能下降
1、_dictRehashStep被动迁移，一般是在插入、查找、删除都会触发执行，避免在一次操作中执行
2、dictRehashMilliseconds，服务器常规任务程序（server cron job）执行
在迁移过程中，查找、删除会在ht[0]、ht[1]中进行，新增只会在ht[1]中进行，这样保证了ht[0]只减不增。
除了扩容，还是缩容，操作与上述类型，创建一个小的table然后进行迁移。
- 在redis扩容过程中，链表迁移时，会把数据放到链表前面，这样的好处是，插入较快，而且新插入的数据可能会频繁的获取。
上述hash表的实现使用的拉链发，也就是出现hash碰撞时，使用链表存储相同hash的数据。
实际上除了拉链法，还有开放地址散列法，开放地址散列法中包括：线性散列、二次散列等，其实就是单出现hash碰撞时，如果当前位置已经存在值，那么就放入下一个节点。
动态hash
主要是为了解决规模扩展的问题，主体思路是在数据规模变大后，映射的范围将翻倍，新数据的插入将按照最新的映射范围插入
hash一致
主要是为了解决分布式系统如何扩展的问题，主体思路是保证数据分布的均匀性和单调性。
在分布式调用不同服务器时，通过取hash来判断应该定位到哪台服务器，或者在mysql数据库做迁移时，确定数据迁移到了哪台服务器，如果后期服务器增加，使用普通hash取模计算，会到手所有数据都要做迁移。
使用hash一致算法就可以减少迁移的数量。
示例如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
class UniformityHassNotVirtualNode {
static TreeMap<Integer, String> dbMap = new TreeMap<>();
static {
String db = "192.168.0.1:3306";
addNode(db);
db = "192.168.0.2:3306";
addNode(db);
db = "192.168.0.3:3306";
addNode(db);
db = "192.168.0.4:3306";
addNode(db);
db = "192.168.0.5:3306";
addNode(db);
}
public static void addNode(String db) {
dbMap.put(strHash(db), db);
}
public static void removeNode(String db) {
dbMap.remove(strHash(db));
}
public static int strHash(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < str.length(); i++)
hash = (hash ^ str.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
if (hash < 0)
hash = Math.abs(hash);
return hash;
}
public static String findDb(String key) {
int hash = strHash(key);
Integer nodeKey = dbMap.ceilingKey(hash);
return nodeKey == null ? dbMap.firstEntry().getValue() : dbMap.get(nodeKey);
}
}
public class Main {
private static Map<String, String> storeNos = new HashMap<>();
public static void main(String[] args) {
IntStream.range(1000, 1050).forEach((i) -> storeNos.put(String.valueOf(i), UniformityHassNotVirtualNode.findDb(String.valueOf(i))));
storeNos.forEach((key, val) -> System.out.printf("key: %s db: %s \n", key, val));
String db = "192.168.0.8:3306";
System.out.printf("新增节点 %s \n", db);
UniformityHassNotVirtualNode.addNode(db);
printNode();
db = "192.168.0.4:3306";
System.out.printf("删除节点 %s \n", db);
UniformityHassNotVirtualNode.removeNode(db);
printNode();
}
public static void printNode() {
storeNos.forEach((key, val) -> {
String findDb = UniformityHassNotVirtualNode.findDb(key);
if (findDb.equals(val)) {
System.out.printf("key: %s db: %s 未发生变化\n", key, val);
} else {
System.out.printf("key: %s db: %s 发生迁移，原来节点：%s\n", key, findDb, val);
storeNos.put(key, findDb);
}
});
}
}
|
上述中通过hash找到对应的数据库地址。
具体hash解释以及图像参考：
- 对一致性Hash算法，Java代码实现的深入研究
- 一致性哈希算法在分布式缓存中的应用
在使用上述一致hash时，因为节点较少，所有可能会出现大量数据集中在某一个节点，这时可以引入虚拟节点。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
|
public static void addNode(String db) {
IntStream.range(0, 100).forEach((i)->{
String virtualNode = db + "#" + i;
dbMap.put(strHash(virtualNode), virtualNode);
});
}
public static void removeNode(String db) {
dbMap.entrySet().removeIf(next -> next.getValue().startsWith(db));
}
|
使用虚拟节点后就很少存在某个节点存在大量的数据了。
参考：