|
前两天有小伙伴问道是否看过Go语言map的实现，当时还真没看过，于是就花了一点时间看了一遍runtime源码中的hashmap实现。map的底层实现就是一个hash表，大体结构上和平时在脑海里的hash表差不多，但确实有很多细节(“Devils in the details”)。
hashmap通过一个bucket数组实现，所有元素将被hash到数组中的bucket中，bucket填满后，将通过一个overflow指针来扩展一个bucket出来形成链表，也就是解决冲突问题。这也就是一个基本的hash表结构，没什么新奇的东西，下面总结一些细节吧。
- 注意一个bucket并不是只能存储一个key/value对，而是可以存储8个key/value对。每个bucket由header和data两部分组成，data部分的内存大小为：(sizeof(key) + sizeof(value)) * 8，也就是要存储8对key/value，这8对key/value在data内存中的存储顺序是：key0key1…key7value0value1…value7，是按照顺序先依次存储8个key值，然后存储对应的8个value。 为什么不是存储为key0value0…key7value7呢？主要是方便访问吧。
- 如果key, value的类型大小超过了128字节，将不会直接存储值，而是存储其指针。
- bucket的header部分有一个
uint8 tophash[8]数组，这个数组将用来存储8个key的hash值的高8位值。比如：tophash[0]存储的值就是hash(key0) ? (64 - 8)。保存了一个key的hash高8位部分，在查找/删除/插入一个key的时候，可以先判断两个key hash的高8位是否相等，如果不等，那就根本不用去比较key的内容。所以这里保存一下hash值的高8位可以作为第一步的粗略过滤，不少时候可以省掉比较两个key的内容，因为比较两个key是否相等的代价远比两个uint8的代价高。当然，这里如果存储整个hash值，而不仅仅是高8位的话，判断效果将更好，但内存的占用就会多很多了。
- bucket的8个key/value空间如果都填满后，就会分配新的bucket，通过overflow指针串联起来。注意这个链表指针被命名为overflow，代表的正是bucket溢出了，这个命名感觉很好，hash表实现的时候我们应该努力避免bucket overflow。
- hashmap是会自增长的，也就说随着插入的kv对越来越多，初始的bucket数组就可以需要增长、重新hash所有元素，性能才会好。bucket数组增长的时机就是插入的元素个数大于了
bucket数组大小 * 6.5，为什么是6.5，这个在代码注释里有说明，主要是测试出来的经验值。
- hashmap每次增长，都是重新分配一个新的bucket数组，新bucket数组是之前bucket数组的2倍大小。
- hashmap增长后，需要将老bucket数组中的元素拷贝到新的bucket数组，这个拷贝过程不是一口气立马完成的，而是采用了增量式的拷贝，也就是说分配了新的bucket数组后，并没有立刻拷贝元素，而是等接下来每次插入一个元素的时候，才拷贝一点，随着插入的动作增多，逐渐就将全部元素拷贝到了新的bucket数组中。
- 在make一个map对象的时候，如果不指定大小的话，bucket数组默认就是1了，随着插入的元素增多，就会增长成2，4，8，16等。可以看出不指定初始化大小的map，很可能要经历很多次的增长、元素拷贝。我们应该给map指定一个合适的大小值。
暂时就总结这么一点了。。。
浙江省图空调开得真冷啊，冷死我了，我要出去晒会太阳了。
|
