深入分析hashmap
一、传统 HashMap的缺点
(1)JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。
(2)当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。
(3)针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题
二、JDK1.8中HashMap的数据结构
2.1HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的
新增红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>
{
TreeNode<K,V>
parent; //
red-black tree links
TreeNode<K,V>
left;
TreeNode<K,V>
right;
TreeNode<K,V>
prev; //
needed to unlink next upon deletion
boolean red;
}
|
2.2HashMap 中关于红黑树的三个关键参数
|
TREEIFY_THRESHOLD |
UNTREEIFY_THRESHOLD |
MIN_TREEIFY_CAPACITY |
|---|---|---|
|
static final int UNTREEIFY_THRESHOLD = 6 |
|
|
|
|
2.3HashMap 在 JDK 1.8 中新增的操作：桶的树形化 treeifyBin()
在Java 8 中，如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8 )，就使用红黑树来替换链表，从而提高速度。
这个替换的方法叫 treeifyBin() 即树形化。
//将桶内所有的
链表节点 替换成 红黑树节点
1 final void treeifyBin(Node<K,V>[]
tab, int hash)
{
2 int n,
index; Node<K,V> e;
3 //如果当前哈希表为空，或者哈希表中元素的个数小于
进行树形化的阈值(默认为 64)，就去新建/扩容
4 if (tab
== null ||
(n = tab.length) < MIN_TREEIFY_CAPACITY)
5 resize();
6 else if ((e
= tab[index = (n - 1)
& hash]) != null)
{
7 //如果哈希表中的元素个数超过了
树形化阈值，进行树形化
8 //
e 是哈希表中指定位置桶里的链表节点，从第一个开始
9 TreeNode<K,V>
hd = null,
tl = null; //红黑树的头、尾节点
10 do {
11 //新建一个树形节点，内容和当前链表节点
e 一致
12 TreeNode<K,V>
p = replacementTreeNode(e, null);
13 if (tl
== null) //确定树头节点
14 hd
= p;
15 else {
16 p.prev
= tl;
17 tl.next
= p;
18 }
19 tl
= p;
20 } while ((e
= e.next) != null);
21 //让桶的第一个元素指向新建的红黑树头结点，以后这个桶里的元素就是红黑树而不是链表了
22 if ((tab[index]
= hd) != null)
23 hd.treeify(tab);
24 }
25 }
26 TreeNode<K,V>
replacementTreeNode(Node<K,V> p, Node<K,V> next) {
27 return new TreeNode<>(p.hash,
p.key, p.value, next);
28 }
|
上述操作做了这些事:
(1)根据哈希表中元素个数确定是扩容还是树形化
(2)如果是树形化遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系
(3)然后让桶第一个元素指向新建的树头结点，替换桶的链表内容为树形内容
三、分析HashMap的put方法
3.1HashMap的put方法执行过程可以通过下图来理解，自己有兴趣可以去对比源码更清楚地研究学习。
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
- 上一篇： ipython常用方法说明
- 下一篇： python learning1
