常见语言的hashmap实现方法

总结一下常见语言的hashmap实现方法

CSharp

c# 中叫 Dictionary，
一个int数组bucket + 一个Entry数组 结构实现
还有一个free链表，存放remove后的节点

size : 长度计算：取大于传入长度的第一个素数

内存占用

bucket : 一个int数组，长度为 size
entries: 一个Entry数组
Entry ：以key value都为int为例： 8 + 4 + 4 = 16B
private struct Entry {
public int hashCode; // Lower 31 bits of hash code, -1 if unused
public int next; // Index of next entry, -1 if last
public TKey key; // Key of entry
public TValue value; // Value of entry
}
hashCode的最高位用来标记这个节点是否被使用。
count ： int，记录以申请节点数
version：int ，值修改次数，用来在遍历的时候判断是否有修改hashmap的行为
freelist ：int， 空闲节点链表头，删除的节点会被挂到改链表
freeCount：int，空闲节点数量

大小：size * 4 + size * 16 + 4 + 4 + 4 + 4 = 16 + size * 20

插入

计算key的hash值，取后31位 ： hash(key) & 0x7FFFFFFF;
hash值对size取余得到index，表示在哪个桶中
每个桶都是一个有相同index的链表
遍历链表，比较hashcode和key（先比较hashcode，整数比较快），有一样的就修改value，增加verison值，直接返回，不用插入。否则记录下链表长度 collisionCount
如果有空闲节点，则待分配节点索引从空闲链表头取，否则待分配节点索引为count，count不够时，resize，长度为2倍当前count的下一个素数；
设置 entries[index] 的hashcode、key、next、value，插入对应bucket头
collisionCount 为碰撞次数，当链表长度超过100时，进行rehash，数据长度不变，更新hash计算方式

删除 remove

安全判断，key和bucket必须不为空
同插入，计算所在bucket
遍历bucket，找到同hashcode和key的节点，从bucket中删除节点，并将节点索引加入freelist
重置待删除节点数据：hashcode置为-1，key value置为默认值

resize

根据大小，重新分配空间，重新计算hash（可选），重新放到不同的bucket中

遍历

初始index=0
遍历 entries，entries[index] 的 hashcode >= 0 即为有值

C++

c++ 中叫做 unordered_map
实现方式和C# 一样，不同：

1. 每个索引对应的链表长度超过8时，会转换为红黑树，以保证查找效率
2. hash 取索引采用位运算，bucket大小为2的幂，能提升运算速度

素数还是2的幂

关于使用素数还是2的幂作为mod，有以下思考：

1. 如果数据是分布均匀的，则mod使用什么数都可以，这时选择2的幂更优
2. 如果数据分布不均匀，使用素数会比使用非素数的分布更加均匀

如果hash函数足够优秀或者数据分布均匀，使用2的幂是更佳方案
和数据分布有很大关系，比如你的key都是整数，表示内存地址，因为内存地址是4字节对齐，你的key可能都是4的倍数，导致数据都堆积在4的倍数的hash桶中。这时选用素数效果会更好。

Lua

lua 没有使用bucket，直接用entries做索引数组

插入

1. 计算hash对应的index，计算方法和c++一样
2. 如果entries[index] 为空直接插入
3. 否则看entries[index] 的index是否一样，一样说明是一个碰撞链上的，从freenode处取一个节点，freenode前移，插入尾部
4. 不一样的话，entries[index]移出，待插入的数据插入，从 freenode 取节点放entries[index]。
5. freenode移到起始位置就resize。freenode只减不增

其他大差不差

总结

lua的方案更省空间，但是freenode只会减，哪怕后面有空节点，也不会分配，只会走rehash逻辑。另外填充率高了后，如果走到步骤4会比较耗时。
c++的方案应该是最好的，链表会转为红黑树保证查找效率（转红黑树有开销，实现也比较麻烦），hash函数比较好的话，长度为2的幂效率也更高。