HashMap 源码解读

本贴最后更新于 2045 天前,其中的信息可能已经天翻地覆
数据结构
  • HashMap 整体结构为数组 + 链表(解决 hash 冲突)
length
  • 数组默认的 length 为 16,填充因子为 0.75,即当数组填充了 length*0.75 个后数组开始扩容为 length<<1
put
  • 根据新计算的 hash 值取模数组长度,得到散列的 index,若当前 indexnull,直接在 index 处添加数据,为 Node 类型,链表的数据结构,若当前 index 不为 null,循环判断当前的 index.next 是否为 null,添加到当前链表的末尾。当链表长度大于特定的阈值时(默认为 8),将链表结构调整为红黑树的结构,Node 类型更改为 TreeNode
resize
  • 数组扩容时,old 数组的元素要重新计算 index 放入到扩容后的新数组,next 为空时仍然用 hash 和扩容后的数组长度去模得到新的 indexnext 不为空的链表会将 next 的值放到当前 index,原来该 index 的元素放到 oldIndex+oldLength(调整过程略复杂,感觉类似于平衡二叉树的自调整)
index
  • 计算散列的 index 时使用的方法是 hash&(length-1)。这是一种较为优雅的取模算法,效果等同于 hash%length。前提是数组长度为 2 的整数幂
  • 验证方法
     1010010 % 10000
    
     1010010
     &  1111
     0000010
    
    高位都是0,只有低位的1才能决定最终的结果,等同于取模运算
    
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3165 引用 • 8206 回帖
  • 源码解读
    1 引用
  • Index
    4 引用

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...