看完还不懂看完还不懂HashMap算我输(附职场面试常见问题)算我输(附职场面试常见问题)
HashMap的原理与实现的原理与实现
版本之更迭:版本之更迭:
–》》JDK 1.7 : Table数组+ Entry链表;
–》》JDK1.8 : Table数组+ Entry链表/红黑树;(为什么要使用红黑树?)
一问一问HashMap的实现原理的实现原理
你看过HashMap源码吗,知道底层的原理吗
为什么使用数组+链表
用LinkedList代替数组可以吗
既然是可以的,为什么不用反而用数组。
重要变量介绍:重要变量介绍:
ps:都是重要的变量记忆理解一下最好。
DEFAULT_INITIAL_CAPACITY Table数组的初始化长度: 1 << 4 2^4=16(为什么要是 2的n次方?)
MAXIMUM_CAPACITY Table数组的最大长度: 1<<30 2^30=1073741824
DEFAULT_LOAD_FACTOR 负载因子:默认值为0.75。 当元素的总个数>当前数组的长度 * 负载因子。数组会进行扩容,扩容为原来的两倍
(todo:为什么是两倍?)
TREEIFY_THRESHOLD 链表树化阙值: 默认值为 8 。表示在一个node(Table)节点下的值的个数大于8时候,会将链表转换成为红黑
树。
UNTREEIFY_THRESHOLD 红黑树链化阙值: 默认值为 6 。 表示在进行扩容期间,单个Node节点下的红黑树节点的个数小于6时候,会将
红黑树转化成为链表。
MIN_TREEIFY_CAPACITY = 64 最小树化阈值,当Table所有元素超过改值,才会进行树化(为了防止前期阶段频繁扩容和树化过程冲
突)。
实现原理:实现原理:
实现原理图实现原理图 我们都知道,在HashMap中,采用数组+链表的方式来实现对数据的储存。
HashMap采Entry数组来存储key-value对,每个键值对组成了个Entry实体,Entry类实际上是个单向的链表结 构,它具有Next指针,
可以连接下个Entry实体。 只是在JDK1.8中,链表度于8的时候,链表会转成红树!
第一问:第一问: 为什么使用链表+数组:要知道为什么使用链表首先需要知道Hash冲突是如何来的: