HashMap
继承了AbstractMap<K,V>
抽象类,实现了Map<K,V>, Cloneable, Serializable
接口。
HashMap的存储结构
HashMap由一个Enrty[]数组组成,Entry是一个节点,有k数组的每个元素都是一个单链表的头节点,链表是用来解决冲突的,如果不同的key映射到了数组的同一位置处,就将其放入单链表中。
常用函数的内部实现
变量
1 | // 默认的初始容量(容量为HashMap中槽的数目)是16,且实际容量必须是2的整数次幂。 |
构造函数
容量表示哈希表中槽的数量(即哈希数组的长度),初始容量是创建哈希表时的容量(从构造函数中可以看出,如果不指明,则默认为16),加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 resize 操作(即扩容)。
关于加载因子:如果加载因子越大,对空间的利用更充分,但是查找效率会降低(链表长度会越来越长);如果加载因子太小,那么表中的数据将过于稀疏(很多空间还没用,就开始扩容了),对空间造成严重浪费。如果我们在构造方法中不指定,则系统默认加载因子为0.75,这是一个比较理想的值,一般情况下我们是无需修改的。
另外,无论我们指定的容量为多少,构造方法都会将实际容量设为不小于指定容量的2的次方的一个数,且最大值不能超过2的30次方
1 | // 指定“容量大小”和“加载因子”的构造函数 |
Entry类定义
1 | // Entry是单向链表。 |
hash()方法/indexFor()方法
为什么哈希表的容量一定要是2的整数次幂:
length为2的整数次幂的话,h&(length-1)就相当于h对length取模,这样便保证了散列的均匀,同时也用位运算代替取模运算提升了效率
length为2的整数次幂的话,为偶数,这样length-1为奇数,奇数的最后一位是1,这样便保证了h&(length-1)的最后一位可能为0,也可能为1(这取决于h的值),即与后的结果可能为偶数,也可能为奇数,这样便可以保证散列的均匀性,而如果length为奇数的话,很明显length-1为偶数,它的最后一位是0,这样h&(length-1)的最后一位肯定为0,即只能为偶数,这样任何hash值都只会被散列到数组的偶数下标位置上,这便浪费了近一半的空间,因此,length取2的整数次幂,是为了使不同hash值发生碰撞的概率较小,这样就能使元素在哈希表中均匀地散列。
1 | // 求hash值的方法,重新计算hash值 |
get()方法
注意:HashMap对象的key、value值均可为null。
HahTable对象的key、value值均不可为null。
首先,如果key为null,则直接从哈希表的第一个位置table[0]对应的链表上查找。记住,key为null的键值对永远都放在以table[0]为头结点的链表中,当然不一定是存放在头结点table[0]中。
如果key不为null,则先求的key的hash值,根据hash值找到在table中的索引,在该索引对应的单链表中查找是否有键值对的key与目标key相等,有就返回对应的value,没有则返回null。
1 | // 获取key对应的value |
containsKey()/containsValue()方法
containsKey方法和containsValue方法。前者直接可以通过key的哈希值将搜索范围定位到指定索引对应的链表,而后者要对哈希数组的每个链表进行搜索。
1 | // HashMap是否包含key |
put()方法
若key为null则添加在table[0]的Entry链表的头部。若key不为空,计算key的哈希值,找到对应的链表。若该<k,v>已存在,即在链表中能够找到hash值相等,key值也相等的(遍历时间复杂度O(k),k为链表长度),则用新value代替旧value;若<k,v>不存在或者该单链表为空,则将<k,v>添加到对应链表的头部(每次新插入的节点都是放在头结点的位置),添加后判断是否需要扩容。
HashMap中key和value都允许为null。
1 |
|
resize()扩容方法
扩容是一个相当耗时的操作,因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此,我们在用HashMap的时,最好能提前预估HashMap中元素的个数,这样有助于提高HashMap的性能。
1 | // 重新调整HashMap的大小,newCapacity是调整后的容量 |
remove()函数
1 | // 删除“键为key”元素 |
equals()方法/hashCode()方法
1 | // 判断两个Entry是否相等 |
clear()方法
1 | // 清空HashMap,将所有的元素设为null |
clone()方法
1 | // 克隆一个HashMap,并返回Object对象 |
JDK1.8新增红黑树
传统 HashMap 的缺点
JDK 1.8 以前 HashMap 的实现是 数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。
当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,这个时候 HashMap 就相当于一个单链表,假如单链表有 n 个元素,遍历的时间复杂度就是 O(n),完全失去了它的优势。
新增红黑树简介
针对这种情况,JDK 1.8 中引入了 红黑树(查找时间复杂度为 O(logn))来优化这个问题。
JDK 1.8 中 HashMap 中除了链表节点:
1 | static class Node<K,V> implements Map.Entry<K,V> { |
还有另外一种节点:TreeNode,它是 1.8 新增的,属于数据结构中的红黑树:
1 | static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { |
可以看到就是个红黑树节点,有父亲、左右孩子、前一个元素的节点,还有个颜色值。
另外由于它继承自 LinkedHashMap.Entry ,而 LinkedHashMap.Entry 继承自 HashMap.Node ,因此还有额外的 6 个属性:
1 | //继承 LinkedHashMap.Entry 的 |
HashMap 中关于红黑树的三个关键参数
HashMap 中有三个关于红黑树的关键参数:
TREEIFY_THRESHOLD
UNTREEIFY_THRESHOLD
MIN_TREEIFY_CAPACITY
值及作用如下:
1 | //一个桶的树化阈值 |
HashMap 在 JDK 1.8 中新增的操作:桶的树形化 treeifyBin()
在Java 8 中,如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8 ),就使用红黑树来替换链表,从而提高速度。
这个替换的方法叫 treeifyBin() 即树形化。
1 | //将桶内所有的 链表节点 替换成 红黑树节点 |
上述操作做了这些事:根据哈希表中元素个数确定是扩容还是树形化,如果是树形化,遍历桶中的元素,创建相同个数的树形节点,复制内容,建立起联系,然后让桶第一个元素指向新建的树头结点,替换桶的链表内容为树形内容。但是我们发现,之前的操作并没有设置红黑树的颜色值,现在得到的只能算是个二叉树。在最后调用树形节点 hd.treeify(tab) 方法进行塑造红黑树,来看看代码:
1 | final void treeify(Node<K,V>[] tab) { |
可以看到,将二叉树变为红黑树时,需要保证有序。这里有个双重循环,拿树中的所有节点和当前节点的哈希值进行对比(如果哈希值相等,就对比键,这里不用完全有序),然后根据比较结果确定在树种的位置。
HashMap 在 JDK 1.8 中新增的操作: 红黑树中添加元素 putTreeVal()
上面介绍了如何把一个桶中的链表结构变成红黑树结构。
在添加时,如果一个桶中已经是红黑树结构,就要调用红黑树的添加元素方法 putTreeVal()。
1 | final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, |
通过上面的代码可以知道,HashMap 中往红黑树中添加一个新节点 n 时,有以下操作:
从根节点开始遍历当前红黑树中的元素 p,对比 n 和 p 的哈希值;
如果哈希值相等并且键也相等,就判断为已经有这个元素(这里不清楚为什么不对比值);
如果哈希值就通过其他信息,比如引用地址来给个大概比较结果,这里可以看到红黑树的比较并不是很准确,注释里也说了,只是保证个相对平衡即可;
最后得到哈希值比较结果后,如果当前节点 p 还没有左孩子或者右孩子时才能插入,否则就进入下一轮循环;
插入元素后还需要进行红黑树例行的平衡调整,还有确保根节点的领先地位。
HashMap 在 JDK 1.8 中新增的操作: 红黑树中查找元素 getTreeNode()
HashMap 的查找方法是 get():
1 | public V get(Object key) { |
它通过计算指定 key 的哈希值后,调用内部方法 getNode();
1 | final Node<K,V> getNode(int hash, Object key) { |
这个 getNode() 方法就是根据哈希表元素个数与哈希值求模(使用的公式是 (n - 1) &hash)得到 key 所在的桶的头结点,如果头节点恰好是红黑树节点,就调用红黑树节点的 getTreeNode() 方法,否则就遍历链表节点。
1 | final TreeNode<K,V> getTreeNode(int h, Object k) { |
getTreeNode 方法使通过调用树形节点的 find() 方法进行查找:
1 | //从根节点根据 哈希值和 key 进行查找 |
添加时已经保证这个树是有序的,因此查找时基本就是折半查找,效率很高。
这里和插入时一样,如果对比节点的哈希值和要查找的哈希值相等,就会判断 key 是否相等,相等就直接返回(也没有判断值哎);不相等就从子树中递归查找。
HashMap 在 JDK 1.8 中新增的操作: 树形结构修剪 split()
HashMap 中, resize() 方法的作用就是初始化或者扩容哈希表。当扩容时,如果当前桶中元素结构是红黑树,并且元素个数小于链表还原阈值 UNTREEIFY_THRESHOLD (默认为 6),就会把桶中的树形结构缩小或者直接还原(切分)为链表结构,调用的就是 split():
1 | //参数介绍 |
从上述代码可以看到,HashMap 扩容时对红黑树节点的修剪主要分两部分,先分类、再根据元素个数决定是还原成链表还是精简一下元素仍保留红黑树结构。
1.分类
指定位置、指定范围,让指定位置中的元素 (hash & bit) == 0 的,放到 lXXX 树中,不相等的放到 hXXX 树中。
2.根据元素个数决定处理情况
符合要求的元素(即 lXXX 树),在元素个数小于 6 时还原成链表,最后让哈希表中修剪的痛 tab[index] 指向 lXXX 树;在元素个数大于 6 时,还是用红黑树,只不过是修剪了下枝叶;
不符合要求的元素(即 hXXX 树)也是一样的操作,只不过最后它是放在了修剪范围外 tab[index + bit]。
总结
JDK 1.8 以后哈希表的 添加、删除、查找、扩容方法都增加了一种节点为 TreeNode 的情况:
- 添加时,当桶中链表个数超过 8 时会转换成红黑树;
- 删除、扩容时,如果桶中结构为红黑树,并且树中元素个数太少的话,会进行修剪或者直接还原成链表结构;
- 查找时即使哈希函数不优,大量元素集中在一个桶中,由于有红黑树结构,性能也不会差。