Dict(hash)

发表于 分类于 ， ，

1.Dict由 哈希表 + 哈希节点 + 字典 组成
image1

1.1 哈希冲突用拉链法
image2

1.2 Dict 内存 结构
image3

2.1 rehash

2.1.1 扩容
由于size是固定的,当used达到一定大小必然出现hash冲突,
我们就规定一个负载因子used/size ,大于1的时候就说明用了拉链法
那么查找的话就要遍历链表,导致性能变差,因此需要对其进行扩容,
也即增加dictEntry[]的大小

image4

2.1.2 收缩
image5

2.1.3
过程图解

a.超出后复制rehash(因为sizemask变了,必须要rehash c)
image6

  1. 接管新的dictEntry*[]
    image7

2.1.4 rehash的时间—>渐进式的rehash
rehashidx用来判断当前rehash到了那个桶, 标记迁移的进度
image8

2.1.5 总结 ,注意扩容都是以2的幂为进制的
image9