1、前序

1.1、TreeMap分析

1. 时间复杂度（平均）

   • 添加、删除、搜索：O(logn)

2. 特点

   • Key 必须具备可比较性
   • 元素的分布是有顺序的

3. 在实际应用中，很多时候的需求

   • Map 中存储的元素不需要讲究顺序
   • Map 中的 Key 不需要具备可比较性

4. 不考虑顺序、不考虑 Key 的可比较性，Map 有更好的实现方案，平均时间复杂度可以达到 O(1)
   • 那就是采取来实现 Map

1.2、需求

• 设计一个写字楼通讯录，存放所有公司的通讯信息
  • 座机号码作为key（假设座机号码最长是 8 位），公司详情（名称、地址等）作为value
  • 添加、删除、搜索的时间复杂度要求是O(1)

上面看到有key和value，我们可以想到可以使用TreeMap来实现，但是还有一个条件必须添加、删除、搜索的时间复杂度要求是O(1)，但是TreeMap时间复杂度是log级别的，所以不能满足。
现在搞一个Comany对象数组，一个Comany对象就代表一个公司, 实现它的添加、删除、搜索，都是O(1)

• 上面Comany实现的是存在什么问题？
  • 空间复杂度非常大
  • 空间使用率极其低，非常浪费内存空间
  • 其实数组companies就是一个哈希表，典型的【空间换时间】

2、哈希表（Hash Table）

• 哈希表也叫做散列表（ hash 有“剁碎”的意思）

• 它是如何实现高效处理数据的？

  • put("Jack", 666);
  • put("Rose", 777);
  • put("Kate", 888);

• 添加、搜索、删除的流程都是类似的

  1. 利用哈希函数生成 key 对应的 indexO(1)
  2. 根据 index 操作定位数组元素O(1)
     

• 哈希表是【空间换时间】的典型应用
• 哈希函数，也叫做散列函数
• 哈希表内部的数组元素，很多地方也叫Bucket（桶），整个数组叫Buckets或者Bucket Array

3、哈希冲突（Hash Collision）

• 哈希冲突也叫做哈希碰撞
  • 2 个不同的 key，经过哈希函数计算出相同的结果

  • key1 ≠ key2 ，hash(key1) = hash(key2)

    
    
• 解决哈希冲突的常见方法

1. 开放定址法（Open Addressing）
   按照一定规则向其他地址探测，直到遇到空桶
2. 再哈希法（Re-Hashing）
   设计多个哈希函数
3. 链地址法（Separate Chaining）
   比如通过链表将同一index的元素串起来

4、JDK1.8的哈希冲突解决方案

• 默认使用将元素串起来

• 在添加元素时，可能会由转为来存储元素
  比如当哈希表容量 ≥ 64 且的节点数量大于 8 时

• 当节点数量少到一定程度时，又会转为

• JDK1.8中的哈希表是使用+解决哈希冲突

思考：这里为什么使用单链表？
每次都是从头节点开始遍历
单向链表比双向链表少一个指针，可以节省内存空间

5、哈希函数

• 哈希表中哈希函数的实现步骤大概如下

  1. 先生成key的哈希值（必须是整数）
  2. 再让key的哈希值跟数组的大小进行相关运算，生成一个
     

• 为了提高效率，可以使用&位运算取代%运算【前提：将数组的长度设计为（）】
  

• 良好的哈希函数
  让哈希值更加均匀分布减少哈希冲突次数提升哈希表的性能

5.1、如何生成key的哈希值

• key的常见种类可能有

  • 整数、浮点数、字符串、自定义对象
  • 不同种类的key，哈希值的生成方式不一样，但目标是一致的
    • 尽量让每个key的哈希值是唯一的
    • 尽量让key的所有信息参与运算

• 在Java中，HashMap的key必须实现hashCode、equals方法，也允许key为null
  

• 整数

  • 整数值当做哈希值
  • 比如10的哈希值就是10

• 浮点数

  • 将存储的二进制格式转为整数值

5.2、Long和Double的哈希值

• >>> 和 ^ 的作用是？
  • 高32bit和低32bit混合计算出32bit的哈希值
  • 充分利用所有信息计算出哈希值

5.3、字符串的哈希值

• 整数 5489 是如何计算出来的？

  • $5 ∗ 10{^3} + 4 ∗ 10{^2} + 8 ∗ 10{^1} + 9 ∗ 10{^0} $

• 字符串是由若干个字符组成的

  • 比如字符串 jack，由 j、a、c、k 四个字符组成（字符的本质就是一个整数）
  • 因此，jack 的哈希值可以表示为$j ∗ n{^3} + a ∗ n{^2} + c ∗n{^1} + k ∗ n{^0}$，等价于[ ( j ∗ n + a ) ∗ n + c ] ∗ n + k
  • 在JDK中，乘数 n 为 31，为什么使用 31？
    31是一个奇素数，JVM会将31 * i优化成(i << 5) – i
    

5.4、关于31的探讨

31 * i = (2^5 – 1) * i = i * 2^5 – i = (i << 5) – i

• 31不仅仅是符合2^n – 1，它是个奇素数（既是奇数，又是素数，也就是质数）
  1. 素数和其他数相乘的结果比其他方式更容易产成唯一性，减少哈希冲突
  2. 最终选择31是经过观测分布结果后的选择

int i =10;
System.out.println(31 * i);//310
System.out.println((i << 5) - i);//310

5.5、自定义对象的哈希值

5.6、自定义对象作为key

1. 自定义对象作为key，最好同时重写hashCode、equals方法

2. equals ：用以判断 2 个key是否为同一个key
   2.1. 自反性：对于任何非null的 x，x.equals(x)必须返回true
   2.2. 对称性：对于任何非null的 x、y，如果 y.equals(x) 返回true，x.equals(y)必须返回true
   2.3. 传递性：对于任何非null的 x、y、z，如果x.equals(y)、y.equals(z)返回true，那么x.equals(z)必须返回true
   2.4. 一致性：对于任何非null的 x、y，只要equals的比较操作在对象中所用的信息没有被修改，多次调用x.equals(y)就会一致地返回true，或者一致地返回false
   2.5. 对于任何非null的 x，x.equals(null)必须返回false

3. hashCode：必须保证equals为true的 2 个 key 的哈希值一样。反过来 hashCode相等的key，不一定equals为true

4. 不重写hashCode方法只重写equals会有什么后果？
   可能会导致 2 个equals为true的 key同时存在哈希表中

6、代码实现：

实现一个 HashMap，我们简单一下，在数组的位置上只存红黑树，不存单向链表，而且数组的那个位置存的是红黑树的根节点。
HashMap里的size是所有红黑树总节点数。

6.1、创建HashMap类

这里创建HashMap类实现Map接口，里面跟TreeMap类一样需要添加红黑树节点

public class HashMap<K, V> implements Map<K, V> {
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    private static final int DEFAULT_CAPACITY = 1 << 4;// 16
    private int size;
    private Node<K,V>[] table;
    
    public HashMap() {
        table = new Node[DEFAULT_CAPACITY];
    }
    ......

    private static class Node<K, V> {
        K key;
        V value;
        boolean color = RED;
        Node<K, V> left;
        Node<K, V> right;
        Node<K, V> parent;
        public Node(K key, V value, Node<K, V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
        
        public boolean isLeaf() {
            return left == null && right == null;
        }
        
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }
        
        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }
        
        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }
        
        public Node<K, V> sibling() {
            if (isLeftChild()) {
                return parent.right;
            }
            
            if (isRightChild()) {
                return parent.left;
            }
            
            return null;
        }
    }
}

6.2、clear的实现

@Override
public int size() {
    return size;
}

@Override
public boolean isEmpty() {
    return size == 0;
}

@Override
public void clear() {
    if(size == 0) return;
     size = 0;
     for(int i=0;i<table.length;i++) {
         table[i] = null;
     }
}

6.3、put方法

步骤是：需要先计算索引，然后在往桶里添加。

private int index(K key) {
    // 这个key是可以支持空的,如果是空，放在0的位置
    if(key == null) return 0;
    int hash = key.hashCode();
    // 因为上面的hash是别人实现的，不能保证这个hash是均匀的，所以这里为了保险起见，这里在做一次混合运算
    hash = hash ^ (hash >>> 16);// 高16位和低16位进行运算
    return hash & (table.length -1);
}

拿到索引后，先看看索引对应的桶的位置上有没有红黑树的根节点，如果没有，就创建一个红黑树的根节点，如果有就要考虑一下放在根节点的左边还是右边。

public V put(K key, V value) {
    int index = index(key);
    // 取出index位置的红黑树根节点
    Node<K, V> root = table[index];
    if(root == null) {
        root = new Node<>(key, value, null);
        table[index] = root;//放入桶中
        size++;
        afterPut(root);// 修复红黑树的性质
        return null;
    }
    // 添加新的节点到红黑树上面
    ......
    
    return null;
}

省略的说明是索引对应的桶有红黑树的根节点。这里可以直接将TreeMap的put方法里的代码拿过来。

private int compare(K k1, K k2) {
    int h1 = k1 == null ? 0: k1.hashCode();
    int h2 = k2 == null ? 0: k2.hashCode();
    ......
    return 0;
}

所以这里处理一下：在Node节点里处理一下

/**
 * 比较key大小
 * @param k1 key1
 * @param k2 key2
 * @param h1 key1的hashCode
 * @param h2 key2的hashCode
 * @return
 */
private int compare(K k1, K k2,int h1,int h2) {
    // 比较哈希值
    int result = h1 - h2;
    if(result != 0) return result;
    // 走到这里说明它俩的哈希值相等
    // 比较equels
    if(Objects.equals(k1, k2)) return 0;
    // 哈希值相等，但是不equals
    // 比较类名
    if(k1 != null && k2 != null) {
        String k1Cls = k1.getClass().getName();
        String k2Cls = k2.getClass().getName();
        result = k1Cls.compareTo(k2Cls);
        if(result != 0) return result;
        // 同一种类型并且具备可比较性
        if(k1 instanceof Comparable) {
            return ((Comparable) k1).compareTo(k2);
        }
    }
    // 同一种类型，哈希值相等，但是不equals，但是不具备可比较性
    // k1不为null，k2为null
    // k1为null，k2不为null
    // 只能进行内存地址相减
    return System.identityHashCode(k1) - System.identityHashCode(k2);
}

6.4、get方法和containsKey方法

public V get(K key) {
    Node<K, V> node = findNode(key);
    return node != null ? node.value : null;
}

public boolean containsKey(K key) {
    return findNode(key) != null;
}

关键是这个findNode方法的实现。通过key来找到节点，先要确定key对应的桶的位置。

private Node<K, V> findNode(K key) {
    Node<K, V> node = table[index(key)];
    int h1 = key == null ? 0 : key.hashCode();
    while (node != null) {
        int cmp = compare(key, node.key,h1,node.hash);
        if(cmp == 0) return node;
        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        }
    }
    return null;
}

6.5、remove方法

这个也可以讲TreeMap里的删除逻辑拷贝过来。

public V remove(K key) {
    return remove(findNode(key));
}

private V remove(Node<K, V> node) {
    if (node == null) return null;
    
    size--;
    
    V oldValue = node.value;
    
    if (node.hasTwoChildren()) { // 度为2的节点
        // 找到后继节点
        Node<K, V> s = successor(node);
        // 用后继节点的值覆盖度为2的节点的值
        node.key = s.key;
        node.value = s.value;
        // 删除后继节点
        node = s;
    }
    
    // 删除node节点（node的度必然是1或者0）
    Node<K, V> replacement = node.left != null ? node.left : node.right;
    int index = index(node);// 获取被删除节点的索引
    
    if (replacement != null) { // node是度为1的节点
        // 更改parent
        replacement.parent = node.parent;
        // 更改parent的left、right的指向
        if (node.parent == null) { // node是度为1的节点并且是根节点
            table[index] = replacement;
        } else if (node == node.parent.left) {
            node.parent.left = replacement;
        } else { // node == node.parent.right
            node.parent.right = replacement;
        }
        
        // 删除节点之后的处理
        afterRemove(replacement);
    } else if (node.parent == null) { // node是叶子节点并且是根节点
        table[index] = null;
    } else { // node是叶子节点，但不是根节点
        if (node == node.parent.left) {
            node.parent.left = null;
        } else { // node == node.parent.right
            node.parent.right = null;
        }
        
        // 删除节点之后的处理
        afterRemove(node);
    }
    return oldValue;
}

6.6、containsValue方法

这里需要遍历每一颗红黑树，才能判断是否存在。这里使用层序遍历来实现

public boolean containsValue(V value) {
    if(size == 0) return false;
    Queue<Node<K, V>> queue = new LinkedList<>();
    for (int i = 0; i < table.length; i++) {
        if(table[i] == null) continue;
        queue.offer(table[i]);
        while (!queue.isEmpty()) {
            Node<K, V> node = queue.poll();
            if (Objects.equals(value, node.value)) return true;
            
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    return false;
}

6.7、遍历traversal方法

这里遍历其实根containsValue方法一样，需要遍历所有红黑树。

public void traversal(Visitor<K, V> visitor) {
    if (size == 0 || visitor == null) return;
    Queue<Node<K, V>> queue = new LinkedList<>();
    for (int i = 0; i < table.length; i++) {
        if(table[i] == null) continue;
        queue.offer(table[i]);
        while(!queue.isEmpty()) {
            Node<K, V> node = queue.poll();
            if(visitor.visit(node.key, node.value)) return;
            
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
}

6.8、发现问题

这里实现的HashMap使用简单的测试数据是发现不了问题的，现在使用复杂一点的测试数据来进行测试。

public class Key {

    private int value;
    
    public Key(int value) {
        this.value = value;
    }
    
    @Override
    public int hashCode() {
        return value / 10;
    }
    
    @Override
    public boolean equals(Object obj) {
        if(obj == this) return true;
        if(obj == null || obj.getClass() != getClass()) return false;
        return ((Key)obj).value == value;
    }
    
    @Override
    public String toString() {
        return "v("+ value +")";
    }
}

这里的Key只要是value相同，就认为是相同的key。

6.9、打印红黑树

在HashMap类中添加print方法，实现具体的打印红黑树的逻辑

public void print() {
    if (size == 0) return;
    for (int i = 0; i < table.length; i++) {
        final Node<K, V> root = table[i];
        System.out.println("【index = " + i + "】");
        BinaryTrees.println(new BinaryTreeInfo() {
            @Override
            public Object string(Object node) {
                return node;
            }
            
            @Override
            public Object root() {
                return root;
            }
            
            @Override
            public Object right(Object node) {
                return ((Node<K, V>)node).right;
            }
            
            @Override
            public Object left(Object node) {
                return ((Node<K, V>)node).left;
            }
        });
        System.out.println("---------------------------------------------------");
    }
}

在HashMap的内部类Node里重写toString方法

public String toString() {
    return "Node_"+key+"_"+value;
}

6.10、修改findNode方法

findNode方法里有使用到compare方法，但是这个compare方法是有些问题的，compare方法里会有根据内存地址进行比较大小，这个内存地址比较是有问题的。

private Node<K, V> findNode(K key) {
    Node<K, V> root = table[index(key)];
    return root == null ? null : findNode(root,key);
}

private Node<K, V> findNode(Node<K, V> node ,K k1) {
    int h1 = k1 == null ? 0 : k1.hashCode();
    Node<K, V> result = null;  
    while (node != null) {
        int h2 = node.hash;
        K k2 = node.key;
        // 先比较哈希值
        if(h1 > h2) {
            node = node.right;
        }else if(h1 < h2){
            node = node.left;
        }else if(Objects.equals(k1, k2)) {
            return node;
        }else if(k1 != null && k2 != null
                && k1.getClass() == k2.getClass()
                && k1 instanceof Comparable) {
            int cmp = ((Comparable) k1).compareTo(k2);
            if(cmp > 0) {
                node = node.right;
            }else if(cmp < 0) {
                node = node.left;
            }else {
                return node;
            }
        }else if(node.right != null && (result = findNode(node.right,k1)) != null){ 
            // 哈希值相等，但不具备可比较性，也不equals
            return result;
        }else if(node.left != null && (result = findNode(node.left,k1)) != null){ 
            // 哈希值相等，但不具备可比较性，也不equals
            return result;
        }else {// 找不到
            return null;
        }
    }
    return null;
}

优化一下代码：

private Node<K, V> findNode(Node<K, V> node ,K k1) {
    int h1 = k1 == null ? 0 : k1.hashCode();
    Node<K, V> result = null;  
    while (node != null) {
        int h2 = node.hash;
        K k2 = node.key;
        // 先比较哈希值
        if(h1 > h2) {
            node = node.right;
        }else if(h1 < h2){
            node = node.left;
        }else if(Objects.equals(k1, k2)) {
            return node;
        }else if(k1 != null && k2 != null
                && k1.getClass() == k2.getClass()
                && k1 instanceof Comparable) {
            int cmp = ((Comparable) k1).compareTo(k2);
            if(cmp > 0) {
                node = node.right;
            }else if(cmp < 0) {
                node = node.left;
            }else {
                return node;
            }
        }else if(node.right != null && (result = findNode(node.right,k1)) != null){ 
            // 哈希值相等，但不具备可比较性，也不equals
            return result;
        }else {// 只能往左边找
            node = node.left;
        }
    }
    return null;
}

6.11、修改put方法

public V put(K key, V value) {
    int index = index(key);
    // 取出index位置的红黑树根节点
    Node<K, V> root = table[index];
    if(root == null) {
        root = new Node<>(key, value, null);
        table[index] = root;//放入桶中
        size++;
        afterPut(root);// 修复红黑树的性质
        return null;
    }
    // 添加新的节点到红黑树上面
    Node<K, V> parent = root;
    Node<K, V> node = root;
    int cmp = 0;
    K k1 = key;
    int h1 = key == null ? 0 :key.hashCode();
    Node<K, V> result = null;
    boolean searched = false; // 是否已经搜索过这个key
    do {
        parent = node;
        K k2 = node.key;
        int h2 = node.hash;
        if (h1 > h2) {
            cmp = 1;
        } else if (h1 < h2) {
            cmp = -1;
        } else if (Objects.equals(k1, k2)) {
            cmp = 0;
        } else if (k1 != null && k2 != null 
                && k1.getClass() == k2.getClass()
                && k1 instanceof Comparable
                && (cmp = ((Comparable) k1).compareTo(k2)) != 0) {

        } else if (searched) { // 已经扫描了底层
            cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
        } else { // searched == false; 还没有扫描，然后再根据内存地址大小决定左右
            if ((node.left != null && (result = findNode(node.left, k1)) != null)
                    || (node.right != null && (result = findNode(node.right, k1)) != null)) {
                // 已经存在这个key
                node = result;
                cmp = 0;
            } else { // 不存在这个key
                searched = true;
                cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
            }
        }
        
        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        } else { // 相等
            node.key = key;
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }
    } while (node != null);

    // 看看插入到父节点的哪个位置
    Node<K, V> newNode = new Node<>(key, value, parent);
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    size++;
    
    // 新添加节点之后的处理
    afterPut(newNode);
    return null;
}

6.12、测试用例

static void test1Map(Map<String, Integer> map, String[] words) {
    Times.test(map.getClass().getName(), new Task() {
        @Override
        public void execute() {
            for (String word : words) {
                Integer count = map.get(word);
                count = count == null ? 0 : count;
                map.put(word, count + 1);
            }
            System.out.println(map.size()); // 17188
            
            int count = 0;
            for (String word : words) {
                Integer i = map.get(word);
                count += i == null ? 0 : i;
                map.remove(word);
            }
            Asserts.test(count == words.length);
            Asserts.test(map.size() == 0);
        }
    });
}

static void test1() {
    String filepath = "/Users/zuojie/eclipse-workspace/dataStructure/11-哈希表/src";
    FileInfo fileInfo = Files.read(filepath, null);
    String[] words = fileInfo.words();

    System.out.println("总行数：" + fileInfo.getLines());
    System.out.println("单词总数：" + words.length);
    System.out.println("-------------------------------------");

    test1Map(new TreeMap<>(), words);
    test1Map(new HashMap<>(), words);
//      test1Map(new LinkedHashMap<>(), words);
}

static void test2(HashMap<Object, Integer> map) {
    for (int i = 1; i <= 20; i++) {
        map.put(new Key(i), i);
    }
    for (int i = 5; i <= 7; i++) {
        map.put(new Key(i), i + 5);
    }
    Asserts.test(map.size() == 20);
    Asserts.test(map.get(new Key(4)) == 4);
    Asserts.test(map.get(new Key(5)) == 10);
    Asserts.test(map.get(new Key(6)) == 11);
    Asserts.test(map.get(new Key(7)) == 12);
    Asserts.test(map.get(new Key(8)) == 8);
}

static void test3(HashMap<Object, Integer> map) {
    map.put(null, 1); // 1
    map.put(new Object(), 2); // 2
    map.put("jack", 3); // 3
    map.put(10, 4); // 4
    map.put(new Object(), 5); // 5
    map.put("jack", 6);
    map.put(10, 7);
    map.put(null, 8);
    map.put(10, null);
    Asserts.test(map.size() == 5);
    Asserts.test(map.get(null) == 8);
    Asserts.test(map.get("jack") == 6);
    Asserts.test(map.get(10) == null);
    Asserts.test(map.get(new Object()) == null);
    Asserts.test(map.containsKey(10));
    Asserts.test(map.containsKey(null));
    Asserts.test(map.containsValue(null));
    Asserts.test(map.containsValue(1) == false);
}

static void test4(HashMap<Object, Integer> map) {
    map.put("jack", 1);
    map.put("rose", 2);
    map.put("jim", 3);
    map.put("jake", 4);     
    map.remove("jack");
    map.remove("jim");
    for (int i = 1; i <= 10; i++) {
        map.put("test" + i, i);
        map.put(new Key(i), i);
    }
    for (int i = 5; i <= 7; i++) {
        Asserts.test(map.remove(new Key(i)) == i);
    }
    for (int i = 1; i <= 3; i++) {
        map.put(new Key(i), i + 5);
    }
    Asserts.test(map.size() == 19);
    Asserts.test(map.get(new Key(1)) == 6);
    Asserts.test(map.get(new Key(2)) == 7);
    Asserts.test(map.get(new Key(3)) == 8);
    Asserts.test(map.get(new Key(4)) == 4);
    Asserts.test(map.get(new Key(5)) == null);
    Asserts.test(map.get(new Key(6)) == null);
    Asserts.test(map.get(new Key(7)) == null);
    Asserts.test(map.get(new Key(8)) == 8);
    map.traversal(new Visitor<Object, Integer>() {
        public boolean visit(Object key, Integer value) {
            System.out.println(key + "_" + value);
            return false;
        }
    });
}

static void test5(HashMap<Object, Integer> map) {
    for (int i = 1; i <= 20; i++) {
        map.put(new SubKey1(i), i);
    }
    map.put(new SubKey2(1), 5);
    Asserts.test(map.get(new SubKey1(1)) == 5);
    Asserts.test(map.get(new SubKey2(1)) == 5);
    Asserts.test(map.size() == 20);
}

public static void main(String[] args) {
    test1();
    test2(new HashMap<>());
    test3(new HashMap<>());
    test4(new HashMap<>());
    test5(new HashMap<>());
}

上面我们执行test2，test3，test4和test5都是通过的，但是执行test1是会报错的。

7、扩容

装填因子

• 装填因子（Load Factor）：节点总数量 / 哈希表桶数组长度，也叫做负载因子
• 在JDK1.8的HashMap中，如果装填因子超过0.75，就扩容为原来的2倍

private static final float DEFAULT_LOAD_FACTOR = 0.75f;

public V put(K key, V value) {
    resize();
    ......
}

下面的才是比较好的做法：

private void resize() {
    // 装填因子 <= 0.75
    if (size / table.length <= DEFAULT_LOAD_FACTOR) return;
    Node<K, V>[] oldTable = table;
    table = new Node[oldTable.length << 1];
    
    Queue<Node<K, V>> queue = new LinkedList<>();
    for(int i =0;i< oldTable.length;i++) {
        if(oldTable[i] == null) continue;
        
        queue.offer(oldTable[i]);
        while(!queue.isEmpty()) {
            Node<K, V> node = queue.poll();
            if(node.left != null) {
                queue.offer(node.left);
            }
            if(node.right != null) {
                queue.offer(node.right);
            }
            // 挪动代码得放到最后面
            moveNode(node);
        }
    }
}

private void moveNode(Node<K, V> newNode) {
    // 重置
    newNode.parent = null;
    newNode.left = null;
    newNode.right = null;
    newNode.color = RED;
    
    int index = index(newNode);
    // 取出index位置的红黑树根节点
    Node<K, V> root = table[index];
    if (root == null) {
        root = newNode;
        table[index] = root;
        afterPut(root);
        return;
    }
    
    // 添加新的节点到红黑树上面
    Node<K, V> parent = root;
    Node<K, V> node = root;
    int cmp = 0;
    K k1 = newNode.key;
    int h1 = newNode.hash;
    do {
        parent = node;
        K k2 = node.key;
        int h2 = node.hash;
        if (h1 > h2) {
            cmp = 1;
        } else if (h1 < h2) {
            cmp = -1;
        } else if (k1 != null && k2 != null 
                && k1 instanceof Comparable
                && k1.getClass() == k2.getClass()
                && (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
        } else {
            cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
        }
        
        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        }
    } while (node != null);

    // 看看插入到父节点的哪个位置
    newNode.parent = parent;
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    
    // 新添加节点之后的处理
    afterPut(root);
}

8、TreeMap VS HashMap

• 何时选择TreeMap？
  元素具备可比较性且要求升序遍历（按照元素从小到大）
• 何时选择HashMap？
  无序遍历

代码链接