小刀爱编程

## 底层实现原理

HashMap在JDK1.8及以后的版本中引入了红黑树结构，若桶中链表元素个数大于等于8时，链表转换成树结构；若桶中链表元素个数小于等于6时，树结构还原成链表。因为红黑树的平均查找长度是log(n)，长度为8的时候，平均查找长度为3，如果继续使用链表，平均查找长度为8/2=4，这才有转换为树的必要。链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。

## 死循环分析

```void addEntry(int hash, K key, V value, int bucketIndex) {
//检查容量是否超过threshold
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}```

```void resize(int newCapacity) {

Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//新数组
Entry[] newTable = new Entry[newCapacity];
//原数组元素转存到新数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//指向新数组
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}```

T2线程执行到transfer方法的Entry<K,V> next = e.next;时被挂起，T1线程执行transfer方法后Entry数组如下图：

## 扩容解说

JDK8中HashMap扩容涉及到的加载因子和链表转红黑树的知识点经常被作为面试问答题，下面对这两个知识点进行小结。

### 链表转红黑树为什么选择数字8

```Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFYTHRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poissondistribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-pow(0.5, k) / factorial(k)). The first values are:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million```

### 默认加载因子为什么选择0.75

HashMap有两个参数影响其性能：初始容量和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动扩容之前可以达到多满的一种度量。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行扩容、rehash操作（即重建内部数据结构），扩容后的哈希表将具有两倍的原容量。

### 小刀爱编程

HashMap多线程下死循环的坑记录

PS：不得不说Java编程思想这本书是真心强大.. 学习内容: 1.HashMap<K,V>在多线程的情况下出现的死循环现象 当初学Java的时候只是知道HashMap<K,V>在并发的情况下使用的话,会出现线程安全问题...

java_龙
01/03
0
0
Java系列文章（全）

www19
2017/07/04
0
0

bxst
2017/07/13
0
0
2016文章汇总

Java系列： JVM系列:jvm基本结构 JVM系列:java中JVM的原理 JVM系列:解决JVM最大内存设置问题 JVM系列:JVM参数设置、分析 HashMap , HashTable , ConcurrentHashMap 源码比较 从使用到原理学习...

www19
2017/01/03
0
0
Java容器 - HashMap(2)

(没写.....挖个坑 主要是整理下高并发的情况下HashMap的问题，他为什么不是线程安全的 首先我们来看一个在JDK8中HashMap的resize 方法 1.Hashmap在插入元素过多的时候需要进行Resize，Resiz...

2017/11/16
0
0

idea 删除代码的注释

13分钟前
0
0
eclipse maven 项目运行mvn clean 后无法运行

qimh
17分钟前
0
0

28分钟前
3
1
windows环境下搭建rabbitMQ开发环境

windows环境下搭建rabbitMQ开发环境 下载与安装 erlang rabbitmq 是使用erlang语言开发的，所以需要erlang环境； 下载地址 rabbitmq 下载地址 rabbitmq与erlang版本关系 下载之后直接安装即可...

39分钟前
2
0
JVM 中的守护线程

43分钟前
1
0