盒子
盒子
文章目录
  1. 参考
  2. 说明
  3. 介绍
    1. 散列函数
      1. HashMap 的 hash 函数
      2. hash 函数的其他实现方式
    2. 散列冲突
      1. 解决哈希冲突的其他方法
    3. 红黑树
  4. 成员常量
  5. 实际存储数据
  6. put()
  7. get()
  8. rehash
  9. JDK1.8的HashMap为什么是链表长度大于 8 之后转为红黑树?

HashMap

参考

红黑树

HashMap –讲解的很棒

说明

线程不安全

线程安全用 Hashtable

与 Hashtable 的主要区别是 HashMap 不支持同步以及允许 null 作为键或值.

对比 ConcurrentHashMap 与 Collections.synchronizedMap()…

介绍

按自己思路大概讲一下.

HashMap 是面向查找的存储结构,避免了其余存储结构查找时的”比较“步骤(比如遍历线性表,会从头到尾一个一个地比较元素是否是想要查询的元素).

  • 构造方法
  • 碰撞处理

通过键值来匹配元素,一个键对应一个值,所以就能达到类似数组的查找效率,一个 index 对应一个值,然后用近似 O(1) 的效率就能查找到某个元素.

散列函数

用到了一个方法(散列函数),对应每一个 key,生成一个唯一的 hash 值,这个值对应这个 key 的存储地址.想象一下,查找时,通过 key 获得存储地址,然后直接通过地址获得存储的元素对象,效率应该是比较高的.

HashMap 的 hash 函数

1
2
3
4
5
6
7
8
static final int hash(Object key) {
int h;
//h >>> 16 表示对 h 无符号右移 16 位,高位补 0,然后 h 与h >>> 16 按位异或
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

hash 函数的其他实现方式

数字分析法,平方取中法,分段叠加法, 除留余数法, 伪随机数法…

散列冲突

有可能多个 key 生成的 hash 值是一样的,那么就涉及到了碰撞处理.

在 HashMap 中,用拉链法 (链地址法)处理碰撞问题.

原理把具有相同 hash 值的各个元素,用一个链表维护.

HashMap 用链表数组实现,每个列表称为桶(bucket),(HashMap 里用 Entry 来维护)对元素进行相关操作时,先计算对象的散列码,然后与桶的总数取余,所得到的结果就是保存这个元素的索引.

比如进行元素插入操作时,通过计算找到了这个桶,然后发现在这个桶里已经有元素了,那么新插入的元素首先先与已经存在的元素作比较,查看是否存在相同的键值对,若存在就替换之(Map 不允许存储重复的 key),若不存在就插入到链表尾部.

因为有了链表,如果有多个 key 对应了相同的 hash 值,那么查找效率就变成了 O(n+a),a 是一个常数,就是链表的大小.

不过 jdk 1.8 在 HashMap 引入了红黑树,当链表长度大于 8 时,就把链表转化为红黑树.(在源码中体现为一个常量 static final int TREEIFY_THRESHOLD = 8 )

红黑树的理解查看二叉搜索树,2-3 搜索树…

可以想象,只有当元素非常多的时候,才会触发这个转换操作.但是也并非元素多了,就必定会触发这样的操作.

看源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 默认装填因子0.75,如果当前键值对个数 >= HashMap最大容量*装填因子,进行rehash操作
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* JDK1.8 新加,Entry链表最大长度,当桶中节点数目大于该长度时,将链表转成红黑树存储;
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* JDK1.8 新加,当桶中节点数小于该长度,将红黑树转为链表存储;
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 桶可能被转化为树形结构的最小容量.当哈希表的大小超过这个阈值,才会把链式结构转化成树型结构,否则仅采取
* 扩容来尝试减少冲突.
* 应该至少4*TREEIFY_THRESHOLD来避免扩容和树形结构化之间的冲突.
*/
static final int MIN_TREEIFY_CAPACITY = 64;

定义了 MIN_TREEIFY_CAPACITY 保证 当哈希表的大小超过这个阈值,才会把链式结构转化成树型结构,否则仅采取扩容来尝试减少冲突.

装填因子 DEFAULT_LOAD_FACTOR 决定何时对散列表进行扩容,默认 0.75 表示表中超过 75% 的位置已经填入元素,这个表就会以双倍的桶数自动地进行再散列.

解决哈希冲突的其他方法

拉链法

开放定址法 -> 冲突,查找下个内存单元

再散列 -> 重新散列直到不冲突

建立一个公共溢出区

红黑树

红黑树是什么呢?

红黑树是为了解决二叉排序树插入,删除导致的不平衡而产生的.

红黑树仍然是一个二叉搜索树.

二叉排序树的查询效率是O(log n),如果大量删除,二叉排序树就有可能变为一个单叶的树,此时查询效率就成了O(n).

而红黑树给某些节点分配了红黑两种颜色,每次插入,删除,都会进行一定的变换,维持红黑树的性质,重新上色.(变色,旋转…)使得 n 个节点,始终保持 log n 的高度,让查询效率保持在 O(log n).

1
2
3
4
public class HashMap<K, V> extends AbstractMap<K, V>
implements Map<K, V>, Cloneable, Serializable {

}

实现 Map 接口.

成员常量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* 默认的初始容量(容量为HashMap中槽的数目)是16,且实际容量必须是2的整数次幂.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 --为什么不直接写 16?

/**
* 最大容量(必须是2的幂且小于2的30次方,传入容量过大将被这个值替换)
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* 默认装填因子0.75,如果当前键值对个数 >= HashMap最大容量*装填因子,进行rehash操作
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* JDK1.8 新加,Entry链表最大长度,当桶中节点数目大于该长度时,将链表转成红黑树存储;
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* JDK1.8 新加,当桶中节点数小于该长度,将红黑树转为链表存储;
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**
* 桶可能被转化为树形结构的最小容量.当哈希表的大小超过这个阈值,才会把链式结构转化成树型结构,否则仅采取扩容来尝试减少冲突.
* 应该至少4*TREEIFY_THRESHOLD来避免扩容和树形结构化之间的冲突.
*/
static final int MIN_TREEIFY_CAPACITY = 64;

实际存储数据

HashMap 维护了一个内部类.

1
2
3
4
5
6
7
8
9
10
static class Node<K, V> implements Map.Entry<K, V> {
// hash存储key的hashCode
final int hash;
// final:一个键值对的key不可改变
final K key;
V value;
//指向下个节点的引用
Node<K, V> next;
...
}

这个类就是 HashMap 维护的节点(一个链表),准确来说是刚开始维护的节点,因为在一定情况下,该节点会由红黑树来维护.

它实现 Map 接口中的一个内部接口 Map.Entry.

put()

1
2
3
4
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
}

hash : key 计算得到的 hash 值.

key : 键.

value : 值.

onlyIfAbsent : key 在 map 中是否已经存在

evict :

  1. 首先,对 key 计算出 hash 值.
  2. 然后判断,哈希表如果为空,创建一个哈希表,并用一个变量记录哈希表长度.
  3. 如果指定参数 hash 在表中没有对应的桶,说明未产生碰撞,直接将键值对插入 map.
  4. 如果桶已经存在元素,首先判断桶是否为红黑树结构,若是,按照红黑树结构插入键值对,如果是链表结构,就按照链表结构插入.
  5. 如果是链表结构,对链表从头到尾进行遍历,如果发现存在 key 相同的节点(通过 hash 判断),记录这个节点,跳出遍历.
  6. 如果参数 onlyIfAbsent 为 false,或者 oldValue 为 null,替换 value,否则不替换.
  7. 如果没发现的话,将键值对插入链表尾,size 相应 ++.如果链表长度达到阀值,将链表转换为红黑树维护.

get()

1
2
3
4
5
public V get(Object key) {
Node<K, V> e;
//根据key及其hash值查询node节点,如果存在,则返回该节点的value值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

用 hash() 计算出 key 的 hashCode,然后调用 getNode() 获取桶,然后在桶里去获取元素.

在 getNode() 中,通过判断 key 和 hashCode,如果桶的第一个元素就匹配上了,那么直接返回该节点,如果没匹配上,就要对桶进行遍历.

如果桶是红黑树,那就用红黑树的查找方式.

如果桶是链表,就遍历链表…

没找到就返回 null.

rehash

1
2
3
4
/**
* 默认装填因子0.75,如果当前键值对个数 >= HashMap最大容量*装填因子,进行rehash操作
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

也就是说当键值对个数达到负载因子对应的个数,HashMap 就需要进行扩容 resize(),扩容后需要把原有的键值对放到新的 HashMap 中,这便是 rehash.

rehash 是发生在 resize() 中的一个过程.

而 resize() 是发生在 put() 操作中的.

在 put() 时判断 HashMap 的容量是否达到负载因子的要求,达到了就进行 resize(),resize() 的过程中进行 rehash.

JDK1.8的HashMap为什么是链表长度大于 8 之后转为红黑树?

一个思路 :

只有长度N >= 7的时候,红黑树的平均查找长度 lgN 才会小于链表的平均查找长度 N/2,这个可以画函数图来确定,lgN 与 N/2 的交点处 N 约为6.64.

为什么设置为 8 而不是 7 呢?一个原因是为了防止出现频繁的链表与树的转换,当大于8的时候链表转红黑树,小于6的时候红黑树转链表,中间这段作为缓冲.