1、HashMap 中定义了几个常量:
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;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
- DEFAULT_INITIAL_CAPACITY: 初始容量，也就是默认会创建 16 个箱子，箱子的个数不能太多或太少。如果太少，很容易触发扩容，如果太多，遍历哈希表会比较慢。
- MAXIMUM_CAPACITY: 哈希表最大容量，一般情况下只要内存够用，哈希表不会出现问题。
- DEFAULT_LOAD_FACTOR: 默认的负载因子。因此初始情况下，当键值对的数量大于 16 * 0.75 = 12 时，就会触发扩容。
- TREEIFY_THRESHOLD: 上文说过，如果哈希函数不合理，即使扩容也无法减少箱子中链表的长度，因此 Java 的处理方案是当链表太长时，转换成红黑树。这个值表示当某个箱子中，链表长度大于 8 时，有可能会转化成树。
- UNTREEIFY_THRESHOLD: 在哈希表扩容时，如果发现链表长度小于 6，则会由树重新退化为链表。
- MIN_TREEIFY_CAPACITY: 在转变成树之前，还会有一次判断，只有键值对数量大于 64 才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。
2、put方法
- 1、使用i = (n - 1) & hash方式进行桶定位
- 2、判断桶是否为链表还是红黑树
- 3、如果为链表，进一步判断是否需要将链表转为红黑树
- 4、是否强制更新
- 5、是否需要扩容
onlyIfAbsent：onlyIfAbsent=true时，如果map中存在对应的key值，则放弃修改
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//如果当前存储元素的数组为空时，使用resize方法进行初始化
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);//使用i = (n - 1) & hash方式进行桶定位，如果桶为空，表明为该桶位的第一个元素
else {
Node<K,V> e; K k;//走到此处说明，对应桶位中以存在元素，
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//与桶中第一个元素hash码相同，为同一个内存地址key，或者key相同（equals）
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 == null）添加元素
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);//如果桶中链表的元素大于链表转红黑树的阈值，则将链表转为红黑树，提升性能
break;
}
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)
e.value = value;//onlyIfAbsent == false时，表示强制修改
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//map的结构变化次数加1
if (++size > threshold)
resize();//threshold的值="容量*加载因子"，map尺寸到达threshold，会进行扩容
afterNodeInsertion(evict);
return null;
}3、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; // 新数组的容量，新数组的扩容阀值都初始化为0
if (oldCap > 0) { // 如果老数组长度大于0，说明已经存在元素
// PS1
if (oldCap >= MAXIMUM_CAPACITY) { // 如果数组元素个数大于等于限定的最大容量（2的30次方）
// 扩容阀值设置为int最大值（2的31次方 -1 ），因为oldCap再乘2就溢出了。
threshold = Integer.MAX_VALUE;
return oldTab; // 返回老的元素数组
}
/*
* 如果数组元素个数在正常范围内，那么新的数组容量为老的数组容量的2倍（左移1位相当于乘以2）
* 如果扩容之后的新容量小于最大容量 并且 老的数组容量大于等于默认初始化容量（16），那么新数组的扩容阀值设置为老阀值的2倍。（老的数组容量大于16意味着：要么构造函数指定了一个大于16的初始化容量值，要么已经经历过了至少一次扩容）
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// PS2
// 运行到这个else if 说明老数组没有任何元素
// 如果老数组的扩容阀值大于0，那么设置新数组的容量为该阀值
// 这一步也就意味着构造该map的时候，指定了初始化容量。
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 能运行到这里的话，说明是调用无参构造函数创建的该map，并且第一次添加元素
newCap = DEFAULT_INITIAL_CAPACITY; // 设置新数组容量 为 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 设置新数组扩容阀值为 16*0.75 = 12。0.75为负载因子（当元素个数达到容量了4分之3，那么扩容）
}
// 如果扩容阀值为0 （PS2的情况）
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE); // 参见：PS2
}
threshold = newThr; // 设置map的扩容阀值为 新的阀值
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的数组（对于第一次添加元素，那么这个数组就是第一个数组；对于存在oldTab的时候，那么这个数组就是要需要扩容到的新数组）
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 将该map的table属性指向到该新数组
if (oldTab != null) { // 如果老数组不为空，说明是扩容操作，那么涉及到元素的转移操作
for (int j = 0; j < oldCap; ++j) { // 遍历老数组
Node<K,V> e;
if ((e = oldTab[j]) != null) { // 如果当前位置元素不为空，那么需要转移该元素到新数组
oldTab[j] = null; // 释放掉老数组对于要转移走的元素的引用（主要为了使得数组可被回收）
if (e.next == null) // 如果元素没有有下一个节点，说明该元素不存在hash冲突
// PS3
// 把元素存储到新的数组中，存储到数组的哪个位置需要根据hash值和数组长度来进行取模
// 【hash值 % 数组长度】 = 【 hash值 & （数组长度-1）】
// 这种与运算求模的方式要求 数组长度必须是2的N次方，但是可以通过构造函数随意指定初始化容量呀，如果指定了17,15这种，岂不是出问题了就？没关系，最终会通过tableSizeFor方法将用户指定的转化为大于其并且最相近的2的N次方。 15 -> 16、17-> 32
newTab[e.hash & (newCap - 1)] = e;
// 如果该元素有下一个节点，那么说明该位置上存在一个链表了（hash相同的多个元素以链表的方式存储到了老数组的这个位置上了）
// 例如：数组长度为16，那么hash值为1（1%16=1）的和hash值为17（17%16=1）的两个元素都是会存储在数组的第2个位置上（对应数组下标为1），当数组扩容为32（1%32=1）时，hash值为1的还应该存储在新数组的第二个位置上，但是hash值为17（17%32=17）的就应该存储在新数组的第18个位置上了。
// 所以，数组扩容后，所有元素都需要重新计算在新数组中的位置。
else if (e instanceof TreeNode) // 如果该节点为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; // 按命名来翻译的话，应该叫高位首尾节点
// 以上的低位指的是新数组的 0 到 oldCap-1 、高位指定的是oldCap 到 newCap - 1
Node<K,V> next;
// 遍历链表
do {
next = e.next;
// 这一步判断好狠，拿元素的hash值 和 老数组的长度 做与运算
// PS3里曾说到，数组的长度一定是2的N次方（例如16），如果hash值和该长度做与运算，结果为0，就说明该hash值小于数组长度（例如hash值为7），
// 那么该hash值再和新数组的长度取摸的话mod值也不会放生变化，所以该元素的在新数组的位置和在老数组的位置是相同的，所以该元素可以放置在低位链表中。
if ((e.hash & oldCap) == 0) {
// PS4
if (loTail == null) // 如果没有尾，说明链表为空
loHead = e; // 链表为空时，头节点指向该元素
else
loTail.next = e; // 如果有尾，那么链表不为空，把该元素挂到链表的最后。
loTail = e; // 把尾节点设置为当前元素
}
// 如果与运算结果不为0，说明hash值大于老数组长度（例如hash值为17）
// 此时该元素应该放置到新数组的高位位置上
// 例：老数组长度16，那么新数组长度为32，hash为17的应该放置在数组的第17个位置上，也就是下标为16，那么下标为16已经属于高位了，低位是[0-15]，高位是[16-31]
else { // 以下逻辑同PS4
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;
newTab[j + oldCap] = hiHead; // 例：hash为 17 在老数组放置在0下标，在新数组放置在16下标； hash为 18 在老数组放置在1下标，在新数组放置在17下标；
}
}
}
}
}
return newTab; // 返回新数组
}
3、get
public V get(Object key) {
Node<K,V> e;
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) {//根据算法 (n - 1) & hash 定位桶
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))//与首个元素的key相同，直接返回
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))))//桶为链表，则循环对应key值
return e;
} while ((e = e.next) != null);
}
}
return null;
}
4、HashMap中keyset遍历与entryset遍历的性能差异
keyset遍历
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
entryset遍历
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}结论：使用keyset遍历，需要进一步使用map.get（key）获取value，这样会导致get时的桶定位和链表的遍历的性能开销，导致性能不如entryset遍历
