主要是分析HashMap类相关源码原理。
数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)
线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)
二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。
哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。
我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。
比如我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。
利用存储位置 = f(关键字)。其中，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。举个例子，比如我们要在哈希表中执行插入操作：
查找操作同理，先通过哈希函数计算出实际存储地址，然后从数组中对应地址取出即可。
二、哈希冲突然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}HashMap是一个利用哈希表原理来存储元素的集合。遇到冲突时，HashMap是采用的链地址法来解决，在 JDK1.7中，HashMap 是由 数组+链表构成的。JDK1.8 中，HashMap 是由 数组+链表+红黑树构成，新增了红黑树作为底层数据结构，结构变得复杂了，但是效率也变的更高效。
HashMap是一个散列表，它存储的键值对(key-value)映射，而且key和value 都可以为 null。
public class HashMap extends AbstractMap
implements Map, Cloneable, Serializable
//默认 HashMap 集合初始容量为16（必须是 2 的倍数）
static final int DEFAULT_INITIAL_CAPACITY = 1 > 操作符表示无符号右移，高位取0。
// | 按位或运算
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;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
//hash(key)获取Key的哈希值，equls返回为true,则两者的hashcode一定相等，意即相等的对象必须具有相等的哈希码。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
*
* @param hash Key的哈希值
* @param key 键
* @param value 值
* @param onlyIfAbsent true 表示不要更改现有值
* @param evict false表示table处于创建模式
* @return
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
//如果table为null或者长度为0，则进行初始化
//resize()方法本来是用于扩容，由于初始化没有实际分配空间，这里用该方法进行空间分配，后面会详细讲解该方法
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//(n - 1) & hash：确保索引在数组范围内,相当于hash % n 的值
//通过 key 的 hash code 计算其在数组中的索引：为什么不直接用 hash 对 数组长度取模？因为除法运算效率低
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);//tab[i] 为null，直接将新的key-value插入到计算的索引i位置
else {//tab[i] 不为null，表示该位置已经有值了
Node e; K k;
//e节点表示已经存在Key的节点，需要覆盖value的节点
//table[i]的首个元素是否和key一样,如果相同直接覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//节点key已经有值了，将第一个节点赋值给e
//该链是红黑树
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
//该链是链表
else {
//遍历链表
for (int binCount = 0; ; ++binCount) {
//先将e指向下一个节点，然后判断e是否是链表中最后一个节点
if ((e = p.next) == null) {
创建一个新节点加在链表结尾
p.next = newNode(hash, key, value, null);
//链表长度大于8，转换成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key已经存在直接终止，此时e的值已经为 p.next
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//修改已经存在Key的节点的value
e.value = value;
afterNodeAccess(e);
//返回key的原始值
return oldValue;
}
}
++modCount;//用作修改和新增快速失败
if (++size > threshold)//超过最大容量，进行扩容
resize();
afterNodeInsertion(evict);
return null;
}- 判断键值对数组 table 是否为空或为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，如果超过，进行扩容。
- if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) 此处先判断p.hash == hash是为了提高效率，仅通过(k = e.key) == key || key.equals(k)其实也可以进行判断，但是equals方法相当耗时！如果两个key的hash值不同，那么这两个key肯定不相同，进行equals比较是扯淡的！ 所以先通过p.hash == hash该条件，将桶中很多不符合的节点pass掉。然后对剩下的节点继续判断。
- h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。数组的长度按规定一定是2的幂。因此，数组的长度的二进制形式是：10000…000, 1后面有偶数个0。 那么，length - 1 的二进制形式就是01111.111, 0后面有偶数个1。
final Node[] resize() {
//将原始数组数据缓存起来
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//原数组如果为null，则长度赋值0
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {//如果原数组长度大于0
if (oldCap >= MAXIMUM_CAPACITY) {//数组大小如果已经大于等于最大值(2^30)
threshold = Integer.MAX_VALUE;//修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
return oldTab;
}
//原数组长度扩大1倍(此时将原数组扩大一倍后的值赋给newCap)也小于2^30次方，并且原数组长度大于等于初始化长度16
else if ((newCap = oldCap = DEFAULT_INITIAL_CAPACITY)
newThr = oldThr 0)
//旧容量为0，旧阀值大于0，则将新容量直接等于就阀值
//在第一次带参数初始化时候会有这种情况
//newThr在面算
newCap = oldThr;
else {
//阀值等于0，oldCap也等于0（集合未进行初始化）
//在默认无参数初始化会有这种情况
newCap = DEFAULT_INITIAL_CAPACITY;//数组长度初始化为16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//阀值等于16*0.75=12
}
//计算新的阀值上限
//此时就是上面原数组长度扩大一倍后大于MAXIMUM_CAPACITY和旧容量为0、旧阀值大于0的情况
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将阀值上限设置为新阀值上限
threshold = newThr;
//用于抑制编译器产生警告信息
@SuppressWarnings({"rawtypes","unchecked"})
//创建容器大小为newCap的新数组
Node[] newTab = (Node[])new Node[newCap];
//将新数组赋给table
table = newTab;
//如果是第一次,扩容的时候,也就是原来没有元素,下面的代码不会运行,如果原来有元素,则要将原来的元素,进行放到新扩容的里面
if (oldTab != null) {
//把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;//元数据j位置置为null，便于垃圾回收
if (e.next == null)//数组没有下一个引用（不是链表）
//直接将e的key的hash与新容量重新计算下标,新下标的元素为e
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//红黑树
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
//原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}扩容（resize），我们知道集合是由数组+链表+红黑树构成，向 HashMap 中插入元素时，如果HashMap 集合的元素已经大于了最大承载容量threshold（capacity * loadFactor），这里的threshold不是数组的最大长度。那么必须扩大数组的长度，Java中数组是无法自动扩容的，我们采用的方法是用一个更大的数组代替这个小的数组。
if ((e.hash & oldCap) == 0)如果判断成立，那么该元素的地址在新的数组中就不会改变。因为oldCap的最高位的1，在e.hash对应的位上为0，所以扩容后得到的地址是一样的，位置不会改变 ，在后面的代码的执行中会放到loHead中去，最后赋值给newTab[j]；如果判断不成立，那么该元素的地址变为 原下标位置+oldCap，也就是lodCap最高位的1，在e.hash对应的位置上也为1，所以扩容后的地址改变了，在后面的代码中会放到hiHead中，最后赋值给newTab[j + oldCap]
HashMap查找元素： get(Object key)：通过 key 查找 value：首先通过 key 找到计算索引，找到桶元素的位置，先检查第一个节点，如果是则返回，如果不是，则遍历其后面的链表或者红黑树。其余情况全部返回 null。
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//根据key计算的索引检查第一个索引
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//不是第一个节点
if ((e = first.next) != null) {
if (first instanceof TreeNode)//遍历树查找元素
return ((TreeNode)first).getTreeNode(hash, key);
do {
//遍历链表查找元素
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}判断是否存在给定的 key 或者 value
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
public boolean containsValue(Object value) {
Node[] tab; V v;
if ((tab = table) != null && size > 0) {
//遍历数组
for (int i = 0; i < tab.length; ++i) {
//遍历数组中的每个节点元素
for (Node e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}HashMap删除元素
public V remove(Object key) {
Node e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node[] tab; Node p; int n, index;
//(n - 1) & hash找到桶的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node node = null, e; K k; V v;
//如果键的值与链表第一个节点相等，则将 node 指向该节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//如果桶节点存在下一个节点
else if ((e = p.next) != null) {
//节点为红黑树
if (p instanceof TreeNode)
node = ((TreeNode)p).getTreeNode(hash, key);//找到需要删除的红黑树节点
else {
do {//遍历链表，找到待删除的节点
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
//找到就停止，如果此时是第一次遍历就找到，则node指向链表中第二个元素，p还是第一个元素
//第一次没找到，第二次找到，则node指向链表中第三个元素，p指向第二个元素，p是找到元素节点的父节点
//所以需要遍历的时候p和node 是不相等的，只有链表第一个元素就判断相等时，p和node 相等
break;
}
//第一次遍历没找到， 此时p指向第二个元素
p = e;
} while ((e = e.next) != null);
}
}
//删除节点，并进行调节红黑树平衡
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode)node).removeTreeNode(this, tab, movable);
else if (node == p)
//如果键的值与链表第一个节点相等，则将元素位置指向 node的下一个节点（链表的第二个节点），有可能node.next 为null
tab[index] = node.next;
else
//如果键的值与链表第一个节点不相等，node的父节点的next指向node的next
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}重写equals方法需同时重写hashCode方法
/**
* author xjl 2021/11/22
*/
public class MyTest {
private static class Person{
int idCard;
String name;
public Person(int idCard, String name) {
this.idCard = idCard;
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()){
return false;
}
Person person = (Person) o;
//两个对象是否等值，通过idCard来确定
return this.idCard == person.idCard;
}
}
public static void main(String []args){
HashMap map = new HashMap();
Person person = new Person(123,"乔峰");
//put到hashmap中去
map.put(person,"天龙八部");
//get取出，从逻辑上讲应该能输出“天龙八部”
System.out.println("结果:"+map.get(new Person(123,"萧峰")));
}
}如果我们已经对HashMap的原理有了一定了解，这个结果就不难理解了。尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，所以put操作时，key(hashcode1)-->hash-->indexFor-->最终索引位置 ，而通过key取出value的时候 key(hashcode2)-->hash-->indexFor-->最终索引位置，由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）
再想象一下，假如两个Java对象A和B，A和B相等（eqauls结果为true），但A和B的哈希码不同，则A和B存入HashMap时的哈希码计算得到的HashMap内部数组位置索引可能不同，那么A和B很有可能允许同时存入HashMap，显然相等/相同的元素是不允许同时存入HashMap，HashMap不允许存放重复元素。所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。
八、HashMap多线程安全问题 8.1 jdk1.7扩容时会造成环形链或数据丢失数据丢失：在jdk8之后对hashMap进行了优化，hash碰撞不再采用头插法而采用尾插法插入新节点。若a，b线程put中key的hash值相同，当线程a获取m值后未插入，此时线程b也获取m值后进行插入操作。由于hashmap不同步，导致其中一个线程的value值会丢失，这是不允许的，这就发生了线程安全问题。
HashMap一个并发可能出现的问题是，可能产生元素丢失的现象。考虑在多线程下put操作时，执行addEntry(hash, key, value, i)，如果有产生哈希碰撞，导致两个线程得到同样的bucketIndex去存储，就可能会出现覆盖丢失的情况：
void addEntry(int hash，K key, V value， int bucketIndex){
/多个线程操作数组的同一个位置
Entrye = table[ bucketIndex];
table[ bucketIndex] = new Entry(hash，key,value,e);
if (size++ >= threshold){
resize(2 * table.length);
}
}
jdk7的时候，转移元素采用头插法处理。在HashMap的transfer函数中（如下代码），当table进行newTable扩容的时候需要将原先的数据进行转移，链表的顺序将发生翻转，而在此时若hashmap不断轮询，将产生死锁，酿成悲剧。在原理的链表的数据的时候，可能会存放在新节点的因为hash值是 hash(key)%(n-1)来表示:在当一个线程遍历的是时候其他的线程获取到了这个值 这将这里null值放置新的为链表下。所以可能会造成是的null的值。
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j - 0; j < src. length;j++){
Entry e - src[j];
if (e != null){
//多线程操作时候 在这个方法里，将旧数组赋值给src，遍历src，当src的元素非null时，就将src中的该元素置null,即将旧数组中的元素置null了 :
src[j] = null;
do {
Entry next = e.next;
int i = indexFor(e.hash，newCapacity);
e.next = newTable[i];
newTable[i] - e;
e = next;
}while (e != null);
}
}
}
多线程put后可能导致get死循环。CPU利用率过高一般是因为出现了出现了死循环，导致部分线程一直运行，占用cpu时间。产生的原因是：那么JDk1.7中使用头插法新的hash桶会倒置原hash桶中的单链表，插入在多个线程同时扩容的情况下就可能导致产生一个存在闭环的单链表，从而导致死循环在。改进的方法：JDK1.8中的采用的是在尾部进行增加的元素。而不是在链头部。
8.4 jdk1.8会发生数据覆盖的情况 博文参考《JDK源码分析》
