HashMap部分源码
hash算法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以看到hash算法计算分为三步
1.获得key的hash值
2.在1的基础上右移16位，即保留低16位，抹去高16位
3.1和2的结果进行异或运算（相同为0，不同为1）
hash()方法，只是key的hashCode的再散列，使key更加散列。而元素究竟存在哪个桶中。还是要看putVal方法中 (n - 1) & hash 结果决定的。
tableSizeFor方法
该方法作用是返回一个大于输入参数且最小的为2的n次幂的数
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;
}
举例：当输入为13的时候，n等于12，转成二进制为1100，右移1位为0110，将1100与0110进行或("|")操作，得到1110。接下来右移两位得11，再进行或操作得1111，接下来操作n的值就不会变化了。最后返回的时候，返回n+1，也就是10000，十进制为16。按照这种逻辑得到2的n次幂的数。
分析算法：实现把从最高位开始第一个为1的位之后所有的位全部变成1，此时返回n+1即可得到一个正好比原数大的最小的2的n次幂
还有一个问题，为什么要在前面减1即 n = cap - 1？
减一是为了传进来的本身就是2的幂次方整数这种情况不减一会返回本身的两倍，减一返回本身
重要成员变量和函数
// 16 默认初始容量（这个容量不是说map能装多少个元素，而是桶的个数）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量值
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//树化阈值 一个桶链表长度超过 8 进行树化
static final int TREEIFY_THRESHOLD = 8;
//链表化阈值 一个桶中红黑树元素少于 6 从红黑树变成链表
static final int UNTREEIFY_THRESHOLD = 6;
//最小树化容量，当容量未达到64，即使链表长度>8，也不会树化，而是进行扩容。
static final int MIN_TREEIFY_CAPACITY = 64;
//桶数组，bucket. 这个也就是hashmap的底层结构。
transient Node<K,V>[] table;
//数量，即hashmap中的元素数量
transient int size;
//hashmap进行扩容的阈值。 （这个表示的元素多少，可不是桶被用了多少哦，比如阈值是16，当有16个元素就进行扩容，而不是说当桶被用了16个）
int threshold;
//当前负载因子，默认是 DEFAULT_LOAD_FACTOR=0.75
final float loadFactor;
/************************************三个构造方法***************************************/
public HashMap(int initialCapacity, float loadFactor) {//1，初始化容量2，负载因子
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)// > 不能大于最大容量
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);//总要保持 初始容量为 2的整数次幂
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
这里需要注意：
1.当容量未达到64，即使链表长度>8，也不会树化，而是进行扩容。
2.一个桶中红黑树元素少于 6 从红黑树变成链表
3.默认初始容量DEFAULT_INITIAL_CAPACITY不是说map能装多少个元素，而是桶的个数
4.threshold表示hashmap进行扩容的阈值。（这个表示的元素多少，可不是桶被用了多少哦，比如阈值是16，当有16个元素就进行扩容，而不是说当桶被用了16个）
put过程源码分析
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//put1，懒加载，第一次put的时候初始化table（node数组）
if ((tab = table) == null || (n = tab.length) == 0)
//如果table为null或者长度为0，hashmap数组初始化
n = (tab = resize()).length;
//计算下标，返回null代表没有hash碰撞
if ((p = tab[i = (n - 1) & hash]) == null)
//new一个Node放入数组中
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如过命中第一个节点，覆盖旧值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果是红黑树直接插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果是链表，存在两种情况，超过阈值转换成红黑树，否则直接在链表后面追加
for (int binCount = 0; ; ++binCount) {
//在链表尾部追加
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//树化（转化成红黑树）
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果key已经存在，覆盖旧值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//当key已经存在，执行覆盖旧值逻辑。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//当size > threshold，进行扩容。
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
可以看到put方法中调用putVal方法进行元素的添加，hash(key)方法获得二次hash后的hash值作为putVal的入参
1.判断当前table是否为空，hashMap将初始化操作放在第一次put的时候
2.计算hash及桶下标。
3.判断是否发生hash碰撞
3.1 没有发生碰撞，new一个node直接放入桶中
3.2 发生碰撞
（1） 如过命中第一个节点，直接覆盖节点并返回旧值
（2）如果是红黑树，插入到红黑树中。
（3）如果是链表，存在两种情况，超过阈值转换成红黑树，否则直接在链表后面追加，（当数组长度小于64时，进行扩容而不是树化）
4.根据上述步骤找到的key覆盖旧节点并返回旧值。
5.如果size > threshold。进行扩容。
treeifyBin方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果容量 < 64则直接进行扩容；不转红黑树。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
hashmap如何扩容的？
（1）扩容时机：
- 初始化后放入元素时：创建对象以后，HashMap并不是立即初始化table，而是在第一次放入元素时，才会初始化table，这很HashMap节省内存得一种机制，而table的初始化其实是resize方法实现的。
- 达到阈值时：这个就比较有意思，所谓阈值，就是HashMap中threshold这个属性，阈值的计算方式很简单，基本上就是capacity（table容量） * loadFactor（负载因子），这里我觉得capacity应该称为理论容量，是因为正常情况下达到阈值就扩容了，达到阈值时HashMap认为哈希冲突的次数会不能接受，因此需要扩容。
（2）这里为什么链表长度大于8了还要满足元素个数不小于64才会进行扩容呢？
hashmap默认容量为16，然而插入了9个元素，它们都在同一个桶里面，如果这时进行树化，树化本身就是一个耗时的过程。时间复杂度会增加，性能下降，不如直接进行扩容，空间换时间。
resize方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 大于最大容量，不进行扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//扩容为原来的两倍，<< 位运算
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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"})
//创建新的桶（原来的两倍）
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//只有一个元素，直接移到新的桶中（为什么不先判断是不是TreeNode？注意TreeNode没有next节点，同样返回为null
if (e.next == null)
//使用newCap计算桶下标
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//有多个元素
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//判断成立，说明该元素不用移动
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//判断不成立，说明该元素要移位到 (j + oldCap) 位置
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//j + oldCap即newIndex
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
总结一下：
- 先确定newCap和newThr
- 创建一个两倍于原来（oldTab）容量的数组（newTab）
- 遍历oldTab
- 如果当前桶没有元素直接跳过。
- 如果当前桶只有一个元素，直接移动到newTab中的索引位。（e.hash & (newCap - 1)）
- 如果当前桶为红黑树，在split()方法中进行元素的移动。
- 如果当前桶为链表，执行链表的元素移动逻辑。
get源码分析
public V get(Object key) {
Node<K,V> e;
//计算哈希，调用getNode方法获得Node
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//非空校验以及下标计算
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//获取桶的头节点，如果头结点key等于目标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<K,V>)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;
}
jdk7死循环问题
jdk8之前采用头插法，因为作者认为新插入的数据被使用的概率更大，但是有一个弊端就是并发情况会造成链表闭环，get时死循环，主要发生在扩容方法的transfer 方法
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
//保留要转移指针的下一个节点
Entry<K, V> next = e.next;
//计算出要转移节点在hash桶中的位置
int i = indexFor(e.hash, newCapacity); -----------------1
//使用头插法将需要转移的节点插入到hash桶中原有的单链表中
e.next = newTable[i]; -----------------2
//将hash桶的指针指向单链表的头节点
newTable[i] = e; -----------------3
//转移下一个需要转移的节点
e = next;
} while (e != null);
}
}
}
代码解析：
1.记录当前节点的next节点
2.indexFor计算桶位置
3.当前节点的next指向桶内链表头结点
4.当前节点放入原表头完成头插
5.e指向第一步记录的next节点，若不为null循环执行逻辑
为什么会造成闭环呢？
HashMap扩容导致死循环的主要原因在于扩容后链表中的节点在新的hash桶使用头插法插入。新的hash桶会倒置原hash桶中的单链表，那么在多个线程同时扩容的情况下就可能导致产生一个存在闭环的单链表，从而导致死循环。
在JDK1.8中，HashMap是不会造成死循环的，因为在JDK1.8中，采用的是尾插法，保证了链表的顺序与之前一致。而且在1.8中链表过长时会转换为红黑树，在转换为红黑树前，也是先根据尾插法生成新链表再进行转换的，所以是不会造成死循环的。
过程分析：首先假设在扩容时，hash表中有一个单链表，单链表中有两个元素：元素1和元素2。
如果该HashMap为单线程操作时没问题，多线程时（假设有T1、T2两个线程）：
- T1执行到 next = e.next；时挂起；
- T2开始执行并且执行完了整个流程，也就是说T2把所有元素都插入了新数组之后（头插法），原来的table引用现在指向了 newtable，即 table = newtable；
-
T1回归继续执行，这时就会有如下场景
- 当元素1正常插入后 next 是 元素2，e = next = 元素2，继续执行插入
-
此时，由于原表中 元素2 的 next 已经被T2所修改，不再是T1挂起时的 next = null了，所以T1就会碰到如下情况，因为 next 永远都不为空，所以就会一直循环执行插入操作，造成死循环。（图中这种状态的链表称为死链）
jdk8是怎么扩容的呢（扩容机制的优化）？
if (loTail != null) {
loTail.next = null;
//新的位置为原老所处的位置
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//新的位置为原老所处的位置+原数组的长度
newTab[j + oldCap] = hiHead;
}
只需要注意newTab[j] = loHead和newTab[j + oldCap] = hiHead这两行代码，其中newTab为新的数组，j为元素在原数组中的下标，oldCap为原数组的长度，loHead和hiHead都为元素。
为什么经过rehash之后，元素的位置要么是在原位置，要么是在原位置加原数组长度的位置？
rehash利用的特性：元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：ps：HashMap数组中链表节点存放了：key、value、hash、next属性。
扩容前 hash & (length - 1) :
key1 : 0001 1001 & 0000 1111 -> 0000 1001
key2 : 0000 1001 & 0000 1111 -> 0000 1001
扩容后 hash & (length - 1) :
key1 : 0001 1001 & 0001 1111 -> 0001 1001
key2 : 0000 1001 & 0001 1111 -> 0000 1001
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看原来的hash值在扩容后新增的那一位是1还是0，如果是0的话索引没变，是1的话索引变成“原索引+oldCap” 。可以看看下图为16扩充为32的resize示意图：
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。代码：
if ((e.hash & oldCap) == 0）
jdk8采用尾插法很好的避免了这个问题（但出现了数据丢失现象），那么jdk8就是线程安全的吗？不是的!!!!
if ((p = tab[i = (n - 1) & hash]) == null)
这段代码是判断是否出现hash碰撞，假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了（数据丢失），从而线程不安全。
除此之外，++size操作和resize等操作都会因为原子性问题造成数据丢失或者覆盖。
常见问题总结
1.HashMap在jdk7与8两个版本中有什么区别？
- 数据结构不同：jdk7使用数组+链表；jdk8使用数组+链表+红黑树，引入了红黑树，目的是避免单条链表过长而影响查询效率；
- 链表插入方式不同：jdk7头插法（多线程可能导致链表死循环）；jdk8采用尾插法，解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。
- 扩容时机不同：在JDK1.7的时候是先扩容后插入的，这样就会导致无论这一次插入是不是发生hash冲突都需要进行扩容，如果这次插入的并没有发生Hash冲突的话，那么就会造成一次无效扩容，但是在1.8的时候是先插入再扩容的，优点其实是因为为了减少这一次无效的扩容，原因就是如果这次插入没有发生Hash冲突的话，那么其实就不会造成扩容。
- 扩容后重新计算索引的方式不同：jdk1.7需要与新的数组长度进行重新hash运算，这个方式是相对耗性能的，而且多线程环境下会造成死锁；jdk8优化resize 扩容，会判断之前hash中新增的那一位是0还是1，如果是0的话索引没变，是1的话索引变成“原索引+oldCap” 。
ps：resize()方法会在HashMap的键值对达到“阈值”后进行数组扩容，而扩容时会调用resize()方法，此外，在jdk1.7中数组的容量是在HashMap初始化的时候就已经赋予（默认16），而在jdk1.8中是在put第一个元素的时候才会赋予数组容量，而put第一个元素的时候也会调用resize()方法。
有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，造成死循环（这也是扩容优化的关键原因），JDK1.8不会。
2.HashMap的put和get方法的具体流程？
当我们put的时候，首先计算 key的hash值，这里调用了 hash方法，hash方法实际是让key.hashCode()与key.hashCode()>>>16进行异或操作，高16bit补0，一个数和0异或不变，所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。因为bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash。
put方法具体流程（jdk1.8）：
①.判断键值对数组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即可；
⑥.插入成功后，存放元素后将 modCount 加 1。判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
get方法具体流程（jdk1.8）：
- 通过 hash & (table.length - 1)获取查找的数组下标;
- 判断首节点是否为空, 为空则直接返回空,不为空进入3;
- 再判断首节点.key 是否和目标值相同, 相同则直接返回(首节点不用区分链表还是红黑树)对应的值，否则进入4;
- 首节点.next为空, 则直接返回空;
- 首节点是树形节点, 则进入红黑树数的取值流程, 并返回结果;
- 进入链表的取值流程, 并返回结果;
3.简述hashmap为什么要转为红黑树？为什么不直接开始就使用红黑树？
为什么使用红黑树？
- 因为当链表长度过长，查找元素耗时（单链表），用红黑树可以减少遍历时间，提高遍历效率。
- 如果一开始就使用红黑树，那么就要进行左旋，右旋，变色等操作，在元素个数较小的时候会消耗时间，并且遍历时间消耗与链表没什么区别。
可不可以使用二叉树，不用红黑树？为什么阈值是8？
- 可以使用二叉树，但是使用二叉树可能会出现只有左子树或者右子树的情况（即退化为单链表）。
- 阈值是8是因为泊松分布，单个hash槽中元素为8的概率小于百万分之一，所以选择7为分水岭，为7不做操作。
- 引入红黑树之后当桶中链表长度超过8且容量达到64将会树化即转为红黑树（put触发）。当红黑树元素少于6会转为链表（remove触发）。
ps：为什么树化和链表化的阈值不一样？
- 想一个极端情况，假设阈值都是8，一个桶中链表长度为8时，此时继续向该桶中put会进行树化，然后remove又会链表化。如果反复put和remove。每次都会进行极其耗时的数据结构转换。
- 如果是两个阈值，将会形成一个缓冲带，减少这种极端情况发生的概率。
一般使用什么作为key？
- 一般使用String，Integer这种不可变类作为key，保证了hash值是不可更改的，减少了hash碰撞。
- 并且这种类已经很好的实现了hashcode与equals方法的重写！ps：因为hashcode生成是一串定长的数字，当数据量很大时候，难免会出现不同对象hashcode相同的情况。也就是说hashcode相同，元素可能不同，hashcode不同，元素一定不同。
HashMap 中的 key若 Object类型， 则需实现哪些方法？
- hashcode方法：计算数据存储位置（只是为了缩小比较的范围，提高效率）
- equals方法：判断插入位置是否存在相同的key，若相同，直接覆盖value（保证key唯一）。
4.HashMap是如何确定键值对的位置？如何解决Hash冲突？
不用hash值直接做索引的原因：hashCode()方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）~2 ^ 30，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置。
如何确定键值对位置（确定插入的索引位置）：
- 如果key为null，则都会被放置在数组的第0位。
- 如果key不为null，则通过key的hashCode方法获得hash值->与自身右移16位进行异或运算->与length - 1进行与运算，得到数组中的索引获得元素 或 再到链表或红黑树中查询。
hash表如何避免哈希冲突：
- hash算法
- 在hashCode后获得的hash值在与自身右移16位进行异或运算
- 每次扩容都只扩容2的次幂，都是为了尽量减少hash冲突，提高查询效率。
- 扩容机制
- 当哈希表中的元素个数 >= 扩容阈值（容量*加载因子）
- 数据结构（存储机制）
- 链地址法 + 红黑树（jdk1.8）
5.HashMap存值过程中什么时候进行数组扩容？为什么每次扩容都是2的次幂？
扩容时机：
- 在存值后进行扩容，即put操作。注意：当数组容量未达到64，即使链表长度>8，也不会树化，而是进行扩容。
- 在jdk1.8中，resize方法扩容是在hashmap中的键值对大于阀值时, 即当前数组的长度乘以加载因子的值的时候。或者初始化时，就调用resize方法进行扩容；
HashMap中的加载因子为什么是0.75，如果调整为1会发生什么？
- 加载因子为0.75是官方给出的默认数值，在官方给出的注释中也表明了这是一个折中的选择。
- 加载因子越小空间利用率越低，查询效率越高；而越接近1，空间利用率越高，效率越低。
- 调整为1则当HashMap中数组每个位置都有键值对时才进行扩容，即最大程度的利用空间。
扩容细节：
- 每次扩容为2的幂次，因为只有当数组大小为2的幂次，数组最大索引（数组的长度 - 1）的二进制表示的每个位置都是1，从而使&运算的分布更加均匀，减少了hash冲突。
- 扩展后Node对象的位置要么在原位置，看原来的hash值在扩容后新增的那一位是1还是0，如果是0的话索引没变，是1的话索引变成“原索引+oldCap” 。
hashmap的长度是2的幂次（分析）
-
为了能让 HashMap 存取⾼效，尽量少碰撞，也就是要尽量把数据分配均匀。Hash值⽤之前还要先做对数组的⻓度取模运算，得到的余数才能⽤来要存放的位置也就是对应的数组下标。这个数组下标的计算⽅法是“ (n - 1) & hash ”。我们⾸先可能会想到采⽤%取余的操作来实现。
-
但是，重点来了：“hash % length 等价于 hash & (length-1) 。” （1）采⽤⼆进制位操作 &，相对于%能够提⾼运算效率，（2）减少hash碰撞，2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1；
6.HashMap有什么特点？
（1）键值允许为空（null）
- key可为null，但是必须唯一（这时hash值默认设置为0）；
- value可以有多个null，不需要唯一。
（2）线程安全问题
多线程下死循环问题（jdk1.7）：
- 在多线程下，jdk1.7扩容操作时可能会造成死循环，单链表倒置，具体见上边例子。
- 不过，jdk 1.8 后解决了这个问题，1.7链表元素采用的是头插法，1.8改成尾插法。但是还是不建议在多线程下使⽤ HashMap，因为多线程下使⽤ HashMap 还是会存在其他问题⽐如数据丢失。并发环境下推荐使⽤ ConcurrentHashMap。
多线程下数据丢失问题：
- 操作头结点：HashMap底层在操作每个数组位置时都是将节点头拿下来进行操作，操作后再将节点头放回去。这样就会导致两个线程同时获取相同的节点头，先放上去节点头的线程被后放上去的覆盖导致数据丢失。
- 添加尾结点：再比如在元素添加时也会出现同时获取到最后一个元素（多线程添加他的next节点），先添加的next节点被后添加的覆盖导致数据丢失。
怎么解决hashmap线程安全问题？
- 使用HashTable 或 ConcurrentHashMap，但是推荐ConcurrentHashMap，因为hashtable加锁的方式很粗暴，加的是整个add方法，也就是锁住了整个数组，ConcurrentHashMap仅仅是锁住了一个node节点。
ps：hashset是基于hashmap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75的hashmap。封装了一个hashmap 对象来存储所有的集合元素，所有放在 hashset中的集合元素实际上由 hashmap的key来保存，而 hashset中的 hashmap的 value则存储了一个PRESENT的静态object对象
ps：hashset和 treeset有什么区别
- hashset是由一个hash表来实现的，因此它的元素是无序的，add，remove，contains方法的时间复杂度是 O(1)
- treeset是由一个树形结构来实现的，它里面的元素是有序的，因此，add，remove，contains方法的时间复杂度是 O(logn）
（3）hashmap不能保证有序
插入顺序与存储顺序不一致
- 插入循序 == 用户操作顺序
- 存储顺序 == hash散列的索引顺序（随机性、均匀性）
同时，存储位置会在扩容时发生改变！
（4）hashmap三种遍历方法
- 通过HashMap.entrySet()得到键值对集合；
- 通过HashMap.keySet()获得键的Set集合；
- 通过HashMap.values()得到“值”的集合
巨人的肩膀：
https://blog.csdn.net/ethan_199402/article/details/107001112
https://blog.csdn.net/u012501054/article/details/103710171/
https://blog.csdn.net/AlohaHeja/article/details/90576432
https://blog.csdn.net/qq_36520235/article/details/82417949
网友评论