理解hashMap

V2AS问路

理解hashMap

阅读原文时间：2023年07月08日阅读：1

首先需要理解几个基本概念：

什么是数据结构？(摘自 java数据结构系列——什么是数据结构 (baidu.com))

数据结构是计算机组织、存储数据的方式。简单来说就是，数据按指定的规则进行存储，从而得到一个有固定存储格式的数据集合，就称之为“数据结构”。

为了深层次的了解，其实可以分为两个层面来理解：

1、数据元素的前后之间存在某种关系，这是从逻辑层面来讲的一种逻辑关系。我们可以将其称为数据的逻辑结构。常见的逻辑结构（和其介绍）如下：

线性结构：

特点：数据元素之间存在一对一的线性关系。包括两大类：顺序存储结构和链式存储结构。线性结构常见有：数组、队列、链表和栈。

非线性结构：

概述：线性结构之外的称为非线性结构（不在过多赘述）。非线性机构包括：二维数组、多维数组、广义表、树结构、图结构。

2、某一逻辑结构的数据在内存中存储的方式，我们可以将其称为数据的物理结构（存储结构）。常见的物理结构（和其介绍）如下：

顺序存储：

简介：在内存中开辟出一组地址连续的存储单元，用于存储数据元素。优点：节省空间因为不用额外存储元素间的逻辑关系。查看数据元素快因为每个存储单元对应一个序号，每个序号存储一个数据元素。通过序号可以快速的查找到数据。缺点：插入、删除数据慢因为每次执行此类操作都需要移动元素。

链式存储：

简介：在内存中开辟出一组任意地址的存储单元（地址可以连续，也可以不连续），用于存储数据。缺点：占用空间大因为除了存储数据外需要额外存储和该元素有逻辑关系的元素所对应的地址。查看数据慢，因为需要从头依次查找，链式存储的地址值可能是不连续的，需要通过上一个数据查找下一个数据的存储地址。优点：插入、删除数据速度快，因为不需要移动元素，只要改变数据中存储的相邻元素的地址值就可以实现。

索引存储：

简介：将数据和数据间的关系进行分别存储。存放数据间逻辑关系的区域称为索引区域。优点：提高查询数据的速度，我们可以通过索引区域快速查找到其对应数据的物理地址。缺点：需要额外维护索引区域，增加内存消耗。

哈希存储：

简介：哈希存储（散列存储）是存放在一块地址连续的存储区域的。元素的存储位置是将数据的关键值通过哈希算法计算得到的。优点：查询速度快，因为数据的地址值是通过数据本身来决定的，知道地址就可以节省数据查找。缺点：数据过多时，可能会产生哈希值冲突。

什么是链表数据结构？

链表的数据元素是一个一个串联在一起的，这一串数据形成的结构就是“链表”。它就像一条自行车“链条”一样。每一个数据元素可以称之为一个节点。

特点：

链表在内存中的物理存储空间是非连续、非顺序的。其中每个节点包含两部分，一个是存储数据元素的“数据域”，另一个是存储下一个节点地址的“指针域”。

优点：

1、因为链表对内存空间的连续性和顺序性没有要求，所以它可以充分利用内存空间，并且这一特点还造就了链表可以不必预先知道数据的大小，更加灵活。

2、链表插入和删除数据速度快，只需要修改相邻节点的指针域就行。

缺点：

1、每个节点除了存储数据外还需要额外的存储下一个节点的地址，因此占用内存空间大。

2、链表没办法像有索引的数据结构那样随机访问某一个元素，只能每次查找元素时从链表的头节点或尾节点开始遍历，增加了查询数据的消耗。

分类：

单向链表：只保存了下一个节点地址值的链表。

双向链表：不光保存了下一个节点的地址值，还保存了上一个节点的。

环形链表：首尾相连的链表

Map的常用实现类

java为数据结构中的映射定义了接口 java.util.Map, 常用的实现类有4个，分别是：

HsahMap: 继承自AbstractMap，它根据key的hashcode值存储数据，大多数情况下可以快速定位到value，因而具有很快的查找速度。HashMap最多只允许一条记录的key为null，允许多条记录的value为null. HashMap非线程安全，多个线程同时写入数据可能会导致数据不一致。如果需要满足线程安全，可以同Collections的synchronizedMap方法，使hashMap具备线程安全，或者使用ConcurrentHashMap

HashTable：遗留类，大部分功能与hashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只能有一个线程操作HashTable, 因此并发性不如ConcurrentHashMap, 因为ConcurrentHasoMap引入了分段锁，将Map分为n个数据段，给每段配一把锁，读不加锁，写的时候只需要锁住某个确定的数据段。

LinkedHashMap：是haspMap的一个子类，区别是它保存了记录的插入顺序，因而遍历时先得到的记录肯定是先插入的。也可以在构造时带参数，按照访问次序进行排序。

TreeMap：它实现了SortedMap接口，能够把它保存的记录根据key来排序，默认升序，也可以指定排序的比较器。遍历treeMap时，得到的记录是排过序的。如果使用treeMap，那么key一定要实现Comparable接口，或者在构造TreeMap时传入自定义的比较器Comparator，否则会在运行时抛出java.lang.ClassCastException

那么了解上述基础之后，我们来详细看看hashMap

HashMap的存储结构

在JDK1.8之前， hashMap的实现方式是数组+链表

在JDK1.8之前， HashMap使用Entry数组来存储数据，用key的hashCode取模来决定key会被放到数组里的哪个位置。如果hashcode相同，或者hashcode取模后的结果相同（就是哈希冲突），那么这些key就会被定位到entry数组的同一个格子里，形成一个单链表，那么在hashcode特别差的情况下，这个链表就可能会很长，我们知道在链表查询中，是需要遍历的，所以耗时就会很长

因此，在JDK1.8中引入了红黑树， hashMap的实现方式就是数组+链表+红黑树

JDK1.8中使用Node数组来存储数据，Node是Entry接口的实现类，但这个node可能是链表结构，也可能是红黑树结构。如果哈希冲突后，链表的长度超过8（默认阙值），就会调用treeifyBin函数，将链表转换为红黑树

HashMap的关键字段

/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

默认初始容量16，必须为 2的n次幂，这也是创建的数组的长度

/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments. //就是说我们可以通过构造函数来创建指定容量的hashMap
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30; //2的30次幂
最大容量，

/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认负载因子0.75

/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
JDK 1.8后，由链表结构转换为红黑树结构的阙值，链表长度大于8时转为红黑树，查找速度更快

/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
扩容过程中，如果红黑树长度小于6，将由红黑树转为链表

/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
红黑树的最小容量为64，超过64将对hashmap进行扩容

构造方法：

/**
* Constructs an empty HashMap with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

默认负载因子0.75，数组容量16

/**
* Constructs an empty HashMap with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY; //数组容量最大为2的30次幂
if (loadFactor <= 0 || Float.isNaN(loadFactor)) //传入的数组容量和负载因子都不能小于0
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}

注意这里计算阙值的方法，

threshold = tableSizeFor(initialCapacity)

/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
int ss = (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
该方法会返回一个为2的n次幂，大于等于给定容量cap且小于最大容量的数，如：

这里有一点搞不明白，在阙值的定义中，我们看到阙值等于容量*负载因子

/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;

那为什么在构造函数里要这样计算阙值呢？
------继续看源码找到了答案：构建hashMap对象时并不会去初始化或者扩容table, 所以这里的threshold只是一个初始阙值，当我们首次调用put方法添加键值对的时候，会调用resize（）方法来初始化，同时计算阙值=容量*负载因子

（摘自【java】HashMap 一遍就懂！！！！_疯-CSDN博客_hashmap 仅作个人笔记使用，感谢博主）

HashMap的put实现

当我们创建了一个HashMap之后，不管增加，删除，修改，查找键值对。首先最重要的一点就是确定数组索引位置

前面说过， HashMap是数组+链表的存储方式，所以我们当然希望这个hashMap里的元素分布尽量均匀，每个数组索引下的元素只有一个，这样就不用遍历列表。所以在我们put数据时，确定它对应的数组索引至关重要。

看源码(方法一 + 方法二)：

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。

方法一：若key为null，则直接返回0，否则通过h = key.hashCode()计算出key的hashcode，然后返回h ^ (h >>> 16)的值。h >>> 16为无符号向右移动16位，移位之后，h的高16位全部变成了0，计算过程如下：

这样做的好处是，低位的信息中混入了高位的信息，这样高位的信息被变相的保留了下来，而且，HashMap已经使用了红黑树对table中的节点碰撞做了处理，因此我们只是以最简单的方式做一些移位，然后进行异或运算。采用这种计算方式，是在速度、性能、分布上做的一个平衡，掺杂的元素多了，那么生成的哈希值的随机性会增大。我们可以看这么一个例子：

运行结果：

haseCode & (capacity - 1)是用来计算节点对应的数组下标，我们后面会介绍。可以看到如果直接使用key的hashcode作为节点的哈希值，计算出来的三个几点处于同一位置，这就产生了哈希冲突，而如果我们使用h ^ (h >>> 16)作为哈希值，计算出来的三个节点的位置都不相同，也就是说这种方式计算出的哈希值随机性更大，能使节点的分布更加均匀。

这也正好解释了为什么HashMap的数组长度要取2的整次幂。因为数组长度-1正好相当于一个“低位掩码”。这个掩码和节点的哈希值进行与操作的结果就是哈希值的高位全部归零，只保留低位值，用来做数组下标访问。同时，capacity - 1的二进制表示中的最后一位是1，这样便保证了haseCode & (capacity - 1)的最后一位可能为0，也可能为1，即计算出的下标可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，若capacity - 1的二进制表示中的最后一位是0，则计算出的下标都是偶数，所有奇数下标都没有被使用，不仅不均匀，而且还浪费了一半空间。

————————————————
版权声明：本文为CSDN博主「DivineH」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_38293564/article/details/80688474

对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。

这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

明白了如何确定数组下标之后，我们来看看put的执行过程：

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

HashMap的get实现：首先对key做hash运算，得到数组索引，然后调用getNode方法获得对应节点

这里需要注意的是，get(Object)方法返回结果为null并不是说HashMap中没有对应key的映射，因为HashMap中key和value都允许为null，这也有可能是key对应的value为null。

HashMap的remove方法

先对key做hash运算得到数组下标，然后再调removenode方法删除节点

remove(Object)方法调用removeNode方法，设置的value为null，matchValue为false，这表明，不需要key和value全部匹配才删除节点，只要key匹配就可以删除了。

HashMap的containsKey()和ContainsValue()方法

因为hashMap中允许一个键值对的key为null, 多个键值对的value为null, 所以我们不能用getObject(key)是否为null来判断key是否存在, 而应该使用containsKey

若该key存在，无论它对应的value是否为null, 但node节点不为null

从上面代码可以看到， containsValue方法会遍历整个哈希表，所以---慎用

hashMap中的数组长度为什么是2的n次幂？

原因一：取模时，可以使hashMap上的数组元素分布均匀

我们在确定下标的时候， i = (length-1) & hash,

&是二进制中的与运算，其特点是：两个数进行&，如果相同位置都为1，则结果为1，否则结果为0

如果数组长度不为2的n次幂的话，那么对应的二进制数肯定有一位为0（如 8-1 转换为二进制 0111， 7-1转换为二进制就是0110）

当(length - 1)转换为二进制后低位为111时， &运算之后，可以完整地得到原hash值的低位值。

如果不为2的n次幂，那么&运算会改变原hash值的低位值（0 & 0 =0， 1&0 = 0），这带来的问题就是hashMap上的数组元素分布不均匀，而数组上的某些位置，永远也用不到

原因二：JDK1.8 扩容过程中，不需要在重新计算哈希值再取模获得元素下标

HashMap的扩容机制

HashMap使用的是懒加载，构造hashMap对象的时候并不会去初始化或者扩容数组，当首次调用put方法的时候， HashMap会发现table为空，然后调用resize方法进行初始化。

当HashMap中的元素越来越多时，因为数组长度是固定的，所以hash冲突的几率也就越来越高。那么为了提高查询的效率，我们就需要对hashMap的数组进行扩容。

扩容过程如下：

扩容是一个相当消耗性能的过程，尤其是在JDK 1.7之前，因为原数组中的元素必须重新计算在新数组中的位置（下标）

JDK1.8对此作了优化：

因为数组长度是2的n次幂，每次扩容也是将数组长度变为原来的2倍，所以

在取模运算 h & (length -1)中， h是我们给key的hashcode做高位运算的结果，扩容前后并不会变，

length -1 扩容后比扩容前大了一倍，如扩容前为16（01111）则扩容后为32（11111）

所以在取模运算获取索引的时候，如果之前的h高位是0，那么索引不变（0&0=0， 0&1=0），如果之前的h的高位是1，那么索引就变成原索引+ 扩容前的容量。

所以在JDK1.8中，我们在扩充hashMap后，不需要再重新计算hash，做取模运算，只需要看原来的hash值里新增的那个bit位是0还是1就可以了，是0的话索引不变， 1的话远索引+原容量

这个设计非常巧妙，省去了重新计算哈希值的时间，同时因为新增的bit位是0还是1可以认为是随机的，所以扩容后会均匀地把之前冲突的节点分散到其他节点。

例如：

有四个节点，它们的哈希值分别为3、11、19、27，若初始容量为8，这四个节点都位于下标为3的位置，在扩容之后，哈希表容量变为16，因为3 & 8 == 0，19 & 8 == 0，所以，这两个节点仍然在新table下标为3的位置，但是11 & 8 != 0,27 & 8 ！= 0，所以，这两个节点会在新table下表为(3+8) = 11的位置，我们验证一下：11 & (16 - 1) = 11，27 & (16 - 1) = 11，这两个节点确实应该在下标为11的位置。

这里也体现出了哈希表容量为2的整数次幂的另一个好处，在rehash时，节点在新table中的下标计算很方便。

还有一点区别就是，在JDK1.7中，旧链表迁移到新链表时，如果在新表的数组索引位置相同，则链表元素会倒置，但是在JDK1.8中不会

HashMap是线程不安全的
2种办法让HashMap线程安全_u012045045的博客-CSDN博客_hashmap 线程安全

在多线程的使用场景中，应尽量避免使用hashMap, 而使用线程安全的ConcurrentHashMap

那么为什么说hashMap是线程不安全的呢？

它的线程不安全主要体现在会造成死循环，数据丢失，数据覆盖这些问题。其中死循环，数据丢失发生在JDK1.7扩容操作中，在JDK1.8中得到了修复

我们先来看JDK 1.7

这段代码是HashMap的扩容操作，重新定位每个桶的下标，并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转，这也是形成死循环的关键点。

由于缺乏同步机制，当多个线程同时 resize 的时候，某个线程 t 所持有的引用 next（参考上面代码next指向原桶数组中某个桶外挂单链表的下一个需要转移的 Entry ），可能已经被转移到了新桶数组中，那么最后该线程t实际上在对新的桶数组进行 transfer 操作。

JDK1.8移除了transfer函数，在resize函数中完成了数据迁移，而且采用了尾插法，因此不再有死循环和数据丢失的问题。

但是在多个线程同时调用put方法时，可能会发生数据覆盖，下面是putVal方法的代码段：

其中第六行代码是判断是否出现hash碰撞，假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完第六行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。

除此之外，还有就是代码的第38行处有个++size，我们这样想，还是线程A、B，这两个线程同时进行put操作时，假设当前HashMap的zise大小为10，当线程A执行到第38行代码时，从主内存中获得size的值为10后准备进行+1操作，但是由于时间片耗尽只好让出CPU，线程B快乐的拿到CPU还是从主内存中拿到size的值10进行+1操作，完成了put操作并将size=11写回主内存，然后线程A再次拿到CPU并继续执行(此时size的值仍为10)，当执行完put操作后，还是将size=11写回内存，此时，线程A、B都执行了一次put操作，但是size的值只增加了1，所有说还是由于数据覆盖又导致了线程不安全。

modCount的作用-- fast-fail

Fail-Fast机制

我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现是通过 modCount 域，modCount 顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了 Map：注意到 modCount 声明为 volatile，保证线程之间修改的可见性。

每次调用对象的next()方法的时候都会调用checkForComodification()方法进行一次检验，checkForComodification()方法中做的工作就是比较expectedModCount 和modCount的值是否相等，如果不相等，就认为还有其他对象正在对当前的List进行操作，那个就会抛出ConcurrentModificationException异常。

解决ConcurrentModificationException有两种办法

一般有2种解决办法：

　　1）在使用iterator迭代的时候使用synchronized或者Lock进行同步；（一个个迭代就和单线程一样了）

　　2）使用并发容器ConcurrentHashMap或者HashTable(不建议)。

红黑树在hashMap中的使用
- 链表长度超过阈值8后，HashMap开始将链表升级成一个二叉树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的，不过如果实现了当然最好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了。
为什么通常用string作为hashMap的key?

设计hashMap时最重要的因素，就是对同一个对象调用hashCode()都应该产生相同的值。

String类型的对象对这个条件有着很好的支持，因为string重写了hashCode（）方法，它的hashCode值是根据string的内容计算的，而不是根据对象的地址计算。所以内容相同， hashCode就一定相同

当然我们也可以使用其他对象作为hashMap的key, 但需要实现equals()和hashCode()方法。

但即使我们给自定义对象重写了上面两个方法，实际使用中也没有string高效，因为string是不可变对象，其中有个hash变量，它可以缓存hashCode, 避免重复计算。