文章
52
标签
19
分类
10
首页
档案
标签
分类
友链
关于
列表
目录
  1. 1. HashMap源码解析
    1. 1.1. 一、HashMap数据结构介绍
    2. 1.2. 二、HashMap的类定义
      1. 1.2.1. 1.HashMap的简单概括
    3. 1.3. 三、HashMap的属性
      1. 1.3.1. 1.HashMap的变动条件
        1. 1.3.1.1. 1.1table扩容
        2. 1.3.1.2. 1.2链表转红黑树
        3. 1.3.1.3. 1.3红黑树退化链表
    4. 1.4. 四、HashMap的构造函数
    5. 1.5. 五、HashMap的核心函数分析
      1. 1.5.1. 1.putVal
      2. 1.5.2. 2.getNode
      3. 1.5.3. 3.resize
        1. 1.5.3.1. 3.1扩容思考
      4. 1.5.4. 4.hash
      5. 1.5.5. 5.tableSizeFor
    6. 1.6. 六、HashMap的内部类
      1. 1.6.1. 1.内部节点类Node
      2. 1.6.2. 2.TreeNode树节点
      3. 1.6.3. 3.KeySet类
      4. 1.6.4. 4.Values
      5. 1.6.5. 5.EntrySet
      6. 1.6.6. 6.KeyIterator、ValueIterator、EntryIterator
      7. 1.6.7. 7.KeySpliterator、ValueSpliterator、EntrySpliterator
HashMap源码解析
|01-Java基础篇03-集合解析
阅读量:

HashMap源码解析

一、HashMap数据结构介绍

  在JDK1.8之前,HashMap采用数组+链表实现,即使用链表处理冲突,同一hash值的key-value都存储在一个链表里.但是当位于一个桶中的元素较多即hash值相等的元素较多时,通过key值依次查找的效率较低.而在JDK1.8中,HashMap采用数组+链表+红黑树实现,但链表长度超过阈值8时,将链表转换为红黑树,这样大大减少了查找时间
  下图代表JDK1.8之前的hashMap结构,左边部分即代表哈希表(也称为哈希数组),数组的每个元素都是单链表的头节点,链表是用来解决冲突的,如果不同的key映射到了数组的同一位置处，就将其放入单链表中
HashMap数据结构.png
  JDK1.8之前的hashmap都采用上图的结构,都是基于一个数组和多个单链表,hash值冲突的时候,就将对应节点以链表的形式存储.如果在一个链表中查找其中一个节点时,将会花费O(n)的查找时间,会有很大的性能损失.到了JDK1.8,当同一个hash值的节点数不小于8时,不再采用单链表形式存储,而是采用红黑树,如下图所示
JDK1.8后hashMap数据结构.png

二、HashMap的类定义

1
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

  可以看到HashMap继承自父类AbstractMap,实现了Map、Cloneable、Serializable接口
  Map接口定义了一组通用操作
  Cloneable接口则表示可以进行拷贝,在HashMap实现的是浅拷贝,即对拷贝对象的改变会影响被拷贝的对象
  Serializable接口表示HashMap实现了序列化,即可以将HashMap对象保存至本地,之后可以恢复状态
  HashMap是基于哈希表的Map接口的实现,此实现提供所有可选的映射操作,并且允许使用null键和null值.此类不保证映射的顺序特别是它不保证该顺序一直不变

1.HashMap的简单概括

  • HashMap中的元素按照hash值分布在不同的桶(bin)中.如果散列特性较好,那么元素分布会比较均匀
  • 单个桶的尺寸过大时,桶的数据结构会由链式转换成一个红黑树,以保证对其操作的时间复杂度为O(logN)
  • key类型推荐实现Comparable,以提高效率
  • KeySet、Values、EntrySet三个视图集合只支持update/remove操作,不支持add
  • 迭代子利用modCount属性来实现乐观锁,来如发生竞态的写操作,则迭代子将直接失效(fast-fail)
  • 尽量直接调用系统函数:Node<K,V>中调用Object的hashCode和Equals
  • 减少不必要的内部函数调用: resize中的transfer(Entry[] newTable)[逻辑优化]和indexFor(hash, table.length)
  • 储存方式:位桶存储;若产生hash碰撞,位桶中按链表存储;若链表达到阀值,链表转换为红黑树
  • 赋值巧妙:if ((p = tab[i = (n - 1) & hash]) == null)判断赋值两不误
  • 通过bool或instance实现代码复用:putMapEntries(Map<? extends K, ? extends V> m, boolean evict)
  • 非同步,若结构改变(add、delete,不包括修改value)必须在外部同步;考虑synchronizedMap–>Map m = Collections.synchronizedMap(new HashMap(…))

三、HashMap的属性

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
/**
 * 默认的初始化容量(必须是2的幂)为16
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * 最大容量
 * - 如果任何具有参数的构造函数隐式指定较高的值则使用该参数
 * - 必须是2的幂,小于2^30
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 当构造函数没有指定时这个加载因子将被使用
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 当桶(bucket)上的节点数大于这个值就会转成红黑树
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 当桶(bucket)上的节点数小于这个值时树转链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 桶中结构转化为红黑树对应的table的最小大小.
 * (否则如果一个bin节点太多,表格大小将会被调整)
 * 至少是TREEIFY_THRESHOLD的4倍一避免table大小调整和树转化的门槛的冲突
 * - 当数组的长度小于64,
 *      但是tab[i]上的节点数已经大于等于8了,它不会先转化为红黑树,而是先扩容
 *   只有数组长度大于64,并且节点数量大于等于8才转化为红黑树结构
 */
static final int MIN_TREEIFY_CAPACITY = 64;

feild
/**
 * 该表初始化为首次使用,并根据需要调整大小
 * - 分配时长度总是2的幂
 * (在某些操作中我们也容忍长度为零,以允许当前不需要的引导机制)
 */
transient Node<K,V>[] table;

/**
 * 存储键值对的数组,保持缓存的entrySet().
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * 存放元素的个数(注意这个不等于table的长度)
 */
transient int size;

/**
 * 每次扩容和更改map结构的计数器
 * - 该字段用于在hashMap的fail-fast进行迭代
 */
transient int modCount;

/**
 * 临界值:当实际大小(容量*加载因子)超过临界值时,会进行扩容
 */
int threshold;

/**
 * hash表的加载因子
 */
final float loadFactor;

1.HashMap的变动条件

1.1table扩容

  • table为null或者table表的长度小于MIN_TREEIFY_CAPACITY(64)
  • 当存储的实际大小超过临界值(容量*加载因子–默认的加载因子为0.75)时

1.2链表转红黑树

table表的长度大于MIN_TREEIFY_CAPACITY(64)并且桶中的单链表长度超过TREEIFY_THRESHOLD(8)时

1.3红黑树退化链表

桶中的红黑树长度小于UNTREEIFY_THRESHOLD(6)时

四、HashMap的构造函数

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
/**
 * 用指定的初始容量和加载因子去构造一个hashMap
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException
 */
public HashMap(int initialCapacity, float loadFactor) {
    // 初始容量不能小于0,否则报错
    if (initialCapacity < 0) {
        throw new IllegalArgumentException("Illegal initial capacity: " +
                initialCapacity);
    }
    // 初始容量不能大于最大值,否则为最大值
    if (initialCapacity > MAXIMUM_CAPACITY) {
        initialCapacity = MAXIMUM_CAPACITY;
    }
    // 加载因子不能小于或等于0,不能为非数字
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
        throw new IllegalArgumentException("Illegal load factor: " +
                loadFactor);
    }
    // 初始化加载因子
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * 使用初始容量和默认加载因子去构造HashMap
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * 使用默认容量16和默认加载因子0.75去构造HashMap
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
 * 使用指定map(容量由此map指定)和默认加载因子0.75构造HashMap
 * @param   m the map whose mappings are to be placed in this map
 * @throws  NullPointerException if the specified map is null
 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    // 将m中的所有元素添加至HashMap中
    putMapEntries(m, false);
}

/**
 * 实现了Map的putAll和构造方法
 * @param m the map
 * @param evict false:初始化构造map;true (传递给方法afterNodeInsertion).
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 判断table是否已经初始化
        if (table == null) {
            // 实际元素个数
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                    (int)ft : MAXIMUM_CAPACITY);
            // 计算得到的t大于阈值,则初始化阈值
            if (t > threshold) {
                threshold = tableSizeFor(t);
            }
        }
        // 已初始化并且m中元素个数大于阈值,进行扩容处理
        else if (s > threshold) {
            resize();
        }
        // 将m中的所有元素添加至处理好的HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

五、HashMap的核心函数分析

1.putVal

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
/**
 * 实现Map中的put和相关方法
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent true表示仅当key不存在的情况才执行put(不修改已存在的值)
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table未初始化或者长度为0;则进行扩容
    if ((tab = table) == null || (n = tab.length) == 0) {
        n = (tab = resize()).length;
    }
    // (n - 1) & hash确定元素存放在哪个桶中
    // 桶为空,新生成节点放入桶中(此时这个节点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null) {
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素
    } else {
        Node<K,V> e; K k;
        // case1:比较桶中的第一个元素(数组中的节点)的hash值相等,key相等
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))) {
            // 将第一个元素赋值给e,用e来记录
            e = p;
        // case2:hash不相等,key不相等,p为红黑树节点
        } else if (p instanceof TreeNode) {
            // 放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // case3:为链表节点
        } 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;
                }
                // 链表中间某个节点的hash值相等,key值与插入元素也相等则跳出循环
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                    break;
                }
                // 用于遍历桶中的链表,与前面的e = p.next组合,可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) { // existing mapping for key
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null) {
                // 用新值替换旧值
                e.value = value;
            }
            // 访问后回调
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 实际大小大于阈值则扩容
    if (++size > threshold) {
        resize();
    }
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

注意:查找位置都分为桶中的第一个节点、是否红黑树节点点、链表由快到慢点,这样效率高,后面再进行对应位置插入、取值

put的逻辑:

  1. 判断键值对数组tab[]是否为空或为null,是则resize
  2. 根据键值key的hashCode()计算hash值得到当前Node的索引i,如果tab[i]==null(没碰撞),直接新建节点添加;如果碰撞转入3
  3. 判断当前数组中处理hash冲突方式为红黑树还是链表(check第一个节点类型即可),分别处理
    1. 是红黑树则按红黑树逻辑插入
    2. 是链表则遍历链表,看是否有key相同的节点
      1. 有则更新value值,没有则新建节点
      2. 此时若链表数量大于阈值8,则调用treeifBin方法(此方法先判断table是否为null或tab.length小于64,是则执行resize操作,否则才将链表改为红黑树)
  4. 如果size+1>threshold则resize

2.getNode

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
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; // table的快照
    Node<K,V> first, e;
    int n; K k;
    // first = tab[(n - 1) & hash]是hash对应桶的第一个元素
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k)))) {
            return first; // 第一个equal就直接返回了
        }
        if ((e = first.next) != null) {
            // 如果是TreeNode就调用TreeNode的get;否则根据next方法进行遍历桶
            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;
}
  1. (n-1) & hash计算bucket的index
  2. 判断第一个节点hash、key是否相等,是则返回first
  3. 若(e=first.next)!=null
    1. 若first为红黑树,getTreeNode返回根节点,并调用其find方法,根据hash值判断进入左/右子树,逐层查找
    2. 若为链表,遍历链表,得到节点值,通过hash和equals(key)确认所查找元素
  4. 没有改元素,返回null

get、containsKey都可以用来判断map中是否存在该元素吗？
  当get()方法的返回值为null时,可能有两种情况:一种是在集合中没有该键对象,另一种是该键对象没有值本就为null.因此在Map集合中不应该利用get()方法来判断是否存在某个元素,而应该利用containsKey()方法来判断

3.resize

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
91
92
93
94
95
96
97
98
99
100
101
102
/**
 * 两倍扩容并初始化table.
 * 由于容量是2的幂次,resize后元素下标--->不变或增加2的幂次
 * @return 节点数组
 */
final Node<K,V>[] resize() {
    // 当前table保存
    Node<K,V>[] oldTab = table;
    // 保存table大小
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 保存当前阈值
    int oldThr = threshold;
    int newCap, newThr = 0;
    // case1:oldCap>0
    if (oldCap > 0) {
        // 之前table大于最大容量:超过上限就不能再扩容了
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 阈值为最大整型
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 容量翻倍(使用左移效率更高)
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY) {
            // 阈值翻倍
            newThr = oldThr << 1; // double threshold
        }
    }
    // case2:oldCap=0,oldThr>0,threshold(新的扩容resize临界值)
    else if (oldThr > 0) { // initial capacity was placed in threshold
        newCap = oldThr; // 新容量=旧阈值(扩容临界值)
    // case3:oldCap=0,oldThr=0,使用缺省值初始化
    // (如使用HashMap()构造函数,之后再插入一个元素会调用resize函数,会进入这一步)
    } else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 新阈值为0,则需要计算新的阈值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr; // 设置新的阈值(一般为容量*加载因子--默认值为0.75)
    @SuppressWarnings({"rawtypes","unchecked"})
    // 初始化新的table
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 新table初始化,将旧的bucket拷贝到新的bucket,分链表和红黑树
    if (oldTab != null) { // 不为空则挨个拷贝,影响效率
        // 复制元素,重新进行hash,移动旧表元素
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 先赋值再判断
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null; // 旧表置null,主动GC
                // case1:只有一个元素的桶,直接扔到新的桶hash对应位置(新桶一定是空的)
                if (e.next == null) {
                    newTab[e.hash & (newCap - 1)] = e;
                // case2:树桶(处理TreeNode分裂)
                } else if (e instanceof TreeNode) {
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // case3:链表桶,逐个遍历处理
                } else { // preserve order
                    Node<K,V> loHead = null, loTail = null; // 原桶的首位指针
                    Node<K,V> hiHead = null, hiTail = null; // 新桶的首位指针
                    Node<K,V> next;
                    // 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割,分成两个不同的链表,完成rehash
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) { // 保持不动,还放在原来的桶
                            if (loTail == null) {
                                loHead = e;
                            } else {
                                loTail.next = e;
                            }
                            loTail = e; // 更新尾指针
                        }
                        else { // 挪到新桶
                            if (hiTail == null) {
                                hiHead = e;
                            } else {
                                hiTail.next = e;
                            }
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 把更新后的两个桶放到表里
                    if (loTail != null) { // 原桶位置的尾指针不为空(即还有node)
                        loTail.next = null; // 链表最后得有个null
                        newTab[j] = loHead; // 链表头指针放在新桶相同下标j处(与旧桶一致)
                    }
                    if (hiTail != null) { // 同理,放在桶 j+oldCap
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
  • 由前面知识可知,table的下标[bucket的index]由(n-1) & hash计算
    n为table的length,hash即hash(key)计算方式如下
  • 假设我们length从16resize到32(以下仅写出8位,实际32位),hash(key)是不变的

& | n-1(原长16)–>0000 1111 | 2n-1(新长32)–>1111 1111 |
| :—: | :—: | :—: |
hash1–>0000 0101 | 0000 0101 | 0000 0101
index1 | hash1高位全0,index不变 | hash1高位全0,index不变|
hash2–>0001 0101 | 0000 0101 | 0001 0101
index2 | 新index=5+16即原index+oldCap | 新index=5+16即原index+oldCap |

  • 新bucket下标:(2n-1) & hash(key),由于是&操作,同1为1;hash(key)是不变的;2n-1在原来n-1基础上仅高位由0变1
  • HashMap在resize时,只需看新n-1高位对应hash(key)位是0还是1即可,0则位置不变,1则位置变为原位置+oldCap
  • 如何确认(新)n-1最高位对应的hash(key)位是0还是1呢?源码给出了很巧妙的方式(e.hash & oldCap): e即Node,由put和Node构造函数相关源码可知,e.hash即为hash(key);
    oldCap为0001 0000

总结:

  1. 无需重新计算hash,节省了时间
  2. 由于所计算的hash(key)位是1是0可以认为是随机的,所以将一个冲突长链表又”均分”成了两个链表,减少碰撞

    说明:进行扩容会伴随着一次重新hash分配,并且会遍历hash表中所有元素,是非常耗时的.在编写程序时要尽量避免resize

在resize前和resize后的元素布局如下图:
resize前后对比图.png
上图只是针对了数组下标为2的桶中的各个元素在扩容后的分配布局,其他各个桶中的元素布局可以以此类推

3.1扩容思考

  从putVal源代码中我们可以知道,当插入一个元素的时候size就加1,若size大于threshold的时候,就会进行扩容.假设我们的capacity大小为32,loadFator为0.75,则threshold为24 = 32 * 0.75,此时插入了25个元素,并且插入的这25个元素都在同一个桶中,桶中的数据结构为红黑树,则还有31个桶是空的,也会进行扩容处理,其实此时还有31个桶是空的,好像似乎不需要进行扩容处理,但是是需要扩容处理的,因为此时我们的capacity大小可能不适当.我们前面知道,扩容处理会遍历所有的元素,时间复杂度很高;前面我们还知道,经过一次扩容处理后,元素会更加均匀的分布在各个桶中,会提升访问效率.所以说尽量避免进行扩容处理,也就意味着,遍历元素所带来的坏处大于元素在桶中均匀分布所带来的好处

4.hash

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

由上可知:
  key是有可能null的,并且会在0桶位的位置
  hashCode的计算也进行了改进,取得key的hashcode后,高16位与低16位异或运算重新计算hash值
  首先由key值通过hash(key)获取hash值h,再通过hash &(length-1)得到所在数组位置:
  一般对于hash表的散列常用方法有直接定址法、除留余数法等,既要便于计算,又能减少冲突
  在Hashtable中就是通过除留余数法散列分布的,具体如下:int index = (hash & 0x7FFFFFFF) % tab.length;但是取模中的除法运算效率很低,HashMap则通过hash &(length-1)替代取模,得到所在数组位置,这样效率会高很多

5.tableSizeFor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 返回不小于cap的最小2幂
 */
static final int tableSizeFor(int cap) {
    // 低位全部用1填充;最后在+1实现2幂次
    int n = cap - 1;
    // >>> 操作符表示无符号右移,高位取0
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // 设置上下限(下限1,上限MAXIMUM_CAPACITY,正常n+1)
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

计算新的扩容临界值threshold,不再是JDK.16的while循环来保证hash表的容量一直是2的整数倍,用移位操作取代了while循环移位(不断乘2).HashMap的构造函数都直接或间接调用了tableSizeFor函数
1.6中

1
int capacity = 1; while (capacity < initialCapacity) capacity <<= 1

其返回值是>=cap的最小2的幂(大于等于1,tableSizeFor(-111)=1)
性能优化:
  length为2的整数幂保证了length - 1 最后一位(二进制表示)为1,从而保证了索引位置index即(hash &length-1)的最后一位同时有为0和为1的可能性,保证了散列的均匀性.反过来讲若length为奇数,length-1最后一位为0,这样与h按位与[同1为1]的最后一位肯定为0,即索引位置肯定是偶数,这样数组的奇数位置全部没有放置元素,浪费了大量空间
  简而言之:length为2的幂保证了按位与最后一位的有效性,使哈希表散列更均匀

六、HashMap的内部类

1.内部节点类Node

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
/**
 * 基于hash的内部节点类
 * - 是存储一对映射关系的最小单元(即key,value实际存储在node中)
 */
static class Node<K,V> implements Map.Entry<K,V> {
    // 节点的hash值,不可变
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    // 由1.6的直接实现变为调用Object的HashCode,实际是一样的
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this) { // 内存地址:1.8新增
            return true;
        }
        if (o instanceof Map.Entry) { //1.6中!(instanceof)返回false
            Map.Entry<?,?> e = (Map.Entry<?,?>)o; //新加<?,?>泛型
            if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue())) {
                return true;
            }
        }
        return false;
    }
}

2.TreeNode树节点

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
/**
 * 树节点. 继承于LinkedHashMap.Entry (进而延伸节点)
 * - 因此可以用作正则节点或链接节点的扩展
 * TreeNode维持为红黑树,保证树的高度为O(logN),并按hashCode有序
 */
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;   // 父节点
    TreeNode<K,V> left;     // 左子节点
    TreeNode<K,V> right;    // 右子节点
    TreeNode<K,V> prev;     // 下一步需要取消删除
boolean red;            // 红黑标志

/**
 * 回溯获取根节点
 */
final TreeNode<K,V> root() {}

/**
 * 静态方法;将根节点移到桶的首元素(即放到tab数组里)
 * - 删除根节点时候可能新的根节点不是首元素
 */
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root){}

/**
 * 通过给定的hash和key从root节点开始查找适合的节点.
 * 参数kc在第一次使用比较键时缓存comparableClassFor(key)的返回值
 */
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {}

/**
 * 辅助方法用来给两个对象指定顺序
 * 用于处理hashCode相同又不是Comparable的情况
 */
static int tieBreakOrder(Object a, Object b) {}

/**
 * 将本节点所属的桶转化为树状结构(调用时该桶应为TreeNode组成的列表)
 * @return root of tree
 */
final void treeify(Node<K,V>[] tab) {}

/**
 * 将树所在桶退化为普通的链表桶
 */
final Node<K,V> untreeify(HashMap<K,V> map) {}

/**
 * TreeNode桶的put实现
 * - 如果k存在,返回对应的旧节点;如果k不存在返回null
 * - 注意此方法不执行value覆盖(由外层根据具体情况判断是否覆盖)
 */
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {}

/**
 * TreeNode桶中删除本节点
 */
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,boolean movable) {}

/**
 * TreeNode桶切分,用于resize
 * - 切分后树过小则退化为链表
 * @param map the map
 * @param tab the table for recording bin heads
 * @param index 待切分的桶下标
 * @param bit 旧hash掩码
 */
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {}

static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,TreeNode<K,V> p) {}

static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,TreeNode<K,V> p) {}

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {}

static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,TreeNode<K,V> x) {}

/**
 * 递归校验指针兼容性和整个树的有序性,容错机制
 */
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {}
}

3.KeySet类

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
/**
 * 内部类:keySet实现,基于HashMap本身的,注意不是全功能的Set
 */
final class KeySet extends AbstractSet<K> {
    // 大部分支持的操作直接调用HashMap对应方法
    public final int size()                 { return size; }
    public final void clear()               { this.clear(); }
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator<K> spliterator() {
        return new KeySpliterator<>(this, 0, -1, 0, 0);
    }

    /**
     * java8新增的Collection方法实现
     * @param action
     */
    public final void forEach(Consumer<? super K> action) {
        Node<K,V>[] tab;
        if (action == null) {
            throw new NullPointerException();
        }
        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.key);
                }
            }
            if (modCount != mc) {
                throw new ConcurrentModificationException();
            }
        }
    }
}

4.Values

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
final class Values extends AbstractCollection<V> {
    public final int size()                 { return size; }
    public final void clear()               { this.clear(); }
    public final Iterator<V> iterator()     { return new ValueIterator(); }
    public final boolean contains(Object o) { return containsValue(o); }
    public final Spliterator<V> spliterator() {
        return new ValueSpliterator<>(this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer<? super V> action) {
        Node<K,V>[] tab;
        if (action == null) {
            throw new NullPointerException();
        }
        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.value);
                }
            }
            if (modCount != mc) {
                throw new ConcurrentModificationException();
            }
        }
    }
}

5.EntrySet

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
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    @Override
    public final int size()                 { return size; }
    @Override
    public final void clear()               { this.clear(); }
    @Override
    public final Iterator<Map.Entry<K,V>> iterator() {
        return new EntryIterator();
    }
    @Override
    public final boolean contains(Object o) {
        if (!(o instanceof Map.Entry)) {
            return false;
        }
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;
        Object key = e.getKey();
        Node<K,V> candidate = getNode(hash(key), key);
        return candidate != null && candidate.equals(e);
    }
    @Override
    public final boolean remove(Object o) {
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Object value = e.getValue();
            return removeNode(hash(key), key, value, true, true) != null;
        }
        return false;
    }
    @Override
    public final Spliterator<Map.Entry<K,V>> spliterator() {
        return new EntrySpliterator<>(this, 0, -1, 0, 0);
    }
    @Override
    public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
        Node<K,V>[] tab;
        if (action == null) {
            throw new NullPointerException();
        }
        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();
            }
        }
    }
}

6.KeyIterator、ValueIterator、EntryIterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
final class KeyIterator extends HashIterator
        implements Iterator<K> {
    @Override
    public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator
        implements Iterator<V> {
    @Override
    public final V next() { return nextNode().value; }
}
final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
    @Override
    public final Map.Entry<K,V> next() { return nextNode(); }
}
  1. 如果是遍历过程中增加或修改数据呢?

  增加或修改数据只能通过Map的put方法实现,在遍历过程中修改数据可以,但如果增加新key就会在下次循环时抛异常,因为在添加新key时modCount也会自增
2. jdk为什么允许通过iterator进行remove操作

  HashMap和keySet的remove方法都可以通过传递key参数删除任意的元素，而iterator只能删除当前元素(current)[movable为false],一旦删除的元素是iterator对象中next所正在引用的,如果没有通过modCount、 expectedModCount的比较实现快速失败抛出异常,下次循环该元素将成为current指向,此时iterator就遍历了一个已移除的过期数据.ConcurrentModificationException是RuntimeException,不要在客户端捕获它.如果发生此异常,说明程序代码的编写有问题,应该仔细检查代码而不是在catch中忽略它
  Iterator自身的remove()方法会自动同步expectedModCount和modCount的值(见上源码).确保遍历可靠的原则是只在一个线程中使用这个集合,或者在多线程中对遍历代码进行同步

7.KeySpliterator、ValueSpliterator、EntrySpliterator

文章作者: Eric Liang
文章链接: https://ericql.github.io/2019/11/12/01-Java%E5%9F%BA%E7%A1%80%E7%AF%87/03-%E9%9B%86%E5%90%88%E7%AF%87/HashMap%E6%BA%90%E7%A0%81%E8%A7%A3%E6%9E%90/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Eric Liang！
集合 HashMap
打赏
  • 微信
  • 支付宝
相关推荐
fail-fast机制
集合工具类
TreeMap源码解析
LinkedList源码解析
ArrayList源码解析
繁