HashMap实现原理分析(8)

if (dictIsRehashing(d)) _dictRehashStep(d);
// …
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
第二句就是用来选择插入到哪个哈希表中，第一句话则是迁移 rehashidx 位置上的链表。它实际上会调用 dictRehash(d,1)，也就是说是单步长的迁移。dictRehash 函数的实现如下:

int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */

while(n-- && d->ht[0].used != 0) { dictEntry *de, *nextde; while(d->ht[0].table[d->rehashidx] == NULL) { d->rehashidx++; if (--empty_visits == 0) return 1; } de = d->ht[0].table[d->rehashidx]; /* Move all the keys in this bucket from the old to the new hash HT */ while(de) { unsigned int h; nextde = de->next; /* Get the index in the new hash table */ h = dictHashKey(d, de->key) & d->ht[1].sizemask; de->next = d->ht[1].table[h]; d->ht[1].table[h] = de; d->ht[0].used--; d->ht[1].used++; de = nextde; } d->ht[0].table[d->rehashidx] = NULL; d->rehashidx++; } /* Check if we already rehashed the whole table... */ if (d->ht[0].used == 0) { zfree(d->ht[0].table); d->ht[0] = d->ht[1]; _dictReset(&d->ht[1]); d->rehashidx = -1; return 0; } return 1;

}
这段代码比较长，但是并不难理解。它由一个 while 循环和 if 语句组成。在单步迁移的情况下，最外层的 while 循环没有意义，而它内部又可以分为两个 while 循环。

第一个循环用来更新 rehashidx 的值，因为有些箱子为空，所以 rehashidx 并非每次都比原来前进一个位置，而是有可能前进几个位置，但最多不超过 10。第二个循环则用来复制链表数据。

最外面的 if 判断中，如果发现旧哈希表已经全部完成迁移，就会释放旧哈希表的内存，同时把新的哈希表赋值给旧的哈希表，最后把 rehashidx 重新设置为 -1，表示重哈希过程结束。

默认哈希函数
与 Java 不同的是，Redis 提供了 void * 类型 key 的哈希函数，也就是通过任何类型的 key 的指针都可以求出哈希值。具体算法定义在 dictGenHashFunction 函数中，由于代码过长，而且都是一些位运算，就不展示了。

它的实现原理是根据指针地址和这一块内存的长度，获取内存中的值，并且放入到一个数组当中，可见这个数组仅由 0 和 1 构成。然后再对这些数字做哈希运算。因此即使两个指针指向的地址不同，但只要其中内容相同，就可以得到相同的哈希值。

归纳对比

首先我们回顾一下 Java 和 Redis 的解决方案。

Java 的长处在于当哈希函数不合理导致链表过长时，会使用红黑树来保证插入和查找的效率。缺点是当哈希表比较大时，如果扩容会导致瞬时效率降低。

Redis 通过增量式扩容解决了这个缺点，同时拉链法的实现(放在链表头部)值得我们学习。Redis 还提供了一个经过严格测试，表现良好的默认哈希函数，避免了链表过长的问题。

Objective-C 的实现和 Java 比较类似，当我们需要重写 isEqual() 方法时，还需要重写 hash 方法。这两种语言并没有提供一个通用的、默认的哈希函数，主要是考虑到 isEqual() 方法可能会被重写，两个内存数据不同的对象可能在语义上被认为是相同的。如果使用默认的哈希函数就会得到不同的哈希值，这两个对象就会同时被添加到 NSSet 集合中，这可能违背我们的期望结果。

根据我的了解，Redis 并不支持重写哈希方法，难道 Redis 就没有考虑到这个问题么？实际上还要从 Redis 的定位说起。由于它是一个高效的，Key-Value 存储系统，它的 key 并不会是一个对象，而是一个用来唯一确定对象的标记。

一般情况下，如果要存储某个用户的信息，key 的值可能是这样: user:100001。Redis 只关心 key 的内存中的数据，因此只要是可以用二进制表示的内容都可以作为 key，比如一张图片。Redis 支持的数据结构包括哈希表和集合(Set)，但是其中的数据类型只能是字符串。因此 Redis 并不存在对象等同性的考虑，也就可以提供默认的哈希函数了。

Redis、Java、Objective-C 之间的异同再次证明了一点:

“`

总结：
1.HashMap线程不安全，主要是多线程put，get是会出现同步问题；
2.多线程操作HashMap是容易出现循环链表，导致get方法调用时可能出现死循环；
3.安全的使用Map有三种方式：Hashtable，SynchronizedMap，ConcurrentHashMap。其中Hashtable不推荐使用，ConcurrentHashMap效率最高。