#### 构造函数和相关参数
```
/**
* 默认初始容量 16,必须是2的幂次方
* 为什么必须是2的幂次方
*
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 被所有实例共享的,当table还没有膨胀的时候
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
transient int hashSeed = 0;
/**
* 设置初始化容量和负载因子的构造函数
*/
public HashMap(int initialCapacity, float loadFactor) {
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;
threshold = initialCapacity;
init();
}
/**
* 设置初始化容量的构造函数
* 默认负载因子是0.75
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 默认构造函数
* 默认长度是16,默认负载因子是0.75
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
```
#### 1、JDK1.7 HashMap put()方法
```
public V put(K key, V value) {
// 空的话就进行初始化
if (table == EMPTY_TABLE) {
// put元素时才进行初始化,创建哈希表
inflateTable(threshold);
}
// 空 直接put
if (key == null)
return putForNullKey(value);
// 计算hashcode,进行异或运算,返回一个哈希值
int hash = hash(key);
// 获取数组的下标(哈希桶)
int i = indexFor(hash, table.length);
// 遍历链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 桶里有重复的key的情况
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 桶里无重复的key,新增一个
addEntry(hash, key, value, i);
return null;
}
/**
* 检索对象哈希代码,并对结果哈希应用一个补充哈希函数,该函数可抵御质量较差的哈希函 * 数。这一点很关键,因为HashMap使用两个长度哈希表的幂,会遇到在低位没有差异的哈的
* 冲突。注意:空键总是映射到哈希0,因此索引为0。
*/
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
// 异或运算,提高hashcode的散列性,使其分布更加均匀
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* 算出数组的下标
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
// hashcode的低位
// 数组的长度减1再与哈希值进行按位与
// 是2的幂次方的话,减1后的每一位都是1
/** 这里就解释了length为什么初始化时必须是2的幂次方数,为了方便计算数组的下标
* 只有它的长度是2的n次方的时候,我对它进行减1操作时才能拿到全部是1的值,再进行按位与时才能快速的得出数组的下标,并且它的分布是均匀的。
*/
return h & (length-1);
}
/**
* 为table开辟空间
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 必须是2的幂次方
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 初始化一个数组
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
// (number - 1) << 1
// 先将number变大,减-1是由于特殊情况,如果是8、16、2的幂次方的情况
// 找到一个小于等于这个数的2的最小次方数
// Integer.highestOneBit((number - 1) << 1)
}
```
put()过程:
1. 如果哈希表还未创建,那么创建哈希表
2. 如果键为null,那么调用putForNullKey插入键为null的值
3. 如果键不为null,计算hash值并得到桶中的索引数,然后遍历桶中链表,一旦找到匹配的,那么替换旧值
4. 如果桶中链表为null或链表不为null但是没有找到匹配的,那么调用addEntry方法插入新节点

扩容的逻辑:
1. 如果长度大于扩容的阈值,且要插入的哈希桶不为空的情况下进行扩容
这里是两个条件 (size >= threshold) && (null != table[bucketIndex]),有时我们往往忽视第2个条件,(null != table[bucketIndex]),如果要插入的哈希桶为空的情况下就不会进行扩容
2. 扩容后的容量是扩容前的2倍
3. 新建一个数组,然后调用transfer()方法将元素复制进去。
```
void addEntry(int hash, K key, V value, int bucketIndex) {
// 扩容逻辑
// (1)hashmap存的元素大于阈值
// (2)table[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);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
// 将新的节点加到链表的头部
Entry<K,V> e = table[bucketIndex];
//
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
/**
* 扩容
*/
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// new一个新的table,新的容量是之前的两倍
Entry[] newTable = new Entry[newCapacity];
// 问题根源,会形成循环链表,造成死锁
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* 判断是否需要rehash
*/
final boolean initHashSeedAsNeeded(int capacity) {
/*
* hashSeed 哈希种子 默认为0
* currentAltHashing 大部分情况下是 false
*/
boolean currentAltHashing = hashSeed != 0;
/*
* capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD
* capacity容量大于Integer的最大值
*/
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
void transfer(Entry[] newTable, boolean rehash) {
// 获取新数组的大小
int newCapacity = newTable.length;
// table 是扩容之前的table
for (Entry<K,V> e : table) {
// 遍历链表
while(null != e) {
// 多线程扩容的情况会形成环形链表
Entry<K,V> next = e.next;
// 是否进行rehash
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 根据新的容量计算出新的数组下标
int i = indexFor(e.hash, newCapacity);
// 相当于重新进行一次put操作
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
```
Integer的highestOneBit()方法
```
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
```
get()方法:
1. 如果键为空,直接调用getForNullKey()方法,否则调用getEntry()方法
2. 计算在哈希桶的下标,然后遍历链表,如果没有找到则返回null
```
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;
}
```
>关于在多线程环境下会造成死循环,*可以看一下下面的文章*
>疫苗:JAVA HASHMAP的死循环<br/>
>文章链接:https://coolshell.cn/articles/9606.html

JDK1.7 HashMap源码学习