一些收藏

重温数据结构经典：HashMap原理

2022-03-10  本文已影响0人  MobotStone

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

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

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

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

二、数组与链表的特点

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

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

三、HashMap原理

(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. 确定了桶数组下标位置，接下来就是对红黑树和链表进行查找和遍历操作了
image

(9) 删除

(10) 遍历

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

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

  1. 找到 18 个元素，分别放在不同节点(这些数据通过程序计算得来)；
  2. 桶数组 02 节点：24、46、68
  3. 桶数组 07 节点：29
  4. 桶数组 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
上一篇 下一篇

猜你喜欢

热点阅读