MyHashMap/README.md

# HashMap笔记

## Node类
Node类有hash、key、value、下一个节点地址等4个属性，可以构成一个单项链表，为HashMap中存储数据的基本类型

```java
static class Node<K,V> implements Map.Entry<K,V> {
    // 经过计算之后的hash值
    final int hash;
    final K key;
    V value;
    // 链表中下一个节点的地址
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}
```

## TreeNode类
TreeNode类可以构成一个红黑数，为HashMap中链表树化之后的类型；

```java
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K, V> parent;  // red-black tree links
    TreeNode<K, V> left;
    TreeNode<K, V> right;
    TreeNode<K, V> prev;    // needed to unlink next upon deletion
    boolean red;

    TreeNode(int hash, K key, V val, Node<K, V> next) {
        super(hash, key, val, next);
    }
}
```
## HashMap属性

### hash表

HashMap中有个table属性，用于存储键值对数据，即是hash表。
其类型为Node数组，数组中每个位置称为桶，桶中保存链表或者红黑树的头节点地址，组成了一个二维的数据结构，
数组的长度即为HashMap的表容量
``` 
transient Node<K,V>[] table;
```

### 默认初始容量

默认为16，即不指定初始容量的情况下，hash表数组长度为16
```
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
```

### 最大初始容量
``` 
static final int MAXIMUM_CAPACITY = 1 << 30;
```

### 默认负载因子

负载因子用于计算hash表扩容值，当hash表桶数量大于 **负载因子与表容量的乘积** 时，需要对hash表进行扩容
``` 
static final float DEFAULT_LOAD_FACTOR = 0.75f;
```

###链表树化阈值

当hash表某个桶中的链表元素大于树化阈值的时候，且桶个树大于树化最小表容量的时候，就要将这个链表转化为红黑树。
这个值必须大于2，并且应该至少为8，
``` 
static final int TREEIFY_THRESHOLD = 8;
```

### 非树化阈值

hash表某个桶中保存的是红黑树且树的节点个数小于非树化阈值的时候，红黑树将转化为链表
这个值应小于链表树化阈值，且最多为6
``` 
static final int UNTREEIFY_THRESHOLD = 6;
```

### 树化最小表容量

链表树化前需要判断是否达到了最小表容量，即判断hash表的大小是否大于这个值，
这个值应该大于等于4倍链表树化阈值，以避免调整大小和树化阈值之间的冲突
``` 
static final int MIN_TREEIFY_CAPACITY = 64;
```

### 负载因子

HashMap中空值扩容阈值的属性
``` 
final float loadFactor;
```

### 扩容阈值

控制hash表扩容的阈值，该值通过 负载因子 * hash表容量计算得到。
初始化的时候不指定表容量，这个值为0，初始化时指定表容量，这个值等于计算后的表容量，
但是第一次put的时候会将表容量与负载因子相乘计算并给这个树形重新赋值
``` 
int threshold;
```

### hash表操作次数

put、remove、merge、clear等操作都会使得该值增加，
在foreach、replaceAll等会影响hash表结构的操作期间，会判断这个值是否变化
，如果变化了，会快速失败
``` 
transient int modCount;
```

## hash表索引计算&表容量为2的幂次方原因
元素在放入hash表中某个桶的时候，需要通过hash算法计算出桶位置，即hash表索引（数组下标）。
计算公式为 **hash & (table.length - 1)**。

如果hash表容量为2的幂次方，即table.length = 2^n，那么该公式即为计算hash值除以表容量后的余数。
通过%同样可以获取到余数，但是位运算更加高效，所以这里需要限定hash表容量必须是2的幂次方。

通过表索引公式，可以将任意hash值转变为0到表容量范围的整数，可以通过该整数直接为元素分配存储的桶。

通过简单的代码对公式可以进行验算：
```java
public class Test {
    public static void main(String[] args) {
        int length = 16;
        for (int i = 0; i < 50; i++) {
            int hash = i & (length - 1);
            System.out.println(i + " -> " + hash);
        }
    }
}
```

## hash计算
HashMap中用于索引计算的hash值不是key的hash值，而是通过hash计算方法得到的。
算法为hash值异或hash值无符号右移16位后的值。

hash无符号右移16位之后，高16位会变为0，异或计算不会改变原hash值的高16位，但是会改变低16位，
将高16位与低16的特征将结合，使得hash值的低16位更加散列

当两个hash值高位不同，但是低位相同的时候，通过hash索引算法，高位会被屏蔽，得到的结果是相同的，
容易造成hash冲突，将低位特征与高位特征相结合可以减少hash冲突提高效率

```
 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    } 
```

## 扩容 

在HashMap添加数据的时候会做扩容判断，如**HashMap#putVal**方法中：
``` 
    // size：hash表容量，即table数组的长度
    // threshold：扩容阈值，一般为0.75倍表容量
    if (++size > threshold){
        resize();
    }
```
HashMap的扩容逻辑在 **HashMap#resize** 方法中。
``` 
// oldCap：旧表容量
// newCap：新表容量
// newThr 、oldThr：新旧扩容阈值
 if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
                //扩容，新表容量*2 ，新阈值*2
                newThr = oldThr << 1;
            }
        } 
```
hash表容量限定都是2的幂次方，扩容时直接按位左移一位，即表容量乘以2.
但是在扩容之后，表容量变化了，表索引的计算结果也会改变。此时需要重新hash，并移动元素保存位置。
对于同一个链表的节点来说，索引计算结果也会改变，所以链表的节点也会移动位置。

但是容量以及索引计算公式都与2的幂次方有关，所以节点移动只有两种结果：
1是位置不变，2是移动到 **当前索引 + 旧容量值** 的桶上。
``` 
 if (oldTab != null) {
            //oldCap：旧表容量，遍历旧表数组，移动元素到新表上
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null){
                        // 重新hash
                        newTab[e.hash & (newCap - 1)] = e;
                    }else if (e instanceof TreeNode){
                        //移动红黑树节点
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    }else {
                        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) {
                                // 如果hash按位与旧容量值为0，则元素在新表中对应的桶位置不需要改变
                                if (loTail == null){
                                    loHead = e;
                                } else{
                                    loTail.next = e;
                                }
                                loTail = e;
                            } 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;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
```

## 链表树化
当hash表中某个桶内的链表节点过多时，需要将链表转换为红黑树以提高查询效率，如在**HashMap#putVal**方法中：
``` 
    //该循环体逻辑为：插入节点数据时，在hash表某个桶上的链表知道key值相同的节点或者找到节点末尾空位
    //binCount：当前链表节点数量
    //TREEIFY_THRESHOLD：链表树化阈值
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            //在链表末尾添加节点
            p.next = newNode(hash, key, value, null);
            //链表中节点数量大于树化阈值，
            if (binCount >= TREEIFY_THRESHOLD - 1) {
                treeifyBin(tab, hash);
            }
            break;
        }
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
            break;
        }
        p = e;
    }
```
在向hash表中插入数据的时候，如果插入位置是同一个桶的链表，那么会根据链表树化阈值，判断是否需要进行树化，
树化方法为**HashMap#treeifyBin**，在树化方法中还要先判断hash表容量是否大于最小树化表容量（默认为64），
否则不会进行树化，而是进行表扩容。
``` 
 final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        // 如果表容量小于最小树化表容量，那么会先扩容，不会进行树化
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            //重新hash扩容
            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);
        }
    }
```