动手实现自己的简单HashMap

HashMap的核心是哈希函数以及冲突解决的办法

比较常用的哈希函数有RS、DJB等,设计原则是使目标元素的hash值尽可能分散,也就是在一定的容量内尽可能平均分布,详细可参考General Purpose Hash Function Algorithms

而解决冲突的办法主要有:开放定址法、链表法、多次哈希等

我们这里选择使用改进的FNV算法获取hash,使用数组entry作为哈希表,,使用单链表解决冲突

因此HashMap的结构就类似于:

entry[0] nullentry[1] obj1 -> obj2entry[2] nullentry[3] nullentry[4] obj3entry[5] obj4entry[6] nullentry[7] obj5肯承认错误则错已改了一半

动手实现自己的简单HashMap

相关文章:

你感兴趣的文章:

标签云: