关于Hash Table的小小思考——Touch With Next-Era HashTable#

1
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
2
    // 序列号
3
    private static final long serialVersionUID = 362498820763181265L;
4
    // 默认的初始容量是16
5
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
6
    // 最大容量
7
    static final int MAXIMUM_CAPACITY = 1 << 30;
8
    // 默认的负载因子
9
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
10
    // 当桶(bucket)上的结点数大于等于这个值时会转成红黑树
11
    static final int TREEIFY_THRESHOLD = 8;
12
    // 当桶(bucket)上的结点数小于等于这个值时树转链表
13
    static final int UNTREEIFY_THRESHOLD = 6;
14
    // 桶中结构转化为红黑树对应的table的最小容量
15
    static final int MIN_TREEIFY_CAPACITY = 64;
16
    // 存储元素的数组，总是2的幂次倍
17
    transient Node<k,v>[] table;
18
    // 一个包含了映射中所有键值对的集合视图
19
    transient Set<map.entry<k,v>> entrySet;
20
    // 存放元素的个数，注意这个不等于数组的长度。
21
    transient int size;
22
    // 每次扩容和更改map结构的计数器
23
    transient int modCount;
24
    // 阈值(容量*负载因子) 当实际大小超过阈值时，会进行扩容
25
    int threshold;
26
    // 负载因子
27
    final float loadFactor;
28
}

1
final Node<K,V>[] resize() {
2
    Node<K,V>[] oldTab = table;
3
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
4
    int oldThr = threshold;
5
    int newCap, newThr = 0;
6
    if (oldCap > 0) {
7
        // 超过最大值就不再扩充了，就只好随你碰撞去吧
8
        if (oldCap >= MAXIMUM_CAPACITY) {
9
            threshold = Integer.MAX_VALUE;
10
            return oldTab;
11
        }
12
        // 没超过最大值，就扩充为原来的2倍
13
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
14
            newThr = oldThr << 1; // double threshold
15
    }
16
    else if (oldThr > 0) // initial capacity was placed in threshold
17
        // 创建对象时初始化容量大小放在threshold中，此时只需要将其作为新的数组容量
18
        newCap = oldThr;
19
    else {
20
        // signifies using defaults 无参构造函数创建的对象在这里计算容量和阈值
21
        newCap = DEFAULT_INITIAL_CAPACITY;
22
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
23
    }
24
    if (newThr == 0) {
25
        // 创建时指定了初始化容量或者负载因子，在这里进行阈值初始化，
26
        // 或者扩容前的旧容量小于16，在这里计算新的resize上限
27
        float ft = (float)newCap * loadFactor;
28
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
29
    }
30
    threshold = newThr;
31
    @SuppressWarnings({"rawtypes","unchecked"})
32
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
33
    table = newTab;
34
    if (oldTab != null) {
35
        // 把每个bucket都移动到新的buckets中
36
        for (int j = 0; j < oldCap; ++j) {
37
            Node<K,V> e;
38
            if ((e = oldTab[j]) != null) {
39
                oldTab[j] = null;
40
                if (e.next == null)
41
                    // 只有一个节点，直接计算元素新的位置即可
42
                    newTab[e.hash & (newCap - 1)] = e;
43
                else if (e instanceof TreeNode)
44
                    // 将红黑树拆分成2棵子树，如果子树节点数小于等于 UNTREEIFY_THRESHOLD（默认为 6），则将子树转换为链表。
45
                    // 如果子树节点数大于 UNTREEIFY_THRESHOLD，则保持子树的树结构。
46
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
47
                else {
48
                    Node<K,V> loHead = null, loTail = null;
49
                    Node<K,V> hiHead = null, hiTail = null;
50
                    Node<K,V> next;
51
                    do {
52
                        next = e.next;
53
                        // 原索引
54
                        if ((e.hash & oldCap) == 0) {
55
                            if (loTail == null)
56
                                loHead = e;
57
                            else
58
                                loTail.next = e;
59
                            loTail = e;
60
                        }
61
                        // 原索引+oldCap
62
                        else {
63
                            if (hiTail == null)
64
                                hiHead = e;
65
                            else
66
                                hiTail.next = e;
67
                            hiTail = e;
68
                        }
69
                    } while ((e = next) != null);
70
                    // 原索引放到bucket里
71
                    if (loTail != null) {
72
                        loTail.next = null;
73
                        newTab[j] = loHead;
74
                    }
75
                    // 原索引+oldCap放到bucket里
76
                    if (hiTail != null) {
77
                        hiTail.next = null;
78
                        newTab[j + oldCap] = hiHead;
79
                    }
80
                }
81
            }
82
        }
83
    }
84
    return newTab;
85
}

1
type hmap struct {
2
    //哈希表中的元素个数，len(m) 返回的就是该值
3
    count     int
4
    //状态（现在是否处于写入状态）
5
    flags     uint8
6
    //Buckets的对数
7
    B         uint8
8
    //溢出桶的数量
9
    noverflow uint16
10
    //生成hash的随机种子
11
    hash0     uint32
12
    //指向buckets数组的指针 (如果元素为0则为nil)
13
    buckets    unsafe.Pointer
14
    //如果扩容，指向老桶数组指针，len_ob = len_nb >> 1，否则为nil
15
    oldbuckets unsafe.Pointer
16
    //表示扩容进度，小于此地址的buckets代表迁移完成
17
    nevacuate  uintptr
18
    //溢出桶， 为了优化gc扫描
19
    extra *map.extra
20
}

1
type bmap struct {
2
    tophash [bucketCnt]uint8
3
    //长度8的数组，用于快速定位key的tophash是否匹配，来确定key是否在这个bucket中
4
}

1
type bmap struct {
2
    tophash [8]uint
3
    //编译器确定map的kv存储类型
4
    keys [8]keyType
5
    values [8]valueType
6
    //指向下一个bmap，用uintptr而不是*bmap是为了保证bmap结构中无显式指针，为了减少gc，而将溢出桶存储在extra字段中。
7
    overflow uintptr
8
}

1
loadFactor := count / (2 ^ B)

1
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
2
    if B > 15 {
3
        B = 15
4
    }
5
    return noverflow >= uint16(1)<<(B&15)
6
}

1
//hasGrow
2
bigger := uint8(1)
3
// 负载判断
4
if !overLoadFactor(h.count+1, h.B) {
5
    // 扩容
6
    bigger = 0
7
    h.flags |= sameSizeGrow
8
}
9

10
// 初始化新buckets
11
oldbuckets := h.buckets
12

13
//h.B + 1, 容量变成二倍
14
//h.b + 0, 容量不变
15
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

1
//真正的迁移
2
func growWork(t *maptype, h *hmap, bucket uintptr) {
3
    //判断old bucket是否被迁移过，没被迁移就直接迁移
4
    evacuate(t, h, bucket&h.oldbucketmask())
5
    if h.growing() {
6
        evacuate(t, h, h.nevacuate)
7
    }
8
}

1
type Map [K comparable, V any] struct {
2
    ctrl     []metadata
3
    groups   []group[K, V]
4
    hash     maphash.Hasher[K]
5
    resident uint32
6
    dead     uint32
7
    limit    uint32
8
}
9

10
type metadata [groupSize]int8
11

12
type group[K comparable, V any] struct {
13
    keys   [groupSize]K
14
    values [groupSize]V
15
}

1
//https://github.com/golang/go/blob/3f4164f508b8148eb526fc096884dba2609f5835/src/internal/runtime/maps/map.go#L194
2
type Map struct {
3
    globalDepth  uint8      // dir的全局深度
4
    dirPtr       unsafe.Pointer // dir指针（指向多个 table）
5
    // ...
6
}