[数据结构与算法]重温数据结构经典：HashMap原理

昨天难得没那么多扯淡的会议，有时间好好重温一下数据结构的知识，在此跟大家一起重温一下数据结构经典：hashCode及HashMap原理

一、HashCode为什么使用31作为乘数

1、选择数字31是因为它是一个奇质数，如果选择一个偶数会在乘法运算中产生溢出，导致数值信息丢失，因为乘二相当于移位运算。选择质数的优势并不是特别的明显，但这是一个传统。

2、数字31有一个很好的特性，即乘法运算可以被移位和减法运算取代，来获取更好的性能：31 * i == (i << 5) - i，现代的 Java 虚拟机可以自动地完成这个优化。

二、数组与链表的特点

数组的特点是：寻址容易，插入和删除困难

链表的特点是：寻址困难，插入和删除容易

三、HashMap原理

• 允许null健及null值，null健，值为0
• HashMap 不保证键值对的顺序，操作时，键值对的顺序会发生变化
• HashMap是非线程安全类，在多线程环境下会发生问题
• HashMap是JDK 1.2时推出的，底层基于散列算法实现
• 在JDK 1.8中涉及比较多：1、散列表实现、2、扰动函数、3、初始化容量、4、负载因子、5、扩容元素拆分、6、链表树化、7、红黑树、8、插入、9、查找、10、删除、11、遍历、12、分段锁等

(1) 扰动函数

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

• 扰动函数就是为了增加随机性，让数据元素更加均衡地散列，减少碰撞。

(2) 负载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

负载因子，可以理解成一辆车可承重重量超过某个阀值时，把货放到新的车上。在 HashMap 中，负载因子决定了数据量多少了以后进行扩容

0.75 是一个默认构造值，在创建 HashMap 也可以调整，如何希望用更多的空间换取时间，可以把负载因子调得更小一些，减少碰撞。

(3) 扩容元素拆分

扩容最直接的问题，就是需要把元素拆分到新的数组中，在JDK1.7中，会重新计算哈希值，但在JDK1.8后，进行了优化，

1. 扩容时计算出新的newCap、newThr，这是两个单词的缩写，一个是Capacity ，另一个是阀Threshold
2. newCap用于创新的数组桶 new Node[newCap];
3. 随着扩容后，原来那些因为哈希碰撞，存放成链表和红黑树的元素，都需要进行拆分存放到新的位置中

(4) 数据迁移

(5) 数据插入

1. 首先进行哈希值的扰动，获取一个新的哈希值。(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
2. 判断tab是否为空或者长度为0，如果是则进行扩容操作。
3. if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;
4. 根据哈希值计算下标，如果对应小标正好没有存放数据，则直接插入即可否则需要覆盖。tab[i = (n - 1) & hash])
5. 判断tab[i]是否为树节点，否则向链表中插入数据，否则向树中插入节点。
6. 如果链表中插入节点的时候，链表长度大于等于8，则需要把链表转换为红黑树。treeifyBin(tab, hash);
7. 最后所有元素处理完成后，判断是否超过阈值；threshold，超过则扩容。
8. treeifyBin,是一个链表转树的方法，但不是所有的链表长度为8后都会转成树，还需要判断存放key值的数组桶长度是否小于64 MIN_TREEIFY_CAPACITY。如果小于则需要扩容，扩容后链表上的数据会被拆分散列的相应的桶节点上，也就把链表长度缩短了。

(6) 链表树化

1. 链表树化的条件有两点；链表长度大于等于8、桶容量大于64，否则只是扩容，不会树化。
2. 链表树化的过程中是先由链表转换为树节点，此时的树可能不是一颗平衡树。同时在树转换过程中会记录链表的顺序，tl.next = p，这主要方便后续树转链表和拆分更方便。
3. 链表转换成树完成后，再进行红黑树的转换。先简单介绍下，红黑树的转换需要染色和旋转，以及比对大小。在比较元素的大小中，有一个比较有意思的方法，tieBreakOrder加时赛，这主要是因为HashMap没有像TreeMap那样本身就有Comparator的实现。

(7) 红黑树转链

在转换树的过程中，记录了原有链表的顺序，红黑树转链表时候，直接把TreeNode转换为Node，因为记录了链表关系，所以替换过程很容易。

(8) 查找

1. 扰动函数的使用，获取新的哈希值
2. 下标的计算， tab[(n - 1) & hash])
3. 确定了桶数组下标位置，接下来就是对红黑树和链表进行查找和遍历操作了

(9) 删除

• 删除的操作也比较简单，没有太多的复杂的逻辑。
• 另外红黑树的操作因为被包装了，只看使用上也是很容易。

(10) 遍历

1. 这里我们要设定一个既有红黑树又有链表结构的数据场景
2. 为了可以有这样的数据结构，我们最好把 HashMap 初始长度设定为 64，避免在

链表超过 8 位后扩容，而是直接让其转换为红黑树。

3. 找到 18 个元素，分别放在不同节点(这些数据通过程序计算得来)；
4. 桶数组 02 节点：24、46、68
5. 桶数组 07 节点：29
6. 桶数组 12 节点：150、172、194、271、293、370、392、491、590

测试代码

public void test_Iterator() {
    Map<String, String> map = new HashMap<String, String>(64);
    map.put("24", "Idx：2");
    map.put("46", "Idx：2");
    map.put("68", "Idx：2");
    map.put("29", "Idx：7");
    map.put("150", "Idx：12");
    map.put("172", "Idx：12");
    map.put("194", "Idx：12");
    map.put("271", "Idx：12");
    System.out.println("排序01：");
    for (String key : map.keySet()) {
        System.out.print(key + " ");
    }

    map.put("293", "Idx：12");
    map.put("370", "Idx：12");
    map.put("392", "Idx：12");
    map.put("491", "Idx：12");
    map.put("590", "Idx：12");
    System.out.println("\n\n排序02：");
    for (String key : map.keySet()) {
        System.out.print(key + " ");
    }    

    map.remove("293");
    map.remove("370");
    map.remove("392");
    map.remove("491");
    map.remove("590");
    System.out.println("\n\n排序03：");
    for (String key : map.keySet()) {
        System.out.print(key + " ");
    }

}

1. 添加元素，在 HashMap 还是只链表结构时，输出测试结果 01
2. 添加元素，在 HashMap 转换为红黑树的时候，输出测试结果 02
3. 删除元素，在 HashMap 转换为链表结构时，输出测试结果 03

结果如下：

排序01：
24 46 68 29 150 172 194 271 

排序02：
24 46 68 29 271 150 172 194 293 370 392 491 590 

排序03：
24 46 68 29 172 271 150 194 
Process finished with exit code 0

• 这一篇 API 源码以及逻辑与上一篇数据结构中扰动函数、负载因子、散列表实现等，内容的结合，算是把 HashMap 基本常用技术点，梳理完成了。但知识绝不止于此，这里还有红黑树的相关技术内容，后续会进行详细。

• 除了 HashMap 以外还有 TreeMap、ConcurrentHashMap 等，每一个核心类都有一与之相关的核心知识点，每一个都非常值得深入研究。这个烧脑的过程，是学习获得的知识的最佳方式。

• 可能关于 HashMap 还有一些疏漏的点，也希望阅读的小伙伴可以提出更多的问题，互相学习，共同进步，本文就到这里，感谢您的阅读！