# HashMap

**Repository Path**: lyon_zhao/hash-map

## Basic Information

- **Project Name**: HashMap
- **Description**: HashMap 源码的一些解析
- **Primary Language**: Java
- **License**: MulanPSL-1.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-11-23
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

### HashMap的扩容

条件：当存储的元素数量达到阈值，就会触发扩容。

方法：resize（）；

扩容细节:每次扩容hash表（数组）的长度*2，默认16，扩容32，再扩容64



源码详解：

```java
/*
	功能：
		1.初始化数组，首次put调用resize()初始化，创建数组长度16
		2.数组扩容，不是首次调用resize()，扩容
*/
final Node<K,V>[] resize() {
  //方便操作，将hash表数组赋值给成员变量 oldTab
    Node<K,V>[] oldTab = table;
  //当oldTab为null，说明长度为0，不等于null就把长度赋值给oldCap。
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
  //阈值赋值给oldThr
    int oldThr = threshold;
  //初始化两个变量 newCap：新数组的长度。newThr：新数组的阈值
    int newCap, newThr = 0;
  //hash表数组的长度大于0？是：现在是扩容操作  否：现在是初始化操作
    if (oldCap > 0) {
      //扩容时，如果你的数组长度已经达到1073741824那就不允许再扩容了，如果再扩容的话就是2147483648，明显超出了数组的int类型的索引的上限值，（int类型的最大值为//2147483647）因此，是不允许扩容的。
        if (oldCap >= MAXIMUM_CAPACITY) {//1073741824
          //将阈值设置为int类型的最大值，
            threshold = Integer.MAX_VALUE; //2147483647
          //因为无法扩容了，所以就返回原数组，虽然无法扩容了，但是存还是可以存数据的额
            return oldTab;
        }
      //如果 老数组长度左移（乘以2）之后小于1073741824并且老长度大于等于初始化的容量16， 则扩容。
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
          //让阈值为老阈值左移1位，相当于新阈值=老阈值*2
            newThr = oldThr << 1; // double threshold
    }
  //如果老的阈值大于0，数组的长度等于0，则让阈值成为数组的长度
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
  //如果数组的长度等于0，阈值也等于0，则说明是第一次执行resize（）操作则初始化数组。
    else {               // zero initial threshold signifies using defaults
      //把16赋值给新数组的长度
        newCap = DEFAULT_INITIAL_CAPACITY;
			//将加载因子*数组默认长度赋值给新数组的阈值，新阈值=0.75*16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
  //当新的阈值等于0的时候
    if (newThr == 0) {
      //就让新的数组长度*0.75计算出临时阈值
        float ft = (float)newCap * loadFactor;
      //如果你的新数组长度和临时阈值均小于1073741824，就说明是正常的情况，就让临时阈值成为新阈值，否则让int最大值成为阈值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
  //让新的阈值成为hash表数组阈值
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})//消除警告
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //扩容以后重新计算每个元素的位置
    //初始化的时候oldTab才为null
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            /*
            	1.e为null
            	2.e为Node（只有一个元素）
            	3.e为链表
            	4.e为红黑树
            */
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //当前是e为Node（只有一个元素）
                if (e.next == null)
                    //寻址算法
                    newTab[e.hash & (newCap - 1)] = e;
                //如果e不是Node，是TreeNode（红黑树）
                else if (e instanceof TreeNode（红黑树）)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //e既不是一个元素，也不是null，也不是红黑树，e只能是链表
                else { // preserve order
                    //loHead：不换位置链表的头结点  loTail：不换位置链表的尾结点
                    //loHead：要换位置链表的头结点  loTail：要换位置链表的尾结点
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        //获取到当前链表的下一个节点
                        next = e.next;
                        //当前的node的第5个位置为0，代表不换位置
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                //不换位置的node放到头部
                                loHead = e;
                            else
                                //不换位置的node放到尾部
                                loTail.next = e;
                            loTail = e;
                        }
                        //当前的节点第5个位置为1，代表要换位置
                        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;
                    }
                }
            }
        }
    }
    return newTab;
}
```