键值对Map-02

1.jdk1.7 和 jdk1.8 中 HashMap？

jdk1.7:

• 底层采用数组+链表
• 数组长度默认是 16，加载因子是 0.75，阈值是 0.75*16=12，当发生冲突时，会以链表的形式存储新的数据，新的数据插入到链表的头部，将新来的值赋值给当前位置的数组。
• 当数组中的 12 个位置被占据时，同时新插入的数据位置不为空，需要进行 2 倍扩容。
• 并发环境会产生死锁。头插法会使链表发生反转，多线程环境下会产生环.

jdk1.8:

• 底层采用数组+链表/红黑树
• 数组长度默认是 16，加载因子是 0.75，阈值是 0.75*16=12，当发生冲突时，会以链表的形式存储新的数据，新的数据插入到链表的尾部，将新来的值赋值给当前位置的数组。插入尾部也是为转换红黑树做准备，如果链表上的元素超过 8 个并且数据个数大于等于 64，则转换为红黑树。提高增删查的效率。
• 达到阈值值，直接扩容，2 倍扩容。不需要判断新元素的位置是否为空。
• 并发下不会产生思死锁，但是会出现数据覆盖。多线程下，1.8 会有数据覆盖

数据覆盖举例:
线程 A：往 index 插，index 此时为空，可以插入，但是此时线程 A 被挂起
线程 B：此时，对 index 写入数据，A 恢复后，就把 B 数据覆盖了

改动对比:

jdk1.8 的 HashMap 主要有五点优化:

数据结构：数组 + 链表改成了数组 + 链表或红黑树

原因：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由 O(n)降为 O(logn)

链表插入方式：链表的插入方式从头插法改成了尾插法

简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后。

原因：因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。

扩容 rehash：扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。

原因：提高扩容的效率，更快地扩容。

扩容时机：在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；

散列函数：1.7 做了四次移位和四次异或，jdk1.8 只做一次。

原因：做 4 次的话，边际效用也不大，改为一次，提升效率。

2.jdk1.7 和 jdk1.8 的扩容原理？

jdk1.7

扩容前和扩容后都是使用的公式 hash&(length-1)

整体扩容过程是取出数组元素，遍历以该数组元素为头节点的链表元素，然后计算在新数组中的下标，然后进行交换，即原来 hash 冲突的单向链表的尾部变成了扩容后单向链表的头部。

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;//这里记做第一步
            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;//这里记做第四部
        }
    }
}

transfer 函数作用:在对 table 进行扩容到 newTable 后，需要将原来数据转移到 newTable 中，注意 10-12 行代码，这里可以看出在转移元素的过程中，使用的是头插法，也就是链表的顺序会翻转，这里也是形成死循环的关键点。

• hashmap1.7 中的死循环是有多个线程并发扩容形成了环状链表，随后再进行扩容的线程会循环取这个环状链表的节点，造成死循环；
• 其次，环状链表是几个节点相互指向，并不是某个节点自己指向自己。

jdk1.8

对公式进行判断(hash&newTable)==0

jdk1.8 的扩容更加的优雅，由于扩容数组长度是 2 倍关系。假设原数组 size 是 4，扩容后为 8，左移一位是 2 倍，二进制表示为 0100 >> 1000 的变化。扩容时只需要判断原来的 hash 值和 newtable 进行与运算的结果，如果为 0，则位置保持不变，如果为 1，则在原来的位置加上原数组的长度。

如果为 true，则放在原位置

如果为 false，则放在原位置+oldCap 处

``HashMap 是线程不安全的，其主要体现:`

1. 在 jdk1.7 中，在多线程环境下，扩容时会造成环形链或数据丢失。
2. 在 jdk1.8 中，在多线程环境下，会发生数据覆盖的情况。

3.HashMap jdk1.8 扩容源码分析

HashMap 的扩容原理也挺值得说的,其中把链表分割成一条高位链表和一条低位链表分别插入到新的 2 倍空间数组中,并且不需要重新对每个 key 重新取模,低位链表还是放在原来相同的下标桶位,高位链表放在原来下标桶位+oldCap 的下标位置

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table;
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  int oldThr = threshold;
  int newCap, newThr = 0;
  // 如果table中有元素
  if (oldCap > 0) {
    // 容量是否已达限制
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    // 扩容，并更新扩容阈值
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; // double threshold
  }
  // 如果table中没有元素，但是已初始化扩容阈值，这里将table的新容量赋值为扩容阈值
  else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
  // 如果以上条件都不满足，则利用默认值进行初始化
  else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  // 这里再次对扩容阈值进行判断，如果未初始化，则进行初始化
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  @SuppressWarnings({"rawtypes","unchecked"})
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  // 如果原来table有值，则循环将原值转移到newTab中
  if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      // 找到有值的节点
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null; //将原来table中当前位置置null
        if (e.next == null) // 如果当前节点next为null，将其放置在newTab中的新位置
          newTab[e.hash & (newCap - 1)] = e;
        // 如果是红黑树则进行红黑树操作，关于红黑树后面会进行分析
        else if (e instanceof TreeNode)
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order  // 当走到这里，说明节点上为链表形式存储数据，需进行循环操作
          // 存储位置在newTable和oldTable位置不变元素
          Node<K,V> loHead = null, loTail = null;
          // 存储oldTable中位置发生了变化的元素，当然这里是和oldTable相比较
          // 参看下面的注释，应该可以很好理解
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          do {
            // 由于是链表循环，因此需存储next节点的值，这种形式在jdk1.7中出现过多次
            next = e.next;
            /**
                             *这里需要注意一下，这里是用元素的hash值，与原来table长度做&操作
                             * 如果为0，则表示e.hash&(newCap-1)和e.hash&(oldCap-1)是一样的
                             * 也就说元素的位置在newTable中是不变的，因为newTable的大小为oldTable大小的2倍
                             * 相当于其二进制向左移动了1位，其newCap-1的二进制全都为1，且比原来oldCap-1的二进制多了一个1
                             * eg:oldCap=16,newCap=32，注意求key的位置是用e.hash&(table.length-1)
                             * e.hash&0x1111=原来key的位置
                             * e.hash&0x10000=0，表明e.hash在二进制的第5位上一定为0，所以：
                             * e.hash&0x11111=也一定是原来key的位置
                             * 如果:
                             * e.hash&0x10000=1，表明e.hash在二进制的第5位上一定为1，所以：
                             * e.hash&0x11111=原来key的位置加上oldCap的长度即可（0x10000）
                             * 这样根据一个二进制位就将原来的一条链表分成两条链表进行存储，这里非常的关键，不是很好理解
                             * 仔细理解上面的解释，相信你会发现这是非常神奇的一个技巧
                             */
            // 有了上面的原理，再来看这就非常明确了
            // 元素在newTable中位置不改变
            if ((e.hash & oldCap) == 0) {
              // 初始时，将e放在loHead头上，然后尾又是e，后续循环的时候，只操作tail就行了，形成链表
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              // 尾部存储为e,形成链表，注意理解就好
              loTail = e;
            }
            // 元素在newTable中位置发生了变化[相对oldTable]
            // 这里就相当于两条链表了，位置不变的一条，位置变了的又是一条
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
            }
          } while ((e = next) != null);
          // 如果位置不变链表不为null
          if (loTail != null) {
            loTail.next = null;
            // 从这里也可看出这里存储的是元素在newTable中位置不改变[相对oldTable]
            // 只需要存储head值即可，因为已形成链表
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            // 位置变化的元素，位置只需要加上oldCap的值就可以了,上面已进行分析
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}

在 jdk1.7 源码中 HashMap 进行扩容时，hash 冲突的数组索引处的旧链表元素扩容到新数组时，如果扩容后的数组元素的位置与原数组的索引位置相同，则链表会发生倒置，在 jdk1.8 中不会出现倒置。

在 jdk1.7 中，扩容时紧紧只是重新计算了数组的下标，整体的数据结构还是数组+链表

在 jdk1.8 中，扩容时，不仅重新计算了下标，在链表长度达到 8 时，会转换为红黑树。且当前结构为红黑树，元素个数小于 6 时，会转换为链表结构。

4.jdk1.8 红黑树扩容 split 方法？

//扩容后，红黑树的hash分布，只可能存在于两个位置：原索引位置、原索引位置+oldCap
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;//拿到调用此方法的节点
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;//存储索引位置为：“原索引位置”的节点
    TreeNode<K,V> hiHead = null, hiTail = null;//存储索引位置为：“原索引+oldCap”的节点
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

5.String 类适合做 key 的原因？

在《Java 编程思想》中有这么一句话:设计 hashCode() 时最重要的因素就是对同一个对象调用 hashCode() 都应该产生相同的值。

String 类型的对象对这个条件有着很好的支持，因为 String 对象的 hashCode() 值是根据 String 对象的 内容计算的，并不是根据对象的地址计算。下面是 String 类源码中的 hashCode() 方法:String 对象底 层是一个 final 修饰的 char 类型的数组，hashCode() 的计算是根据字符数组的每个元素进行计算的，所 以内容相同的 String 对象会产生相同的散列码

HashMap 内部实现是通过 key 的 hashCode 来确定 value 的位置的。

• String 天生复写了 hashCode 方法，根据 String 的内容来计算 hashCode。

• 因为字符串是不可变的，当创建字符串时，它的 hashCode 被缓存下来，不需要再次计算，所以相比于其他对象更快。

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
}

6.自定义的对象作为 key？

需要重写 hashCode 方法和 equals 方法。

当 HashMap 存入 k1 的时候，会执行 hashCode 方法，因为没有重写 hashCode 方法，会去 Object 类找 hashCode 方法，而 object 类的 hashCode 方法返回的时对象的地址。这时候用 k2 去获取，用相同的方式去获取 hashCode 方法，因为内存地址不一样，所以 hashCode 不一样。

即使 hashCode 一致，在 hash 冲突的情况下，需要调用 equals 方法进行对比，因为没有重写 equals 方法，会调用 object 的 equals 方法，object 的 equals 方法会比较内存地址是否一样，因为 k1 和 k2 时 new 出来的，内存地址是不一样的，所以 k2 获取不到 k1 的值。因为没有重写 hashCode 方法和 equals 方法。

7.什么是 hash 冲突？

hash，一般翻译为散列，也音译为哈希。

通俗来讲就是将任意长度的字符通过散列算法，输出为固定长度的散列值，也叫 hash 值。这种散列是一种压缩映射，散列值的空间远小于原值的空间，不同的输入可能会有相同的散列值输出。所以不能仅仅通过散列值来做字符相等的判断。简单来说就是将任意长度的消息，压缩到某一固定长度消息的函数。

根据同一散列函数计算出的 hash 值不同，则输入值肯定不同，hash 值相同，输入值也可能不同。也就是 hash 冲突的情况。

在处理哈希冲突的情况下，equals 方法非常有用。当不同的对象被映射到相同的哈希值时，我们需要进一步检查它们的内容是否真的相同。这时就需要通过重写 equals 方法来定义两个对象在逻辑上的相等性。通常，重写 equals 方法会比较对象的字段内容，以确定它们是否表示相同的数据。

8.解决 hash 冲突的方式有哪些？

开放定址法:使用探测的方式在数组中找到另一个可以存储值的位置。

链地址法:也叫拉链法，HashMap 和 HashSet 都是使用的这种方式，在存在 hash 冲突的时候，使用链表或者红黑树的形式存储数据。

再散列法:hash 冲突时，通过再次散列的方式确定插入的位置，缺点是每次冲突都要计算散列，时间复杂度增加。

公共溢出区:将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

9.开发寻址法的探索方式？

线性探测:

按顺序决定哈希值时，如果某数据的哈希值已经存在，则在原来哈希值的基础上往后加一个单位，直至不发生哈希冲突。

再平方探测:

按顺序决定哈希值时，如果某数据的哈希值已经存在，则在原来哈希值的基础上先加 1 的平方个单位，若仍然存在则减 1 的平方个单位。随之是 2 的平方，3 的平方等等。直至不发生哈希冲突。

伪随机探测:

按顺序决定哈希值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来哈希值的基础上加上随机数，直至不发生哈希冲突。

10.开放地址法和拉链法的优缺点？

开放地址法:会产生堆积问题，不适合大规模的数据存储，插入时，可能会出现多次冲突的情况，删除数据时，其他数据也有影响，实现相对较为复杂。且节点规模大时，再平方探测会浪费空间。

拉链法:处理冲突简单，且无堆积现象。平均查找长度短，时间复杂度低。链表中的节点是动态申请的，适合构造表不能确定的情况。相对而言，指针域可以忽略不计，所以更节省空间。尾插法简单，只需要修改指针，不需要对其他冲突做处理。

11.负载因子为什么会影响性能？

负载因子代表了一个散列表的空间使用程度。initailCapacity*loadFactor=HashMap 的实际容量

负载因子越大，元素越多，导致扩容时机越晚,导致 hash 冲突的机会变多,从而链表变长，查询的时间复杂度增大，性能下降。HashMap 的负载因子默认是 0.75

负载因子越小，元素稀疏，空间利用率低。查找效率高。

12.HashMap 中红黑树的插入方法?

插入方法 balanceInsertion

源码及注释如下,需要注意的是参数 root 表示根节点,x 表示需要旋转的结点,返回值就是新的根节点,红黑树的插入平衡中可能会涉及根节点的改变，因此参数传入原来的根节点来修改。

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
  x.red = true;             //所有插入结点初始值都为红色
  for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //xp为x父结点，xpp为x的祖父结点，xppl为x的祖父结点的左子结点，xppr为x的祖父结点的右子结点
    if ((xp = x.parent) == null) { //插入结点是根结点，直接变黑色，返回x
      x.red = false;
      return x;
    }
    else if (!xp.red || (xpp = xp.parent) == null) //情况2，插入结点父结点为黑色
      return root; //不用操作，直接返回原来的根结点
    //下面是情况3，父结点是红结点
    if (xp == (xppl = xpp.left)) { //x的父结点是祖父结点的左子结点
      if ((xppr = xpp.right) != null && xppr.red) { //情况3.1，叔叔结点是红结点
        xppr.red = false;//x的叔叔结点变黑色
        xp.red = false; //x的父结点变为黑色
        xpp.red = true; //x的祖父结点变红色
        x = xpp;  //把祖父结点作为新的插入结点
      }
      else {
        if (x == xp.right) {//情况3.2.2叔叔结点不存在或者为黑色，插入结点x是父结点p的右子结点
          root = rotateLeft(root, x = xp); 对x的父结点左旋，把p设为插入结点,之后转到下面情况3.2.1
            xpp = (xp = x.parent) == null ? null : xp.parent;
        }
        if (xp != null) {//情况3.2.1 叔叔结点不存在或者为黑色，插入结点x是父结点p的左子结点
          xp.red = false;//x的父结点xp变黑
          if (xpp != null) {
            xpp.red = true; //x的祖父结点xpp变为红
            root = rotateRight(root, xpp); //对x的祖父结点右旋
          }
        }
      }
    }
    else { //x的父结点是祖父结点的右子结点
      if (xppl != null && xppl.red) {//情况3.1 叔叔结点是红色
        xppl.red = false;//叔叔结点变黑
        xp.red = false;//父结点变黑
        xpp.red = true;//祖父结点变红
        x = xpp;//把祖父结点设置为新的插入结点
      }
      else {
        if (x == xp.left) {//情况3.3.2叔叔结点不存在或者为黑色，插入结点x是父节点p的左子结点
          root = rotateRight(root, x = xp);//duix的父结点右旋，把p设置为新的插入结点，之后转到下面情况3.3.1
          xpp = (xp = x.parent) == null ? null : xp.parent;
        }
        if (xp != null) {//情况3.3.1 叔叔结点不存在或者为黑色，插入结点x是父结点p的右子结点
          xp.red = false;//x的父结点xp变黑
          if (xpp != null) {
            xpp.red = true;//x的祖父结点xpp变为红
            root = rotateLeft(root, xpp);//对x的祖父结点xpp左旋
          }
        }
      }
    }
  }
}

13.红黑树的特点?

• 红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：

• 每个节点要么是红色，要么是黑色；

• 根节点永远是黑色的；

• 所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；

• 每个红色节点的两个子节点一定都是黑色；

• 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

  

14.如果初始化 HashMap 为 17?

简单来说，就是初始化时，传的不是 2 的倍数时，HashMap 会向上寻找离得最近的 2 的倍数，所以传入 17，但 HashMap 的实际容量是 32。我们来看看详情，在 HashMap 的初始化中，有这样⼀段⽅法；

public HashMap(int initialCapacity, float loadFactor) {
  ...
    this.loadFactor = loadFactor;
  this.threshold = tableSizeFor(initialCapacity);
}

阀值 threshold ，通过⽅法 tableSizeFor 进⾏计算，是根据初始化传的参数来计算的。同时，这个⽅法也要要寻找⽐初始值⼤的，最⼩的那个 2 进制数值。⽐如传了 17，我应该找到的是 32。

static final int tableSizeFor(int cap) {
 int n = cap - 1;
 n |= n >>> 1;//高位不断补1
 n |= n >>> 2;//高位不断补1
 n |= n >>> 4;//高位不断补1
 n |= n >>> 8;//高位不断补1
 n |= n >>> 16;//高位不断补1
 //最后加1变为2的 n次幂
 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

MAXIMUM_CAPACITY = 1 << 30，这个是临界范围，也就是最⼤的 Map 集合。
计算过程是向右移位 1、2、4、8、16，和原来的数做|运算，这主要是为了把⼆进制的各个位置都填上 1，当⼆进制的各个位置都是 1 以后，就是⼀个标准的 2 的倍数减 1 了，最后把结果加 1 再返回即可。

那为什么必须要对cap进行-1之后再进行运算呢？如果指定的数刚好是 2 的整数次幂，如果没有-1 结果会变成比他大两倍的数

以 17 为例，看一下初始化计算 table 容量的过程:

例子 1:

例子 2:

15.为什么 key 和 value 都可以为 null

在 Java 中，HashMap 是一种散列表实现，它使用键值对的方式来存储数据。HashMap 中的每个键对应唯一的值，即 key-value 对。在 HashMap 中，key 和 value 都可以为 null，这是因为 HashMap 内部使用了哈希算法来计算 key 的散列值，并将 key-value 对存储在散列表中。如果key为null，那么在计算散列值时，会将null作为特殊值对待，并将散列值设置为0。如果value为null，那么在存储value时，HashMap会将这个null值作为一个普通的value来处理，并将它与key一起存储在散列表中。

需要注意的是，在使用 HashMap 时，如果 key 为 null，那么在进行 put、get、remove 等操作时，需要特殊处理。例如，当需要判断一个 key 是否存在时，应该使用 containsKey 方法而不是直接判断 key 是否为 null。同样地，当需要获取一个 key 对应的 value 时，也应该使用 get 方法，并在返回结果之前判断 value 是否为 null。

在使用 HashMap 时，通常建议尽量避免使用 null 值作为 key 或 value，以免造成不必要的麻烦。如果确实需要使用 null 值，那么应该注意特殊处理，并避免在程序中出现空指针异常。

16.设计实现一个 HashMap 吗？

• 散列函数：hashCode()+除留余数法
• 冲突解决：链地址法
• 扩容：节点重新 hash 获取位置

/**
 * 自定义HashMap
 *
 * @author : kwan
 * @date : 2022/8/8
 */
public class ThirdHashMap<K, V> {
  /**
     * 节点类
     */
  class Node<K, V> {
    //键值对
    private K key;
    private V value;
    //连表。后维
    private Node<K, V> next;

    private Node(K key, V value) {
      this.key = key;
      this.value = value;
    }

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

  //默认容量
  final int DEFAULT_CAPACITY = 16;
  final float LOAD_FACTOR = 0.75f;
  //HashMap的大小
  private int size;
  //桶效组
  Node<K, V>[] buckets;

  /**
     * 无参构造器，设置桶数组默认容量
     */
  public ThirdHashMap() {
    buckets = new Node[DEFAULT_CAPACITY];
    size = 0;
  }

  /**
     * 有多构造，指定桶数组容量
     */
  public ThirdHashMap(int capacity) {
    buckets = new Node[capacity];
    size = 0;
  }

  /**
     * 哈希函数，获取地址
     */
  private int getIndex(K key, int length) {
    //获取hash code
    int hashCode = key.hashCode();//和标数组长度取余
    int index = hashCode % length;
    return Math.abs(index);
  }

  /**
     * put方法
     */
  public void put(K key, V value) {
    //刺断是否需要进行打容
    if (size >= buckets.length * LOAD_FACTOR) {
      resize();
    }
    putVal(key, value, buckets);
  }

  /**
     * 将元素存入指定的node数组
     */
  private void putVal(K key, V value, Node<K, V>[] table) {
    //获取位置
    int index = getIndex(key, table.length);
    Node node = table[index];//插入的值置为空
    if (node == null) {
      table[index] = new Node<>(key, value);
      size++;
      size++;
      return;
    }
    //插入位置不为空，说明发生冲夹，使用链地址法，调历销表
    while (node != null) {
      //如果key相同，就覆盖掉
      if ((node.key.hashCode() == key.hashCode())
          && (node.key == key || node.key.equals(key))) {
        node.value = value;
        return;
      }
      node = node.next;
    }
    //当前key不在链表中，捡入链表头都
    Node newNode = new Node(key, value, table[index]);
    table[index] = newNode;
    size++;
  }

  /**
     * 扩容
     */
  private void resize() {
    //创建一个两价容量的桶数组
    Node<K, V>[] newBuckets = new Node[buckets.length * 2];
    //将当落元表主新散列到新的敬组
    rehash(newBuckets);
    buckets = newBuckets;
  }

  /**
     * 重新散列当苗元素
     */
  private void rehash(Node<K, V>[] newBuckets) {
    //map大小里新计算
    size = 0;
    //将旧的桶数组的元素全部剧到新的桶数组里
    for (int i = 0; i < buckets.length; i++) {
      //为空，跳
      if (buckets[i] == null) {
        continue;
      }
      Node<K, V> node = buckets[i];
      while (node != null) {
        //将元未放入新数组
        putVal(node.key, node.value, newBuckets);
        node = node.next;
      }
    }
  }

  /**
     * 获取元素
     */
  public V get(K key) {
    //获取key对应的地址
    int index = getIndex(key, buckets.length);
    if (buckets[index] == null) {
      return null;
    }
    Node<K, V> node = buckets[index];
    //查找链表
    while (node != null) {
      if ((node.key.hashCode() == key.hashCode())
          && (node.key == key | !node.key.equals(key))) {
        return node.value;
      }
      node = node.next;
    }
    return null;
  }

  /**
     * 返回HashMap大小
     *
     * @return
     */
  public int size() {
    return size;
  }
}