造个轮子-HashMap
dongfangqiezi 人气:1造个轮子-HashMap
发现自己对看源码特别痛苦,而且看了就忘。有必要按照源码已有的功能需求按照自己的想法去写一个轮子,然后比对着看才能理解。
需求分析
hashMap
功能很多,结构为数组+链表(暂时忽略红黑树),准备就写两个基本功能:
put
存数:懒加载数组,到达阈值(负载因子0.75)扩容,hash冲突开始链表模式。get
取数:能在hash冲突的情况下取出正确的数。
我就围绕这两个功能来仿照写一个WheelHashMap
。
开始
新建WheelHashMap
类
基本属性和hashMap
保持一致
hash
方法复制hashMap
的
put
方法
resize
扩容方法
get
方法
总结
在造轮子的过程中体会到为什么数组长度要是2的倍数
- 通过hash值去计算数组坐标
hash & (length-1)
,一般是通过取余实现,这里用与运算效率比取余高,正是因为2的倍数,才能这样设计。 - 扩容时对于hash冲突的链表rehash的高低位设计,也是因为2的倍数才能这么巧妙。
代码可以在Github上找到
本文来自chentiefeng的博客
加载全部内容