造个轮子-HashMap

发现自己对看源码特别痛苦，而且看了就忘。有必要按照源码已有的功能需求按照自己的想法去写一个轮子，然后比对着看才能理解。

需求分析

hashMap功能很多，结构为数组+链表（暂时忽略红黑树），准备就写两个基本功能：

  • put存数：懒加载数组，到达阈值（负载因子0.75）扩容，hash冲突开始链表模式。
  • get取数：能在hash冲突的情况下取出正确的数。

我就围绕这两个功能来仿照写一个WheelHashMap。

开始

新建WheelHashMap类

基本属性和hashMap保持一致

hash方法复制hashMap的

put方法

resize扩容方法

get方法

总结

在造轮子的过程中体会到为什么数组长度要是2的倍数

  1. 通过hash值去计算数组坐标hash & (length-1)，一般是通过取余实现，这里用与运算效率比取余高，正是因为2的倍数，才能这样设计。
  2. 扩容时对于hash冲突的链表rehash的高低位设计，也是因为2的倍数才能这么巧妙。

代码可以在Github上找到

本文来自chentiefeng的博客

版权声明：本文为dongfangqiezi原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/dongfangqiezi/p/12101288.html