Java HashMap 与 HashSet

Java

基于Hash的集合

代码版本jdk1.8.0_101

HashMap顾名思义就是利用哈希机制构建的Map
应该是Java最常用的Map结构

底层存储结构

HashMap的基础结构是Node数组，Node是Entry的子类，一个node表示一条数据
数组容量必须是2的幂次，默认初始容量16， 最大容量2的30次幂

HashMap.java
1
transient Node<K,V>[] table;

由数据映射到底层

每当新加入一条数据，需要决定数据的存放位置

  1. 首先，对key求哈希值，将hash作为存放位置的依据
HashMap.java
1
2
3
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
  1. hash的范围是整个int空间，还需要将hash映射到当前的数组大小
    由于整数n的大小始终为2的幂次，那么n-1的二进制表示为末尾全1的形式，相当于一个掩码，把hash值截断，相当于取模运算，比%效率更高
HashMap.java
1
tab[i = (n - 1) & hash]
  1. 截断的hash值损失了高位信息，因此采用了一种弥补方式。计算哈希时并没有直接采用key的hashCode,而是与高16位进行异或的结果作为hash值
    对null值key进行特殊处理,哈希值为0
HashMap.java
1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

哈希冲突解决

Hash表冲突有两大解决方案

  • Open addressing:一个位置由一条数据独占，如果发现目标位置被占用，就按规则选其他位置
  • Separate chaining:一个位置被多个数据共享，这些数据链接起来存储
    Java的HashMap冲突解决策略采用后者。
    • Java7中，所有冲突都用链表解决。哈希全部冲突的极端情况下，退化成链表，查询效率变成O(n)。
    • Java8中，采用两种方案。如果同一位置的数据比较少，线性查找尚可接受，那么直接链表存储，如果比较多(默认是超过8)则转化成一颗红黑树来优化查询效率。这种转化是双向的，如果删除数据，那么树可能重新退化成链表。 因为采用了双结构，因而实现上有两种形式的Node,一种为普通的链表Node,除了包含hash,key,value这三个基础元素，还包括next引用。另一种为树节点TreeNode,它在Node基础上增加了parent,left,right,prev引用以及红黑树用到的颜色信息。进行树化操作可以缓解哈希碰撞攻击，故意构造哈希值一样的数据会使得链表形式性能大幅下降。
HashMap.java
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
public V put(K key, V value) {
    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;
    if ((tab = table) == null || (n = tab.length) == 0)
        //还没有数据，执行resize分配空间
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        //槽位是空的，直接创建新节点插入
        tab[i] = newNode(hash, key, value, null);
    else {
        //槽位已有数据
        Node<K,V> e; K k;
        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);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //链表过长转为树结构
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    //key已存在，跳出
                    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)
        //超过threshold，进行扩容
        resize();
    //钩子函数，供子类实现
    afterNodeInsertion(evict);
    return null;
}

转树结构策略

  • 如果容量超过64，启用树管理，否则直接扩容来缩减链表长度
  • 如果链表长度超过8，变成树，如果树少于6个节点，变成链表
1
2
3
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

数据检索

  1. 由key的hash值定位到底层Node数组
  2. 判断当前Node数组上节点是否命中
  3. 不是的话继续查找，根据Node类型进行链表查找或树查找

判断命中有两层条件，首要条件是hash值相等，hash值判定了大致范围，进而精确判断同一key或key相等
这就是为什么自定义对象用作key时要重写hashcode和equals方法

HashMap.java
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
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        //槽位有数据
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            //先检查槽位上数据是否命中
            return first;
        if ((e = first.next) != null) {
            //槽位数据是桶，还有其他数据
            if (first instanceof TreeNode)
                //树查找
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                //链表循环查找
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

扩容

初始时HashMap容量为0，无参构造并不会先进行存储分配,因此只要不插入数据就没有数据存储空间

HashMap.java
1
2
3
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

用户设置的初始容量值可能不是2的幂次，会根据容量计算出一个下次扩容的threshold值，他是可以满足需求的最小的2的幂次值。之所以要求2的幂次是有利于扩容、取模等操作。即使指定容量，也不会立刻分配存储，而是仅仅用于设置threshold

HashMap.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
    //...
    this.loadFactor = loadFactor;
    //初始容量只是作为一个参考值，用来计算阈值
    this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

put和putAll操作会导致容量扩充,扩容的标准是判断是否超过threshold
扩容的基本标准是倍增，新阈值threshold的基本标准是容量和loadFactor的乘积。默认的loadFactor为0.75。可见并不是满了才扩容，而是快满了就会扩容。0.75是空间和查询时间的tradeoff。如果很满，说明大概率哈希冲突，可能同一位置数据过多，从而降低查询效率

  • Java6中扩容阈值始终采用因子乘积
  • Java7后第一次扩容阈值采用初始容量，之后采用因子乘积

由于底层容量改变，计算存储位置时会发生变化，因此扩容之后需要对数据进行重新hash。

  • Java7全量重哈希+头插入
    扩容采用全部重新hash的方式，并且采用头部插入，考虑到新插入数据能较快命中。扩容时遍历链表依次重新哈希，每个节点头插入新位置，效果是进行了逆序，并发访问可能造成环死循环。如果HashMap被用到高并发环境下，同时扩容，可能出现链表环，从而get时死循环。Java7扩容后同一位置数据顺序可能更改。
  • Java8链表分离+尾插入
    优化了扩容，无需全体调整位置。由于是倍增方式扩容，相当于掩码增加了一位，相当于在高位多了0或1。因此只有两种情况，要么保持不动，要么移动到新增容量的同一位置。而且java8尾插入，保持相对顺序，扩容之前和之后Node链表内数据顺序保持不变
    建立两个链表loHead和hiHead分别表示低位和高位，将原链表按照高位值不同划分到两个子链表，loHead保持原链表位置，hiHead挂到新增区域的对应位置
HashMap.java
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;

    if (oldCap > 0) {
        //数组分配过
        if (oldCap >= MAXIMUM_CAPACITY) {
            //旧容量已超过最大值2的30次方，threshold直接置为整数最大值
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            //二倍扩充threshold
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0)
        //没分配过存储，初始设过threshold，因为已经调整为2的幂次，因此新容量就是threshold
        newCap = oldThr;
    else {
        //没分配过存储，全部采用默认，容量16，负载因子0.75
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;

    //分配新空间
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    //槽位是单一数据节点，直接迁到新位置
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    //槽位是树结构
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    //槽位是链表结构
                    //保持数据相对顺序，根据容量对应二进制位不同分出两个高低两个链表
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //旧容量位10..0形式，最高位1相当于新容量新增的掩码位
                        if ((e.hash & oldCap) == 0) {
                            //0接入低链表
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            //1接入高链表
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);

                    //低链表扩容后位置不变
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //高链表扩容后位置移动，新旧位置对称，直接加上旧容量间隔就是
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

遍历

Map可以按照三种方式遍历：keySet,values,entrySet
这三个对象都是无状态的，不存储任何信息，遍历直接遍历底层Node数组
值得注意的是modCount变量，它记录了HashMap变动数，每次操作都会增加，可以作为fail-fast机制的标志变量
一旦在遍历前后modCount发生变化，直接抛异常

HashMap.java
1
2
3
4
5
6
7
8
9
if (size > 0 && (tab = table) != null) {
    int mc = modCount;
    for (int i = 0; i < tab.length; ++i) {
        for (Node<K,V> e = tab[i]; e != null; e = e.next)
            action.accept(e);
    }
    if (modCount != mc)
        throw new ConcurrentModificationException();
}

使用技巧

  • 建HashMap时传入初始容量参数，因为扩容代价很大，如果有预期容量上限设为目标容量/负载因子+1能避免扩容
  • 不能再并发环境下使用，否则可能会产生环链表死循环或者数据覆盖丢失

HashSet

有了HashMap之后，HashSet的实现变得极其简单
HashSet和HashMap的区别是没有Key-Value结构

HashSet.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
}

实际上内部就是个HashMap,Map所有的value都存成一个用于占位的同一Object
另外map的put和remove返回旧值，使用占位的Object而不是null可以用于区分原来是否存在

版权声明

This site by Linest is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由Linest创作并维护的博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文永久链接：http://linest.github.io/2017/10/20/java-hashmap/