阅读云风开源的AOI实现时，看到里面有一个hashmap算法实现。
https://github.com/cloudwu/aoi
这里记录下分享下其实现
map内部存储是使用数组实现即 map_slot，初始分配16个。容量不足时，以翻倍容量增加，并将对象重新进行分配至新的内存空间。
这里画图举例时以初始容量为8进行原理说明：
1、初始状态，所有slot处于未分配
2、插入A，使用hash算法计算出应该分配在哪个slot上(注：可以考虑添加扰动函数避免比较差的hash算法，这里针对aoi的情况，直接使用了对size取模)
假设对A取模后将其放入第三个slot
3、继续插入B和C，其中B和A取模后 不在相同的slot中。
然后是取模后分配到相同的slot的情况：
实际上两个对象不会存在相同的slot中。
这里如果出现分配的slot中已经存在对象了，比如此时，C分配的第三个slot已经存在A了。
则从数组最尾部向前查找第一个为空的slot，将C放入，并将A.next指向C所在的slot
4、继续插入一个和A相同slot的对象时，继续从尾部向前查找一个空的slot，并将A.next指向新分配的slot，新分配的slot.next指向原A.next ( 即C)
5、如果遇到分配的slot被其它slot的对象占用如何处理。
比如，我这里想分配E，取模后应该分配在第七个格子，但第七个格子已经被D占用。
这里采用的方式，是将D取出( 因为D取模不应该分配在第七个格子，只是因为第三个格子被占用了，所以才从尾部查找的一个空闲的格子放D)，取出D后将E放后，如下图：
这里D被取出应该如何处理，再执行一个第1步，将D放hashmap即可。
0 条评论。