HashMap 学习总结

关注
发布于: 2020 年 07 月 14 日
首先列出几个定义：
Hash表
Hash表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“散列表”
Hash表用的是数组支持按照下标随机访问数据的特性，所以Hash表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有Hash表。
﻿
Hash函数
散列函数，顾名思义，它是一个函数。我们可以把它定义成 hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。
三点散列函数设计的基本要求：
散列函数计算得到的散列值是一个非负整数；
如果 key1 = key2，那 hash(key1) == hash(key2)；（也就是说：equals 相等，hashCode 一定要相等。）
重写了 hashCode 也要重写 equals。
关于第2、3点的说明，极客时间的每日一课上有个教程讲的比较好：
https://time.geekbang.org/dailylesson/detail/100028428
﻿
HashMap定义
根据Key值直接进行访问的数据结构。通过把Key值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做Hash函数，存放记录的数组就叫做Hash表。
﻿
把map里的key，计算hash后，放置到数组里。所放数组的下标是根据特定的算法，例如除以数组length然后取模。如果hashcode相同，那么按照链表的方式进行存储。更准确的说，数组里存放的并不是key值，而是key值所在的地址引用。
在Java的HashMap实现里，具体键值对在哈希表中的位置（数组 index）取决于下面的位运算：
i = (n - 1) & hash
﻿
装载因子
HashMap的装载因子 = 填入表中的元素个数 / 散列表的长度
在Java的HashMap实现里：装载因子叫做load factor，也有翻译成负载系数，初始值是0.75；散列表长度就叫做capacity，初始值是1<<4，也就是16。
装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
装载因子阈值的设置要权衡时间、空间复杂度。如果内存空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值，甚至可以大于 1。
﻿
HashMap的时间复杂度和空间复杂度
结论：
时间复杂度O(1)，最坏情况是O(n)，查询、插入、删除都是
空间复杂度为O(n)
原因：
﻿
对于查询数据：
    散列表的查询效率并不能笼统地说成是 O(1)。它跟散列函数、装载因子、散列冲突等都有关系。如果散列函数设计得不好，或者装载因子过高，都可能导致散列冲突发生的概率升高，查询效率下降。
在极端情况下，有些恶意的攻击者，还有可能通过精心构造的数据，使得所有的数据经过散列函数之后，都散列到同一个槽里。如果我们使用的是基于链表的冲突解决方法，那这个时候，散列表就会退化为链表，查询的时间复杂度就从 O(1) 急剧退化为 O(n)。
    如果散列表中有 10 万个数据，退化后的散列表查询的效率就下降了 10 万倍。更直接点说，如果之前运行 100 次查询只需要 0.1 秒，那现在就需要 1 万秒。这样就有可能因为查询操作消耗大量 CPU 或者线程资源，导致系统无法响应其他请求，从而达到拒绝服务攻击（DoS）的目的。这也就是散列表碰撞攻击的基本原理。
﻿
对于插入数据：
    插入一个数据，最好情况下，不需要扩容，最好时间复杂度是 O(1)。最坏情况下，散列表装载因子过高，启动扩容，我们需要重新申请内存空间，重新计算哈希位置，并且搬移数据，所以时间复杂度是 O(n)。用摊还分析法，均摊情况下，时间复杂度接近最好情况，就是 O(1)。
﻿
Java里的HashMap源代码
首先类关系如下：
代码主要实现逻辑如下：
（图片引用自：Java性能调优实战 ）
﻿
主要说明：
1. Hash值计算逻辑：
static final int hash(Object kye) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>>16;
}
﻿
这是因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的，那么这种处理就可以有效避免类似情况下的哈希碰撞。
﻿
然后通过putVal方法中的(n - 1) & hash决定该Node的存储位置，也就是数组下标
if ((p = tab[i = (n - 1) & hash]) == null)
﻿
2. 存储结构
Java的HashMap实现采用了链地址法来解决Hash冲突的问题。
解决Hash冲突的常用方法有：
开放定址法：
    当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置后面的空位置上去。
    适用场景：当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
﻿
再哈希法（双重散列 Double hashing ）：
    这种方法是同时构造多个不同的哈希函数：Hi=RH1（key）  i=1，2，…，k
    当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
﻿
链地址法：
    这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
    Java的HashMap则是综合考虑了所有因素，采用链地址法解决哈希冲突问题。这种方法是采用了数组（哈希表）+ 链表的数据结构，当发生哈希冲突时，就用一个链表结构存储相同 Hash 值的数据。
    基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。
    于是，在 JDK1.8 版本中，为了对 HashMap 做进一步优化，我们引入了红黑树。而当链表长度太长（默认超过 8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。
﻿
下图中，也可以把Node理解为Map.Entry<k,v>，因为源代码中，Node也是实现了Entry接口：
static class Node<K,V> implements Map.Entry<K,V>
﻿
HashMap的线程安全性？
HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步（1）可以用 Collections的synchronizedMap方法；（2）使用ConcurrentHashMap类，相较于HashTable锁住的是对象整体， ConcurrentHashMap基于lock实现锁分段技术。首先将Map存放的数据分成一段一段的存储方式，然后给每一段数据分配一把锁，当一个线程占用锁访问其中一个段的数据时，其他段的数据也能被其他线程访问。ConcurrentHashMap不仅保证了多线程运行环境下的数据访问安全性，而且性能上有长足的提升。
﻿
LinkedHashMap
LinkedHashMap 也是通过散列表和链表组合在一起实现的。实际上，它不仅支持按照插入顺序遍历数据，还支持按照访问顺序来遍历数据。
LinkedHashMap 是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap 中的“Linked”实际上是指的是双向链表，并非指用链表法解决散列冲突。
（图片引用自：数据结构与算法之美 ）
﻿
﻿
HashMap<Integer, Integer> m = new LinkedHashMap<>();
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);
﻿
for (Map.Entry e : m.entrySet()) {
  System.out.println(e.getKey());
}
上面的代码会按照数据插入的顺序依次来打印，也就是说，打印的顺序就是 3，1，5，2。
它不仅支持按照插入顺序遍历数据，还支持按照访问顺序来遍历数据。你可以看下面这段代码：
﻿
// 10是初始大小，0.75是装载因子，true是表示按照访问时间排序
HashMap<Integer, Integer> m = new LinkedHashMap<>(10, 0.75f, true);
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);
﻿
m.put(3, 26);
m.get(5);
﻿
for (Map.Entry e : m.entrySet()) {
  System.out.println(e.getKey());
}
这段代码打印的结果是 1，2，3，5。
（代码引用自：数据结构与算法之美 ）
﻿