首先需要理解几个基本概念：
- 什么是数据结构？(摘自 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的存储结构
- HashMap的关键字段
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 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 <tt>HashMap</tt> 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 <tt>HashMap</tt> 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的话远索引+原容量
有四个节点，它们的哈希值分别为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中的下标计算很方便。
- HashMap是线程不安全的
在多线程的使用场景中， 应尽量避免使用hashMap, 而使用线程安全的ConcurrentHashMap
- modCount的作用-- fast-fail
- 红黑树
小结：
(1) 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
(2) 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
(3) HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。
(4) JDK1.8引入红黑树大程度优化了HashMap的性能。