0%

HashMap源码分析

发表于 分类于

HashMap源码分析

1、实现原理概括

  • HashMap是一个关联数组、哈希表，它是线程不安全的，允许key为null,value为null。遍历时无序

  • 使用拉链法实现哈希表，结合了数组与链表的特点

    • 数组的特点是空间连续（大小固定）、寻址迅速，但是插入和删除时需要移动元素，所以查询快，增加删除慢
    • 链表可动态增加或减少空间以适应新增和删除元素，但查找时只能顺着一个个节点查找，所以增加删除快，查找慢

  • 其底层数据结构是数组称之为哈希桶，每个桶里面放的是链表，链表中的每个节点，就是哈希表中的每个元素；
    在JDK8中，当链表长度达到8，会转化成红黑树，以提升它的查询、插入效率

    • 哈希桶的底层数据结构是数组（数组中每个元素都是链表），所以就会面临着扩容问题
    • 当容量达到threshold域值时，就会触发扩容。扩容前后，哈希桶的长度一定会是2的次方。
      在根据key的hash值寻找对应的哈希桶时，可以用位运算替代取余操作，更加高效。
    • 扩容时，会new个新的Node数组作为哈希桶，然后将原哈希表中的所有数据(Node节点)移动到新的哈希桶中，
      即对原哈希表中所有的数据重新做了个put操作，所以性能消耗很大；在哈希表的容量越大时，性能消耗越明显。
    • 如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置。
    • 扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位，或者扩容后的下标，即high位。
      high位= low位+原哈希桶容量。

  • 而key的hash值，并不仅仅只是key对象的hashCode()方法的返回值，还会经过扰动函数的扰动，以使hash值更加均衡。

    • 扰动函数就是为了解决hash碰撞的。它会综合hash值高位和低位的特征，并存放在低位，因此在与运算时，
      相当于高低位一起参与了运算，以减少hash碰撞的概率。（在JDK8之前，扰动函数会扰动四次，JDK8简化了这个操作）

2、代码分析

类关系
  • HashMap继承自AbstractMap，实现了Map接口，Map接口定义了所有Map子类必须实现的方法。
  • AbstractMap也实现了Map接口，并且提供了两个实现Entry的内部类：SimpleEntry和SimpleImmutableEntry
1
2
3
4
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    private static final long serialVersionUID = 362498820763181265L;
    //省略....
}
成员变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/** 默认的初始容量，必须是2的幂 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/** 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/** 默认装载因子，默认值为0.75，如果实际元素所占容量占分配容量的75%时就要扩容了 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** 当链表中元素个数超过这个值时，将链表转换为红黑树 */
static final int TREEIFY_THRESHOLD = 8;
/** 树的链表还原阈值，当扩容时，桶中元素个数小于这个值，就会把树形的桶元素还原（切分）为链表结构 */
static final int UNTREEIFY_THRESHOLD = 6;
/** 最小树形化的容量，当哈希表总容量大于该值时，链表才会树形化；避免进行扩容、树形化选择的冲突，不能小于 4 * TREEIFY_THRESHOLD */
static final int MIN_TREEIFY_CAPACITY = 64;
/** 存储数据的Entry数组，长度是2的幂 */
transient Node<K,V>[] table;
/** 缓存entrySet()，用于keySet()和values() */
transient Set<Map.Entry<K,V>> entrySet;
/** map中保存的键值对的数据量 */
transient int size;
/** map结构被改变的次数 */
transient int modCount;
/** 需要调整大小的极限值（容量*装载因子） */
int threshold;
/** 装载因子 */
final float loadFactor;
内部类
  • 链表节点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
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

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

    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)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}
构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/** 根据给定的初始容量和装载因子创建一个空的HashMap */
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
/** 根据给定的初始容量并使用默认的装载因子创建一个空的HashMap */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/** 使用默认的容量及装载因子构造一个空的HashMap */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/** 通过传入的map及默认的装载因子创建一个HashMap */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

这里有个方法 putMapEntries(Map m,boolean evict) 涉及到其中三个重要方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            //重新计算新的阈值
            float ft = ((float)s / loadFactor) + 1.0F;
            //校正阈值不会超过最大值
            int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
            //若新的阈值大于当前阈值
            if (t > threshold)
                //则返回一个满足2的幂次方且大于新阈值的阈值
                threshold = tableSizeFor(t);
        }
        //如果当前数据表不为空 且新的容量大于当前阈值，则必定扩容
        else if (s > threshold)
            resize();
        //遍历新的map将元素依次put到当前表中
        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);
        }
    }
}
  • 重新计算新的阈值tableSizeFor(int cap)：
1
2
3
4
5
6
7
8
9
10
11
static final int tableSizeFor(int cap) {
    //经过下面的 或 和位移 运算， n最终各位都是1
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    //判断n是否越界，返回 2的n次方作为 table 的阈值
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

  • 扩容方法resize()：
    主要步骤：

    • 如果到达最大容量，那么返回当前的桶，并不再进行扩容操作，否则的话扩容为原来的两倍，返回扩容后的桶；
    • 根据扩容后的桶，修改其他的成员变量的属性值；
    • 根据新的容量创建新的扩建后的桶，并更新桶的引用；
    • 如果原来的桶里面有元素就需要进行元素的转移；
    • 在进行元素转移的时候需要考虑到元素碰撞和转红黑树操作；在发生碰撞的时候，将新加入的元素添加到末尾；
    • 在扩容的过程中，按次从原来的桶中取出链表头节点，并对该链表上的所有元素重新计算hash值进行分配；
    • 在元素复制的时候需要同时对低位和高位进行操作。
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
103
104
105
106
final Node<K,V>[] resize() {
    //oldTab 为当前表的哈希桶
    Node<K,V>[] oldTab = table;
    //当前哈希桶的容量 length
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //将当前的阈值缓存下来
    int oldThr = threshold;
    //初始化新的容量和阈值为0
    int newCap, newThr = 0;
    //如果当前容量大于0
    if (oldCap > 0) {
        //如果当前容量已经到达上限
        if (oldCap >= MAXIMUM_CAPACITY) {
            //则设置阈值是2的31次方-1
            threshold = Integer.MAX_VALUE;
            //同时返回当前的哈希桶，不再扩容
            return oldTab;
        }
        //否则新的容量为旧的容量的两倍，如果旧的容量大于等于默认初始容量16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            //新的阈值也等于旧的阈值的两倍
            newThr = oldThr << 1; // double threshold
    }
    //如果当前表是空的，但是有阈值。代表是初始化时指定了容量、阈值的情况
    else if (oldThr > 0) // initial capacity was placed in threshold
        //那么新表的容量就等于旧的阈值
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //如果当前表是空的，而且也没有阈值。代表是初始化时没有任何容量/阈值参数的情况
        newCap = DEFAULT_INITIAL_CAPACITY;
        //新的阈值为 12 = 16 * 0.75
        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;
    @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;
            //如果当前桶中有元素,则将链表赋值给e
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;//将原哈希桶置空以便GC
                //如果当前链表中就一个元素，（没有发生哈希碰撞），直接将这个元素放置在新的哈希桶里
                if (e.next == null)
                    //位运算：是用哈希值 与 桶的长度-1,由于桶的长度是2的n次方，相当于一个模运算。
                    newTab[e.hash & (newCap - 1)] = e;
                //如果发生过哈希碰撞 ,而且是节点数超过8个，转化成了红黑树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置
                else { // preserve order
                    //扩容是容量翻倍后原链表上的每个节点可能在low位(原来的下标)或high位(扩容后的下标)
                    //high位=low位+原哈希桶容量
                    //低位链表的头结点、尾节点
                    Node<K,V> loHead = null, loTail = null;
                    //高位链表的头节点、尾节点
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;//临时节点 存放e的下一个节点
                    do {
                        next = e.next;
                        //位运算：用哈希值与旧的容量相与后判断是否为0，若为0应存放在低位，否则存放在高位
                        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);
                    //将低位链表存放在原index处
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //将高位链表存放在新index处
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
核心方法
tableSizeFor方法
1
2
3
4
5
6
7
8
9
10
11
12
//新的阈值计算
static final int tableSizeFor(int cap) {
    //经过下面的 或 和位移 运算， n最终各位都是1
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    //判断n是否越界，返回 2的n次方作为 table 的阈值
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
resize方法：
  • 如果到达最大容量，那么返回当前的桶，并不再进行扩容操作，否则的话扩容为原来的两倍，返回扩容后的桶；
  • 根据扩容后的桶，修改其他的成员变量的属性值；
  • 根据新的容量创建新的扩建后的桶，并更新桶的引用；
  • 如果原来的桶里面有元素就需要进行元素的转移；
  • 在进行元素转移的时候需要考虑到元素碰撞和转红黑树操作；在发生碰撞的时候，将新加入的元素添加到末尾；
  • 在扩容的过程中，按次从原来的桶中取出链表头节点，并对该链表上的所有元素重新计算hash值进行分配；
  • 在元素复制的时候需要同时对低位和高位进行操作
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
103
104
105
106
final Node<K,V>[] resize() {
    //oldTab 为当前表的哈希桶
    Node<K,V>[] oldTab = table;
    //当前哈希桶的容量 length
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //将当前的阈值缓存下来
    int oldThr = threshold;
    //初始化新的容量和阈值为0
    int newCap, newThr = 0;
    //如果当前容量大于0
    if (oldCap > 0) {
        //如果当前容量已经到达上限
        if (oldCap >= MAXIMUM_CAPACITY) {
            //则设置阈值是2的31次方-1
            threshold = Integer.MAX_VALUE;
            //同时返回当前的哈希桶，不再扩容
            return oldTab;
        }
        //否则新的容量为旧的容量的两倍，如果旧的容量大于等于默认初始容量16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            //新的阈值也等于旧的阈值的两倍
            newThr = oldThr << 1; // double threshold
    }
    //如果当前表是空的，但是有阈值。代表是初始化时指定了容量、阈值的情况
    else if (oldThr > 0) // initial capacity was placed in threshold
        //那么新表的容量就等于旧的阈值
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //如果当前表是空的，而且也没有阈值。代表是初始化时没有任何容量/阈值参数的情况
        newCap = DEFAULT_INITIAL_CAPACITY;
        //新的阈值为 12 = 16 * 0.75
        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;
    @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;
            //如果当前桶中有元素,则将链表赋值给e
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;//将原哈希桶置空以便GC
                //如果当前链表中就一个元素，（没有发生哈希碰撞），直接将这个元素放置在新的哈希桶里
                if (e.next == null)
                    //位运算：是用哈希值 与 桶的长度-1,由于桶的长度是2的n次方，相当于一个模运算。
                    newTab[e.hash & (newCap - 1)] = e;
                //如果发生过哈希碰撞 ,而且是节点数超过8个，转化成了红黑树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置
                else { // preserve order
                    //扩容是容量翻倍后原链表上的每个节点可能在low位(原来的下标)或high位(扩容后的下标)
                    //high位=low位+原哈希桶容量
                    //低位链表的头结点、尾节点
                    Node<K,V> loHead = null, loTail = null;
                    //高位链表的头节点、尾节点
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;//临时节点 存放e的下一个节点
                    do {
                        next = e.next;
                        //位运算：用哈希值与旧的容量相与后判断是否为0，若为0应存放在低位，否则存放在高位
                        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);
                    //将低位链表存放在原index处
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //将高位链表存放在新index处
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
put方法
  • 其内部调用的是putVal方法
    • 需要判断是否出现哈希冲突问题：
    • 其中如果哈希值相等，key也相等，则是覆盖value操作；如果不是覆盖操作，则插入一个普通链表节点；
    • 遍历到尾部，追加新节点到尾部；
    • 在元素添加的过程中需要随时检查是否需要进行转换成红黑树的操作；
1
2
3
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
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 V putVal(int hash, K key, V value, boolean onlyIfAbsent,  boolean evict) {
    //tab存放当前的哈希桶，p用作临时链表节点 
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果当前哈希表是空的，代表是初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//直接扩容并将扩容后的长度赋值给n
    //如果当前index的节点是空的，表示没有发生哈希碰撞。直接构建一个新节点Node，挂载在index处即可
    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;//将当前节点引用赋值给e
        //判断是否为红黑树
        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;
                }
                //如果找到了要覆盖的节点
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //如果e不是null，说明有需要覆盖的节点
        if (e != null) { // existing mapping for key
            V oldValue = e.value;//则覆盖节点值，并返回原oldValue
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);//这是一个空实现的函数，用作LinkedHashMap重写使用
            return oldValue;
        }
    }
    //如果执行到了这里，说明插入了一个新的节点，所以会修改modCount，以及返回null。
    ++modCount;
    if (++size > threshold)//更新size，并判断是否需要扩容
        resize();
    //这是一个空实现的函数，用作LinkedHashMap重写使用
    afterNodeInsertion(evict);
    return null;
}

先调用了hash(int h)方法获取了一个hash值。 “扰动函数”，这个方法的主要作用是防止质量较差的哈希函数带来过多的冲突（碰撞）问题。Java中int值占4个字节，即32位。根据这32位值进行移位、异或运算得到一个值。

1
2
3
4
5
//只做一次16位右位移异或混合：
static int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h=key.hashCode())^(h>>>16);
}

“<<” 左移：右边空出的位上补0，左边的位将从字头挤掉，左移一位其值相当于乘2。

“>>”右移：右边的位被挤掉，右移一位其值相当于除以2。对于左边移出的空位，如果是正数则空位补0，若为负数，可能补0或补1，这取决于所用的计算机系统。

“>>>”无符号右移，右边的位被挤掉，对于左边移出的空位一概补上0。

HashMap 在这块的处理就很巧妙：

  • 取得 hashCode，该方法是native方法，根据内存地址算出来的int值
  • 将取得的哈希值无符号右移16位，高位补0。并与前面第一步获得的hash码进行按位异或^ 运算。

    这样做有什么用呢？

    为了降低哈希码的冲突。hashCode右移16位，正好是32bit的一半，与自己本身做异或操作（相同为0，不同为1）
    混合原始哈希码的高位和低位并且混合后的低位也有高位的部分特征，这样高低位都参与到Hash的计算中，加大低位的随机性。

    其实很多哈希算法，为了使元素分布均匀，都是用的取模运算，用一个值去模上总长度，即 n%hash。但在计算机中 & 的效率比 % 高很多，那么如何将 % 转换为 & 运算呢？在HashMap 中，是用的 (n - 1) & hash 进行运算的，那么这是为什么呢？

  • 当 length = 2n 时，X % length = X & (length - 1)*
  • 长度为2的n次幂时，模运算 % 可以变换为按位与 & 运算
  • 一定要是2n次方，才满足上面的公式，否则就是错误的

key.hashCode()返回一个int类型的散列值。32位带符号的int表值范围从-2147483648到2147483648。只要hash函数松散的话，一般是很难发生碰撞的，但还是不能直接拿来用，需要对数组的长度取模运算(n - 1) & hash得到余数才是索引值

HashMap之所以不能保持元素的顺序有以下几点原因：

  • 插入元素的时候对元素进行哈希处理，不同元素分配到table的不同位置
  • 容量拓展的时候又进行了hash处理
  • 复制原表内容的时候链表被倒置其中，

(n-1)&hash 数组长度-1 和 hash 的与运算就是取模运算，这里减1是为了数组越界的问题

get方法
1
2
3
4
5
public V get(Object key) {
    Node<K,V> e;
    //传入扰动后的哈希值 和 key 找到目标节点Node
    return (e = getNode(hash(key), key)) == null ? null : e.value; 
}

经过扰动的hash后，调用getNode方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//查找，找到返回节点，否则返回null
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //同样采用长度减一后和hash与运算得到数组的索引
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        // 总是会比较第一个，需要同时判断hash和值相同
        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 {
                //比较hash值的同时需要比较key的值是否相同
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}