HashMap 知识点

HashMap的一些特性

  • HashMap可以接受null键和null值,而Hashtable则不能
  • HashMap是非synchronized
  • HashMap速度快,效率高
  • 数组 + 链表 + 红黑树(JDK1.8增加了红黑树部分)
  • Java8里面用node<key,value>实现 Map.Entry接口

hashing的概念

对于 HashMap 及其子类而言,它们采用 Hash 算法来决定集合中元素的存储位置。当系统开始初始化 HashMap 时,系统会创建一个长度为 capacity 的 Entry 数组,这个数组里可以存储元素的位置被称为“桶(bucket)”,每个 bucket 都有其指定索引,系统可以根据其索引(hashcode)快速访问该 bucket 里存储的元素(Map.Entry(即键和值))。

HashMap存储结构

HashMap 的每个“桶”只存储一个元素(也就是一个 Entry,包含有键值对的Map.Entry对象)。由于 Entry 对象可以包含一个引用变量(就是 Entry 构造器的的最后一个参数)用于指向下一个 Entry,因此可能出现的情况是:HashMap 的 bucket 中只有一个 Entry,但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。

demo:

1
2
3
4
5
6
public static void main(String[] args) {
HashMap map = new HashMap();
map.put("key1","value1");
String value = (String)map.get("key1");
System.out.println(value);
}

计算hashcode

1
2
3
4
5
6
static final int hash(Object key) {
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

过程:

  1. 求key的hashCode值
  2. 高位运算
  3. 取模运算

把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。
在JDK1.8的实现中,优化了高位运算的算法,通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。

String.java里面的方法(因为这儿的key是字符串类型):

1
2
3
4
5
6
7
8
9
10
11
12
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;

for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}

上面的 value: char[] (java.lang.invoke.MethodHandleImpl.MAX_ARITY)

{‘j’,’a’,’m’,’v’,’a’,’.’,’l’,’a’,’n’,’g’,’.’,…,’Y’}

HashMap中解决碰撞的方法

拉链法

equals()和hashCode()的应用,以及它们在HashMap中的重要性

get()方法:对象的hashCode()(通过键获取)相同,则它们的bucket位置相同,碰撞’会发生。
“拉链法”解决碰撞,从存储结构可以看出。然后会调用keys.equals()方法遍历链表找到正确的节点,最终找到要找的值对象。

不可变对象的好处

String、Integer等wrapper类(包装类),适合作为键。因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。

负载因子(loadFactor) 和 初始化容量INITIAL_CAPACITY

默认的负载因子大小为0.75f,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。

INITIAL_CAPACITY 默认值为 1<<4 (16) 必须是2的幂

HashMap多线程的条件竞争

首先要知道HashMap是线程不安全的。当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。

通过键获取值

当程序通过 key 取出对应 value 时,系统只要先计算出该 key 的 hashCode() 返回值,在根据该 hashCode 返回值找出该 key 在 table 数组中的索引,然后取出该索引处的 Entry,最后返回该 key 对应的 value 即可。

重新调整HashMap的大小

关于resize()

  • jdk1.8
    resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。
  • JDK1.7
    使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置;这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话),发生倒置,但是JDK1.8不会倒置。

HashMap在Java8中的一点改进

  • 从结构实现来讲,HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现

哪里用到了红黑树?
当链表长度大于8时自动转为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。

  • 增加了Node类

Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对)。上面的图片的每一个圈表示一个Node。

Node<K,V>类源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static class Node<K,V> implements Map.Entry<K,V> {

final int hash;//用来定位数组索引位置
final K key;
V value;
Node<K,V> next; //链表的下一个node
Node(int hash, K key, V value, Node<K,V> next) { ... }
public final K getKey(){ ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
```

### 几个字段:
```
int threshold; // 所能容纳的key-value对极限
final float loadFactor; // 负载因子,默认0.75f
int initialCapacity; // table数组长度,默认为16
int size; // key-value实际对数
int modCount; // 用来记录HashMap内部结构发生变化的次数,主要用于迭代的快速失败。强调一点,内部结构发生变化指的是结构发生变化,例如put新键值对,但是某个key对应的value值被覆盖不属于结构变化。

threshold = loadFactor*initialCapacity;
也就是说,在数组定义好长度之后,负载因子越大,所能容纳的键值对个数越多。当超过threshold时,就重新resize(扩容),扩容后的HashMap容量是之前容量的两倍。如果内存空间很多而又对时间效率要求很高,可以降低负载因子LoadFactor的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子loadFactor的值,这个值可以大于1。

initialCapacity

在HashMap中,哈希桶数组table的长度length大小必须为2的n次方(一定是合数),这是一种非常规的设计,常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数。Hashtable初始化桶大小为11,就是桶大小设计为素数的应用(Hashtable扩容后不能保证还是素数)。HashMap采用这种非常规设计,主要是为了在取模和扩容时做优化,同时为了减少冲突,HashMap定位哈希桶索引位置时,也加入了高位参与运算的过程。

put方法的源码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public V put(K key, V value) {
// 对key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步骤①:tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤②:计算index,并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步骤③:节点key存在,直接覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤④:判断该链为红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步骤⑤:该链为链表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key,value,null);
//链表长度大于8转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已经存在直接覆盖value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) break;
p = e;
}
}

if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}

++modCount;
// 步骤⑥:超过最大容量 就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}