HashMap数据结构分析
2018-12-06 本文已影响0人
起猿日
基本结构:
数组+单向链表
元素:
Node,包含key value Node(next)
基本限制
数组默认长度:1<<4 即 16
数组最大值 :1<<30
默认加载因子:0.75 ------ 数组容量*0.75 = 12 (使用大小触发点:使用到12时做扩大数组容量的操作)
链表变形为红黑树的触发大小:8 -------- 注:变形目的是降低查找的时间复杂度。
红黑树变形为链表的触发大小:6
添加元素的方式
先存数组,如果重叠则往下存成链表
1.计算出在数组的位置
目的:得到0-15的某个值,方式:哈希算法,通过key的hashCode取数组大小的模-------key.hashCode()%数组大小=下标值(即数组位置)
源码中的具体细节
1.如果为空则resize() 初始化
2.根据hash进行运算,
3.node中的hash记录