map底层原理

2023-07-09 02:22| 来源: 网络整理| 查看: 265

map底层使用散列表hash，平时一直都在听hash，到底什么是hash？

一个哈希表里面有多个哈希表节点bucket，一个bucket保存了map中的一个或者一组键值对。

map本质上还是一个结构体

type hmap struct { count int // 当前保存的元素个数 B uint8 // 指示bucket数组的大小 buckets unsafe.Pointer // bucket数组指针，数组的大小为2^B }

bucket也是一个结构体

type bmap struct { tophash [8]uint8 //存储哈希值的高8位 data byte[1] //key value数据:key/key/key/.../value/value/value... overflow *bmap //溢出bucket的地址 }

是B决定了buckets 指向的数组的大小，还是相反呢？

当两个或者两个以上数量的键被哈希到了同一个bucket的时候，这些键就发生了冲突，这个具体的哈希的过程是怎么进行的呢？

冲突了之后，是先存储在八个位置中的其他位置吗？还是直接就存储到了overflow指向的bucket中了？

哈希因子过大，也就是键的数量变多，bucket数量变少，bucket的数量不是只有冲突的时候才会增多吗？如果增多了，那负载因子应该是会减少的？

【本文地址】

今日新闻