源码分析
变量解释
约定前面的数组结构的每一个格格称为桶
约定桶后面存放的每一个数据称为bin
transient int size;HashMap中存放KV的数量（为链表和树中的KV的总和）
int threshold; 如果当前size超过threshold，会调用resize方法
（capacity * load factor）
final float loadFactor;装载因子，默认值为0.75f。计算HashMap的实时装载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity。
final int capacity() {
return (table != null) ? table.length :
(threshold > 0) ? threshold :
DEFAULT_INITIAL_CAPACITY;
}
capacity:HashMap中桶的数量。默认值为16
重要函数解析（JDK1.7）
put
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
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);
}
indexFor
static int indexFor(int h, int length) {
return h & (length-1);
}
最常见的取hash算法是value mod length，而这里用的是‘&’运算
分析：HashMap的capacity都是2的幂，length-1转换成二进制就全是1，例如（16的容量，length-1就为1111），这样&运算的话，参与运算的另一个成员的每位是什么，运算结果就是什么。假设与hash值参与运算的某一位为0，那么不管hash的对应的那一位是什么，对应的运算结果位都为0，造成hash冲突。
&运算的好处
- 1.length（2的整数次幂）的特殊性导致了length-1的特殊性（二进制全为1）
- 位运算快于十进制运算，hashmap扩容也是按位扩容，所以相比较就选择了后者
put过程
- 首先检测table是否为空，为空则创建一个数组
- 判断key是否为null。若为null，特殊处理，创建一个（key为null）hash值为0的k-v对
- 算出key所对应的hash值，找出数组中对应的下标i
- 遍历table[i]是否存在相同的键值，如果相同则覆盖，返回一个老value值
- 如果没有一样的，调用addEntry()，判断在插入之前的size是否超过threshold，如果超过就调用resize()扩容两倍的长度,注意扩容的顺序，扩容之前old1->old2->old3，扩容之后old3->old2->old1
- 如果扩容了，因为数组的长度变了，需要重新计算下标。
- 插入：注意插入的顺序，原先table[index]的链表比如 old1->old2->old3，插入新值之后为new1->old1->old2->old3.
1.7之前是头插法，1.8之后是尾插法。因为1.8是数组+ 链表+红黑树（table[i]超过8个），效率变高，之前头插法是因为如果链表接了10000个，尾插法遍历太多。
resize
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);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
transfer
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; ---------------------(1)
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;
} // while
}
get
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
get过程：
- 如果key为null，则在table[0]寻找
- 否则计算key对应的hash，找到在table表中的下标
- 遍历table[i]的链表，通过hash和equals找到Entry
- 得到entry中的value
多线程为什么导致死循环
- size超过当前最大容量*负载因子时候会发生resize
- 两个线程同时执行了resize的方法（transfer()），在各自内部线程的栈里都生成了局部的table。
比如： - 扩容前 table[i] - >3 - > 7 - > null
- 需要扩容了，transfer方法：
- 线程1： e指向3,nexr指向7 暂时挂起
- 线程2：完成扩容，table[j] = 7 -> 3 - > null
- 线程1获取时间片，继续执行循环，这时把table[j] - >3 -> null，此时e指向7，next指向3；
然后继续插入，table[j] -> 7 -> 3 - >null，但是此时7的next已经是3，不是null了，则继续循环3；
e指向3，next为null；循环之后，3指向7；
互相指向，以后一旦执行到遍历next操作，会死循环，cpu占用率到100%
网友评论