《恋上数据结构与算法》笔记（十六）：HashMap、HashSet、LinkedHashMap、LinkendHashSet

墨蓝 2022-12-30 13:38 45阅读 0赞

必须要先看上一篇 : 小码哥《恋上数据结构与算法》笔记（十五）：哈希表（Hash Table）

  • 以及红黑树的实现, 因为下面的HashMap就是使用Hash表 + 红黑树来实现的

目录

  • 一、哈希表的接口设计（HashMap）

  • 二、哈希表的实现（HashMap）

    • 1、声明节点
    • 2、clean实现
    • 3、put实现
    • 4、get实现
    • 5、remove实现
    • 6、containsValue 和 containsKey实现
    • 7、扩容 resize
    • 8、元素遍历traversal实现
    • 9、equals的优化
  • 三、TreeMap VS HashMap
  • 四、LinkedHashMap实现
  • 五、LinkedHashMap的接口实现
  • 六、使用HashMap和LinkedHashMap实现HashSet和LinkedHashSet
  • 附录、HashMap完整代码

一、哈希表的接口设计（HashMap）

  • 用哈希表实现的Map, 称为HashMap

  • 用哈希表中的数组(桶)索引, 存储红黑树的根节点, 每一个哈希表中的桶都是一颗红黑树
    在这里插入图片描述

    /* Description: 使用哈希表来实现一个HashMap @author guizy @date 2020/12/14 22:00 /
    public class HashMap implements Map { 

    1. private static final boolean RED = false;
    2. private static final boolean BLACK = true;
    3. private static final int DEFAULT_CAPACITY = 1 << 4;
    4. // 装载因子, 当哈希表容量为table.length用到75%就进行扩容
    5. private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    7. private int size;   // HashMap的容量(哈希表容量), 用来记录存放多少个entry(键值对)
    9. // 存放 红黑树根节点 的数组(哈希表底层就是数组), 也就是说哈希表中每一个桶中都是一颗红黑树. 桶数组
    10. private Node<K, V>[] table;
    12. public HashMap() { 
    13.     table = new Node[DEFAULT_CAPACITY];
    14. }

    }

二、哈希表的实现（HashMap）

1、声明节点

  1. protected static class Node<K, V> { 
  2.     int hash;    // 节点的哈希值
  3.     K key;
  4.     V value;
  5.     boolean color = RED;
  6.     Node<K, V> left;
  7.     Node<K, V> right;
  8.     Node<K, V> parent;
  10.     public Node(K key, V value, Node<K, V> parent) { 
  11.         this.key = key;
  12.         int hash = key == null ? 0 : key.hashCode();
  13.         this.hash = hash ^ (hash >>> 16);
  14.         this.value = value;
  15.         this.parent = parent;
  16.     }
  18.     public boolean isLeaf() { 
  19.         return left == null && right == null;
  20.     }
  22.     public boolean hasTwoChildren() { 
  23.         return left != null && right != null;
  24.     }
  26.     public boolean isLeftChild() { 
  27.         return parent != null && this == parent.left;
  28.     }
  30.     public boolean isRightChild() { 
  31.         return parent != null && this == parent.right;
  32.     }
  34.     public Node<K, V> sibling() { 
  35.         if (isLeftChild()) { 
  36.             return parent.right;
  37.         }
  39.         if (isRightChild()) { 
  40.             return parent.left;
  41.         }
  42.         return null;
  43.     }
  45.     @Override
  46.     public String toString() { 
  47.         return "Node_" + key + "_" + value;
  48.     }
  49. }

注意: 为了节省篇幅, 下面关于修复红黑树性质的代码就不提供了 , 可以参考之前的博客, 红黑树实现, TreeMap实现, 这些方法的代码都是相同的。
在这里插入图片描述
在这里插入图片描述

2、clean实现

  • 遍历哈希表中的桶数组，清空桶中红黑树的根节点。这样每个桶中的红黑树就都销毁了

    @Override
    public int size() { 

    1. return size;

    }

    @Override
    public boolean isEmpty() { 

    1. return size == 0;

    }

    @Override
    public void clear() { 

    1. // 这里的判断是因为, 如果size==0的时候, 调用clear, 还是会进入下面的循环,进行清空,数组只是开辟了16个空的位置,本来就是空的.
    2. if (size == 0) return;
    3. size = 0;
    4. // 将哈希表中每一个桶(红黑树的根节点)都清空.
    5. for (int i = 0; i < table.length; i++) { 
    6.     table[i] = null;
    7. }

    }

3、put实现

  • 在进行插入操作时，通过比较key和key.parent的哈希值大小，来决定插入到哈希表位置。
  • 如果哈希值相同，则比较equals。
  • 如果equals相同，则比较类名。
  • 如果类名相同（同一种类型），则查看是否实现comparable，如果实现，则直接通过该函数比较。
  • 如果相同类型，不具有可比较性，或其中一个数据为空，则比较内存地址。
  • 直接比较内存地址会导致结果不稳定，应该先扫码树中是否有该值，如果没有，再比较内存地址。

上面的操作, 就是为了提高HashMap的性能, 通过各种可以比较的条件, 判断红黑树上的结点添加的位置; 这样可以减少红黑树的性质修复. 提高代码性能

  1. /** * 往哈希表数组中(桶中)添加 * * @param key * @param value * @return 返回是被替代的value */
  2. @Override
  3. public V put(K key, V value) { 
  4.     resize();
  6.     // 哈希表中的索引
  7.     int index = index(key);
  8.     // 取出index位置(数组中)的红黑树根节点(因为哈希表中存储的就是红黑树的根节点(键值对))
  9.     Node<K, V> root = table[index];
  10.     if (root == null) { 
  11.         //root = new Node<>(key, value, null);
  12.         root = createNode(key, value, null);
  13.         table[index] = root;
  14.         size++;
  15.         // 修复红黑树性质
  16.         afterPut(root);
  17.         return null;
  18.     }
  19.     // 出现hash冲突, 说明table[index]表中的位置不为空,已经有红黑树的根节点了
  20.     // 添加的不是第一个节点
  21.     Node<K, V> parent = root; // 这个是第一次比较的父节点
  22.     Node<K, V> node = root;
  23.     int cmp = 0;
  24.     K k1 = key;
  25.     //int h1 = k1 == null ? 0 : k1.hashCode();
  26.     int h1 = hash(k1);
  27.     // 搜索结果
  28.     Node<K, V> result = null;
  29.     // 是否搜索过, 为了防止重复搜索; 提高代码性能
  30.     boolean searched = false;
  31.     do { 
  32.         parent = node; // 记录其每一次比较的父节点
  33.         K k2 = node.key;
  34.         int h2 = node.hash;
  35.         // 先比较哈希值
  36.         if (h1 > h2) { 
  37.             cmp = 1;
  38.         } else if (h1 < h2) { 
  39.             cmp = -1;
  40.         } else if (Objects.equals(k1, k2)) { 
  41.             cmp = 0;
  42.         } else if (k1 != null && k2 != null
  43.                 && k1.getClass() == k2.getClass()
  44.                 && k1 instanceof Comparable
  45.                 && (cmp = ((Comparable) k1).compareTo(k2)) != 0) { 
  46.             // 什么都不做. 直接就会到下下面cmp的比较逻辑
  47.             // 这里就不比较了, 因为我们之前说过哈希表的元素可以不具备可比较性.
  48.             // 确定两个key是否相同,只能比equals是否相同; 通过compareTo比较相等,也不代表他们就是相等的
  49.             // cmp = ((Comparable) k1).compareTo(k2);
  50.         } else if (searched) { 
  51.             // 已经搜索过了
  52.             cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
  53.         } else {  // 先进行扫描, 然后再根据内存地址大小决定,插入到左/右; searched == false 还没有搜索过
  54.             if ((node.left != null && (result = node(node.left, k1)) != null)
  55.                     || (node.right != null && (result = node(node.right, k1)) != null)) { 
  56.                 // 已经存在这个key
  57.                 node = result;
  58.                 cmp = 0;
  59.             } else { 
  60.                 // 不存在这个key
  61.                 searched = true;
  62.                 cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
  63.             }
  64.         }
  66.         if (cmp > 0) { 
  67.             // 插入的元素大于根节点的元素,插入到根节点的右边
  68.             node = node.right;
  69.         } else if (cmp < 0) { 
  70.             // 插入的元素小于根节点的元素,插入到根节点的左边
  71.             node = node.left;
  72.         } else {  // 相等
  73.             node.key = key;
  74.             V oldValue = node.value;
  75.             node.value = value;
  76.             // 这里写不写都行,hash本来就等于h1; 因为key是相同(equals相同)的时候,才会来到这里,key相同,hash值也肯定相同
  77.             node.hash = h1;
  78.             return oldValue; // 返回之前node的value
  79.         }
  80.     } while (node != null);
  81.     // 看看插入到父节点的哪个位置
  82.     //Node<K, V> newNode = new Node<>(key, value, parent);
  83.     Node<K, V> newNode = createNode(key, value, parent);
  84.     if (cmp > 0) { 
  85.         parent.right = newNode;
  86.     } else { 
  87.         parent.left = newNode;
  88.     }
  89.     size++;
  91.     // 添加节点之后的逻辑
  92.     afterPut(newNode);
  93.     // 这里的key是第一次加进去的, 之前没有值, 所以返回null
  94.     return null;
  95. }
  97. // ------------上面代码中用到的方法 (resize扩容,后面再说)----------------
  98. /** * 计算key的索引(在哈希表(数组)的哪个索引位置) * * @param key * @return */
  99. private int index(K key) { 
  100. // if (key == null) return 0; // 如果key为空, 插入到哈希表的0位置
  101. // int hash = key.hashCode();
  102. // // 同Double,Long的hashCode类似实现,因为key.hashCode()是我们自己实现的,在JDK底层又作了一次混合运算
  103. // // 拿到我们自己实现的hash值, 将hash值和hash值无符号右移16位再做一次运算
  104. // hash = hash ^ (hash >>> 16);
  105. // return hash & (table.length - 1);
  107.     return hash(key) & (table.length - 1);
  108. }
  110. /** * 为了拓展, HashMap子类可以创建自己的Node结点 * @param key * @param value * @param parent * @return */
  111. protected Node<K, V> createNode(K key, V value, Node<K, V> parent) { 
  112.     return new Node<>(key, value, parent);
  113. }
  115. /** * 扰动计算哈希值 * * @param key * @return */
  116. private int hash(K key) { 
  117.     if (key == null) return 0;
  118.     int hash = key.hashCode();
  119.     return hash ^ (hash >>> 16);
  120. }
  122. /** * 根据传入的node,计算它在数组中的哪个索引位置(即使它不是根节点) * * @param node * @return */
  123. private int index(Node<K, V> node) { 
  124.     return node.hash & (table.length - 1);
  125. }
  127. /** * 根据一个key, 找到对应的节点 * * @param key * @return */
  128. private Node<K, V> node(K key) { 
  129.     Node<K, V> root = table[index(key)];
  130.     return root == null ? null : node(root, key);
  131. }
  133. private Node<K, V> node(Node<K, V> node, K k1) { 
  134.     //int h1 = k1 == null ? 0 : k1.hashCode();
  135.     int h1 = hash(k1);
  136.     // 存储查找结果
  137.     Node<K, V> result = null;
  138.     int cmp = 0;
  139.     // 递归去左右子树查找
  140.     while (node != null) { 
  141.         K k2 = node.key;
  142.         int h2 = node.hash;
  143.         // 先比较哈希值
  144.         if (h1 > h2) { 
  145.             node = node.right;
  146.         } else if (h1 < h2) { 
  147.             node = node.left;
  148.             // 哈希值相同, 看看k1,k2是否相同,如果相同,则表示找到
  149.         } else if (Objects.equals(k1, k2)) { 
  150.             return node;
  151.             // 哈希值相同, equals不同, 看看是否具备可比较性
  152.         } else if (k1 != null && k2 != null
  153.                 && k1.getClass() == k2.getClass()
  154.                 && k1 instanceof Comparable
  155.                 && (cmp = ((Comparable) k1).compareTo(k2)) != 0) { 
  156.             // 具备可比较性
  157.             //cmp = ((Comparable) k1).compareTo(k2); // 和put相同,compareTo相同不应该确定key就相同,应该继续向下搜索节点的key
  158.             if (cmp > 0) { 
  159.                 node = node.right;
  160.             } else if (cmp < 0) { 
  161.                 node = node.left;
  162.             }
  163. // else { 
  164. // return node;
  165. // }
  166.             // 哈希值相同,equals不同, 不具备可比较性
  167.         } else if (node.right != null && (result = node(node.right, k1)) != null) { 
  168.             return result;
  169.         } else { 
  170.             node = node.left; // 优化下面的6行代码, 减少一次递归调用
  171.         }
  172. // } else if (node.left != null && (result = node(node.left, k1)) != null) { 
  173. // return result;
  174. // } else { 
  175. // // 没找到
  176. // return null;
  177. // }
  178.     }
  179.     return null;
  180. }

4、get实现

  • 首先根据想要获取的元素的key看看它是存在于哈希表的哪个桶中, 然后根据该桶中的红黑树根节点, 遍历去寻找该树的结点。

    @Override
    public V get(K key) { 

    1. Node<K, V> node = node(key);
    2. return node != null ? node.value : null;

    }

    /* 根据一个key, 找到对应的节点 @param key @return /
    private Node node(K key) { 

    1. Node<K, V> root = table[index(key)];
    2. return root == null ? null : node(root, key);

    }

    private Node node(Node node, K k1) { 

    1. //int h1 = k1 == null ? 0 : k1.hashCode();
    2. int h1 = hash(k1);
    3. // 存储查找结果
    4. Node<K, V> result = null;
    5. int cmp = 0;
    6. // 递归去左右子树查找
    7. while (node != null) { 
    8.     K k2 = node.key;
    9.     int h2 = node.hash;
    10.     // 先比较哈希值
    11.     if (h1 > h2) { 
    12.         node = node.right;
    13.     } else if (h1 < h2) { 
    14.         node = node.left;
    15.         // 哈希值相同, 看看k1,k2是否相同,如果相同,则表示找到
    16.     } else if (Objects.equals(k1, k2)) { 
    17.         return node;
    18.         // 哈希值相同, equals不同, 看看是否具备可比较性
    19.     } else if (k1 != null && k2 != null
    20.             && k1.getClass() == k2.getClass()
    21.             && k1 instanceof Comparable
    22.             && (cmp = ((Comparable) k1).compareTo(k2)) != 0) { 
    23.         // 具备可比较性
    24.         //cmp = ((Comparable) k1).compareTo(k2); // 和put相同,compareTo相同不应该确定key就相同,应该继续向下搜索节点的key
    25.         if (cmp > 0) { 
    26.             node = node.right;
    27.         } else if (cmp < 0) { 
    28.             node = node.left;
    29.         }

    // else {
    // return node;
    // }

    1.         // 哈希值相同,equals不同, 不具备可比较性
    2.     } else if (node.right != null && (result = node(node.right, k1)) != null) { 
    3.         return result;
    4.     } else { 
    5.         node = node.left; // 优化下面的6行代码, 减少一次递归调用
    6.     }

    // } else if (node.left != null && (result = node(node.left, k1)) != null) {
    // return result;
    // } else {
    // // 没找到
    // return null;
    // }

    1. }
    2. return null;

    }

5、remove实现

  1. @Override
  2. public V remove(K key) { 
  3.     return remove(node(key));
  4. }
  5. protected V remove(Node<K, V> node) { 
  6.     if (node == null) return null;
  7.     Node<K, V> willNode = node; // 本来要删除的节点,由于红黑树中度为2的节点删除方式, 和链表中的删除方式不同,所以要做交换
  9.     // node 不为空, 必然要删除结点, 先size--;
  10.     size--;
  12.     V oldValue = node.value;
  14.     // 删除node是度为2的结点
  15.     if (node.hasTwoChildren()) { 
  16.         /*//1 找到后继(也可以找到前驱) Node<E> successor = successor(node); //2 用后继结点的值覆盖度为2结点的值 node.element = successor.element; //3 删除后继节点 node = successor;*/
  18.         //1、找到前驱
  19.         Node<K, V> predecessor = predecessor(node);
  20.         //2、用前驱节点的值覆盖度为2节点的值
  21.         node.key = predecessor.key;
  22.         node.value = predecessor.value;
  23.         node.hash = predecessor.hash;
  24.         //3、删除前驱节点
  25.         node = predecessor;
  26.     }
  27.     // 删除node,即删除后继节点 (node节点必然是度为1或0)
  28.     // 因为node只有一个子节点/0个子节点, 如果其left!=null, 则用node.left来替代, node.left==null, 用node.right来替代,
  29.     // 若node为叶子节点, 说明, node.left==null, node.right也为null, 则replacement==null;
  30.     Node<K, V> replacement = node.left != null ? node.left : node.right;
  31.     // 获取要删除节点的索引(就是红黑树所在桶的索引)
  32.     int index = index(node);
  33.     // 删除node是度为1的结点
  34.     if (replacement != null) { 
  35.         // 更改parent
  36.         replacement.parent = node.parent;
  37.         // 更改parent的left、right的指向
  38.         if (node.parent == null) {   // node是度为1且是根节点
  39.             table[index] = replacement;
  40.         } else if (node == node.parent.left) { 
  41.             node.parent.left = replacement;
  42.         } else if (node == node.parent.right) { 
  43.             node.parent.right = replacement;
  44.         }
  45.         // 删除结点之后的处理
  46.         afterRemove(node, replacement);
  47.         // 删除node是叶子节点, 且是根节点
  48.     } else if (node.parent == null) { 
  49.         table[index] = null;
  50.         // 删除结点之后的处理
  51.         afterRemove(node, null);
  52.     } else {  // node是叶子结点, 且不是根节点
  53.         if (node == node.parent.left) { 
  54.             node.parent.left = null;
  55.         } else {   // node == node.parent.right
  56.             node.parent.right = null;
  57.         }
  58.         // 删除结点之后的处理
  59.         afterRemove(node, null);
  60.     }
  61.     // 交给子类处理的
  62.     afterChildRemove(willNode, node);
  63.     return oldValue;
  64. }
  66. /** * @param willNode 即将要删除的节点 * @param removeNode 实际删除的节点 */
  67. protected void afterChildRemove(Node<K, V> willNode, Node<K, V> removeNode) { 
  68. }

6、containsValue 和 containsKey实现

  • 检测哈希表中是否存在某值，通过遍历所有桶中的红黑树去寻找，使用层序遍历实现。

    @Override
    public boolean containsKey(K key) { 

    1. return node(key) != null;

    }

    @Override
    public boolean containsValue(V value) { 

    1. if (size == 0) return false;
    2. Queue<Node<K, V>> queue = new LinkedList<>();
    3. // 遍历哈希表中的所有的桶, 然后根据每个桶中的红黑树根节点, 层序遍历, 看看是否存在value
    4. for (int i = 0; i < table.length; i++) { 
    5.     // 说明哈希表中的table[i]的位置没有红黑树根节点, 也就是为空, 此时不用遍历比较.跳过
    6.     if (table[i] == null) continue;
    7.     queue.offer(table[i]);
    8.     while (!queue.isEmpty()) { 
    9.         Node<K, V> node = queue.poll();
    10.         if (Objects.equals(value, node.value)) return true;
    11.         if (node.left != null) { 
    12.             queue.offer(node.left);
    13.         }
    14.         if (node.right != null) { 
    15.             queue.offer(node.right);
    16.         }
    17.     }
    18. }
    19. return false;

    }

7、扩容

  • 扩容操作, 在put方法, 中调用
  • 当哈希表的table数组中添加元素过多后，哈希冲突概率增大，效率变低。所以要根据装填因子判断是否需要扩容。
  • 装填因子：节点总数量 / 哈希表桶数组长度，也叫做负载因子。
  • 在JDK1.8的HashMap中，如果装填因子超过0.75，就扩容为原来的2倍。
  • 如果装填因子超过0.75，就将数组长度扩大为原来的两倍，并将原来的数据迁移进新数组。

  • 扩容之后，原来数据算出的节点值就有可能不一样了（保持不变或index = index + 旧容量），因为节点的计算需要涉及到table.length。

    /* 扩容 */
    private void resize() { 

    1. // 装填因子 <= 0.75, 不扩容
    2. if (size / table.length <= DEFAULT_LOAD_FACTOR) return;
    3. Node<K, V>[] oldTable = table;
    4. table = new Node[oldTable.length << 1];
    5. Queue<Node<K, V>> queue = new LinkedList<>();
    6. for (int i = 0; i < oldTable.length; i++) { 
    7.     if (oldTable[i] == null) continue;
    8.     // 层序遍历
    9.     queue.offer(oldTable[i]);
    10.     while (!queue.isEmpty()) { 
    11.         Node<K, V> node = queue.poll();
    12.         if (node.left != null) { 
    13.             queue.offer(node.left);
    14.         }
    15.         if (node.right != null) { 
    16.             queue.offer(node.right);
    17.         }
    18.         // 挪动代码,放到后面
    19.         moveNode(node);
    20.     }
    21. }

    }

    /* 将之前哈希表中的节点, 挪动到扩容后的哈希表中 @param newNode */
    private void moveNode(Node newNode) { 

    1. // 首先重置挪动过来node的left,right,parent
    2. newNode.parent = null;
    3. newNode.left = null;
    4. newNode.right = null;
    5. newNode.color = RED;
    7. // 哈希表中的索引
    8. int index = index(newNode);
    9. // 取出index位置(数组中)的红黑树根节点(因为哈希表中存储的就是红黑树的根节点(键值对))
    10. Node<K, V> root = table[index];
    11. if (root == null) { 
    12.     root = newNode;
    13.     table[index] = root;
    14.     afterPut(root);
    15.     return;
    16. }
    17. Node<K, V> parent = root; // 这个是第一次比较的父节点
    18. Node<K, V> node = root;
    19. int cmp = 0;
    20. K k1 = newNode.key;
    21. int h1 = newNode.hash;
    22. do { 
    23.     parent = node; // 记录其每一次比较的父节点
    24.     K k2 = node.key;
    25.     int h2 = node.hash;
    26.     // 先比较哈希值, 因为是挪动, 所以不用equals比较key, 肯定没有相同的key
    27.     if (h1 > h2) { 
    28.         cmp = 1;
    29.     } else if (h1 < h2) { 
    30.         cmp = -1;
    31.     } else if (k1 != null && k2 != null
    32.             && k1.getClass() == k2.getClass()
    33.             && k1 instanceof Comparable
    34.             && (cmp = ((Comparable) k1).compareTo(k2)) != 0) { 
    35.     } else { 
    36.         cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
    37.     }
    39.     if (cmp > 0) { 
    40.         // 插入的元素大于根节点的元素,插入到根节点的右边
    41.         node = node.right;
    42.     } else if (cmp < 0) { 
    43.         // 插入的元素小于根节点的元素,插入到根节点的左边
    44.         node = node.left;
    45.     }
    46. } while (node != null);
    47. // 看看插入到父节点的哪个位置
    48. newNode.parent = parent;
    49. if (cmp > 0) { 
    50.     parent.right = newNode;
    51. } else { 
    52.     parent.left = newNode;
    53. }
    54. // 添加节点之后的逻辑
    55. afterPut(newNode);

    }

8、元素遍历traversal实现

  1. @Override
  2. public void traversal(Visitor<K, V> visitor) { 
  3.     if (size == 0 || visitor == null) return;
  4.     Queue<Node<K, V>> queue = new LinkedList<>();
  5.     // 遍历哈希表中的所有的桶, 然后根据每个桶中的红黑树根节点, 层序遍历, 看看是否存在value
  6.     for (int i = 0; i < table.length; i++) { 
  7.         // 说明哈希表中的table[i]的位置没有红黑树根节点, 也就是为空, 此时不用遍历比较.跳过
  8.         if (table[i] == null) continue;
  9.         queue.offer(table[i]);
  10.         while (!queue.isEmpty()) { 
  11.             Node<K, V> node = queue.poll();
  12.             // 返回为true, 就停止遍历
  13.             if (visitor.visit(node.key, node.value)) return;
  14.             if (node.left != null) { 
  15.                 queue.offer(node.left);
  16.             }
  17.             if (node.right != null) { 
  18.                 queue.offer(node.right);
  19.             }
  20.         }
  21.     }
  22. }

9、equals的优化

  • 我们在添加元素时，要谨防因equals的函数实现有问题，导致a.equals(b)和b.equals(a)的结果不一致。
  • 所以在实现equals函数时，要遵循以下条件：
    在这里插入图片描述

三、TreeMap VS HashMap

  • TreeMap增删改查都是O(logn)级别，而哈希表是O(1)级别。
  • 当元素具备可比较性且要求升序遍历时，使用TreeMap。当对遍历没有要求时，选择HashMap。

四、LinkedHashMap

  • 在HashMap的基础上维护元素的添加顺序，使得遍历的结果是遵循添加顺序的。在HashMap的基础上维护一个双向链表
  • 假设添加顺序是37，21，31，41，97，95，52，42，83

注意: 该链表是跨树的, 将所有桶中的红黑树的节点, 通过添加顺序, 都串到一个链表中
在这里插入图片描述

五、LinkedHashMap的接口实现

  • 新增first和last两个属性。

    public class LinkedHashMap extends HashMap { 

    1. private LinkedNode<K, V> first;
    2. private LinkedNode<K, V> last;

    }

  • 给Node增加前驱和后继两个指针。

    private static class LinkedNode extends Node { 

    1. LinkedNode<K, V> prev;
    2. LinkedNode<K, V> next;
    3. public LinkedNode(K key, V value, Node<K, V> parent) { 
    4.     super(key, value, parent);
    5. }

    }

  • 添加一个构造节点的函数。

    @Override
    protected Node createNode(K key, V value, Node parent) { 

    1. LinkedNode node = new LinkedNode(key, value, parent);
    2. if (first == null) {  //没有头节点
    3.     first = last = node;
    4. } else {  //有头节点
    5.     last.next = node;
    6.     node.prev = last;
    7.     last = node;
    8. }
    9. return node;

    }

  • clear函数需要清空first和last指针。

    @Override
    public void clear() { 

    1. super.clear();
    2. first = null;
    3. last = null;

    }

  • 遍历函数

    @Override
    public void traversal(Visitor visitor) { 

    1. if (visitor == null) return;
    2. LinkedNode<K, V> node = first;
    3. while (node != null) { 
    4.     if (visitor.visit(node.key, node.value)) return;
    5.     node = node.next;
    6. }

    }

  • 删除函数，不仅仅需要删除数据，还需要修改指针指向。

  • 删除度为2的节点时，需要注意更换node与前驱/后继节点的链接位置。
  • 例如，删除31

img

  1. @Override
  2. protected void afterRemove(Node<K, V> willNode, Node<K, V> removedNode) { 
  3.     LinkedNode<K, V> node1 = (LinkedNode<K, V>) willNode;
  4.     LinkedNode<K, V> node2 = (LinkedNode<K, V>) removedNode;
  6.     if (node1 != node2) { 
  7.         // 交换linkedWillNode和linkedRemovedNode在链表中的位置
  8.         // 交换prev
  9.         LinkedNode<K, V> tmp = node1.prev;
  10.         node1.prev = node2.prev;
  11.         node2.prev = tmp;
  12.         if (node1.prev == null) { 
  13.             first = node1;
  14.         } else { 
  15.             node1.prev.next = node1;
  16.         }
  17.         if (node2.prev == null) { 
  18.             first = node2;
  19.         } else { 
  20.             node2.prev.next = node2;
  21.         }
  23.         // 交换next
  24.         tmp = node1.next;
  25.         node1.next = node2.next;
  26.         node2.next = tmp;
  27.         if (node1.next == null) { 
  28.             last = node1;
  29.         } else { 
  30.             node1.next.prev = node1;
  31.         }
  32.         if (node2.next == null) { 
  33.             last = node2;
  34.         } else { 
  35.             node2.next.prev = node2;
  36.         }
  37.     }
  39.     LinkedNode<K, V> prev = node2.prev;
  40.     LinkedNode<K, V> next = node2.next;
  41.     if (prev == null) { 
  42.         first = next;
  43.     } else { 
  44.         prev.next = next;
  45.     }
  47.     if (next == null) { 
  48.         last = prev;
  49.     } else { 
  50.         next.prev = prev;
  51.     }
  52. }
  • 核心就是交换。

img

  • 遍历节点

    @Override
    public boolean containsValue(V value) { 

    1. LinkedNode<K, V> node = first;
    2. while (node != null) { 
    3.     if (Objects.equals(value, node.value)) return true;
    4.     node = node.next;
    5. }
    6. return false;

    }

六、使用HashMap和LinkedHashMap实现HashSet和LinkedHashSet

HashSet

  1. /** * Description: 使用HashMap实现HashSet * * @author guizy1 * @date 2020/12/24 12:58 */
  2. public class HashSet<E> implements Set<E> { 
  4.     private HashMap<E, Object> map = new HashMap<>();
  6.     @Override
  7.     public int size() { 
  8.         return map.size();
  9.     }
  11.     @Override
  12.     public boolean isEmpty() { 
  13.         return map.isEmpty();
  14.     }
  16.     @Override
  17.     public void clear() { 
  18.         map.clear();
  19.     }
  21.     @Override
  22.     public boolean contains(E element) { 
  23.         return map.containsKey(element);
  24.     }
  26.     @Override
  27.     public void add(E element) { 
  28.         map.put(element, null);
  29.     }
  31.     @Override
  32.     public void remove(E element) { 
  33.         map.remove(element);
  34.     }
  36.     @Override
  37.     public void traversal(Visitor<E> visitor) { 
  38.         map.traversal(new Map.Visitor<E, Object>() { 
  39.             @Override
  40.             public boolean visit(E key, Object value) { 
  41.                 return visitor.visit(key);
  42.             }
  43.         });
  44.     }
  45. }

LinkedHashSet

  1. /** * Description: 使用LinkedHashMap 实现 LinkedHashSet * * @author guizy1 * @date 2020/12/24 13:02 */
  2. public class LinkedHashSet<E> implements Set<E> { 
  4.     private LinkedHashMap<E, Object> map = new LinkedHashMap<>();
  6.     @Override
  7.     public int size() { 
  8.         return map.size();
  9.     }
  11.     @Override
  12.     public boolean isEmpty() { 
  13.         return map.isEmpty();
  14.     }
  16.     @Override
  17.     public void clear() { 
  18.         map.clear();
  19.     }
  21.     @Override
  22.     public boolean contains(E element) { 
  23.         return map.containsKey(element);
  24.     }
  26.     @Override
  27.     public void add(E element) { 
  28.         map.put(element, null);
  29.     }
  31.     @Override
  32.     public void remove(E element) { 
  33.         map.remove(element);
  34.     }
  36.     @Override
  37.     public void traversal(Visitor<E> visitor) { 
  38.         map.traversal(new Map.Visitor<E, Object>() { 
  39.             @Override
  40.             public boolean visit(E key, Object value) { 
  41.                 return visitor.visit(key);
  42.             }
  43.         });
  44.     }
  45. }

附录: HashMap完整代码

  1. package com.hashtable.map;
  3. import com.hashtable.printer.BinaryTreeInfo;
  4. import com.hashtable.printer.BinaryTrees;
  6. import java.util.LinkedList;
  7. import java.util.Objects;
  8. import java.util.Queue;
  10. /** * Description: 使用哈希表来实现一个HashMap * * @author guizy * @date 2020/12/14 22:00 */
  11. @SuppressWarnings("all")
  12. public class HashMap<K, V> implements Map<K, V> { 
  14.     private static final boolean RED = false;
  15.     private static final boolean BLACK = true;
  16.     private static final int DEFAULT_CAPACITY = 1 << 4;
  17.     // 装载因子, 当哈希表容量为table.length用到75%就进行扩容
  18.     private static final float DEFAULT_LOAD_FACTOR = 0.75f;
  20.     private int size;   // HashMap的容量(哈希表容量), 用来记录存放多少个entry(键值对)
  22.     // 存放 红黑树根节点 的数组(哈希表底层就是数组), 也就是说哈希表中每一个桶中都是一颗红黑树. 桶数组
  23.     private Node<K, V>[] table;
  25.     public HashMap() { 
  26.         table = new Node[DEFAULT_CAPACITY];
  27.     }
  29.     @Override
  30.     public int size() { 
  31.         return size;
  32.     }
  34.     @Override
  35.     public boolean isEmpty() { 
  36.         return size == 0;
  37.     }
  39.     @Override
  40.     public void clear() { 
  41.         // 这里的判断是因为, 如果size==0的时候, 调用clear, 还是会进入下面的循环,进行清空,数组只是开辟了16个空的位置,本来就是空的.
  42.         if (size == 0) return;
  43.         size = 0;
  44.         // 将哈希表中每一个桶(红黑树的根节点)都清空.
  45.         for (int i = 0; i < table.length; i++) { 
  46.             table[i] = null;
  47.         }
  48.     }
  50.     /** * 往哈希表数组中(桶中)添加 * * @param key * @param value * @return 返回是被替代的value */
  51.     @Override
  52.     public V put(K key, V value) { 
  53.         resize();
  55.         // 哈希表中的索引
  56.         int index = index(key);
  57.         // 取出index位置(数组中)的红黑树根节点(因为哈希表中存储的就是红黑树的根节点(键值对))
  58.         Node<K, V> root = table[index];
  59.         if (root == null) { 
  60.             //root = new Node<>(key, value, null);
  61.             root = createNode(key, value, null);
  62.             table[index] = root;
  63.             size++;
  64.             // 修复红黑树性质
  65.             afterPut(root);
  66.             return null;
  67.         }
  68.         // 出现hash冲突, 说明table[index]表中的位置不为空,已经有红黑树的根节点了
  69.         // 添加的不是第一个节点
  70.         Node<K, V> parent = root; // 这个是第一次比较的父节点
  71.         Node<K, V> node = root;
  72.         int cmp = 0;
  73.         K k1 = key;
  74.         //int h1 = k1 == null ? 0 : k1.hashCode();
  75.         int h1 = hash(k1);
  76.         // 搜索结果
  77.         Node<K, V> result = null;
  78.         // 是否搜索过, 为了防止重复搜索; 提高代码性能
  79.         boolean searched = false;
  80.         do { 
  81.             parent = node; // 记录其每一次比较的父节点
  82.             K k2 = node.key;
  83.             int h2 = node.hash;
  84.             // 先比较哈希值
  85.             if (h1 > h2) { 
  86.                 cmp = 1;
  87.             } else if (h1 < h2) { 
  88.                 cmp = -1;
  89.             } else if (Objects.equals(k1, k2)) { 
  90.                 cmp = 0;
  91.             } else if (k1 != null && k2 != null
  92.                     && k1.getClass() == k2.getClass()
  93.                     && k1 instanceof Comparable
  94.                     && (cmp = ((Comparable) k1).compareTo(k2)) != 0) { 
  95.                 // 什么都不做. 直接就会到下下面cmp的比较逻辑
  96.                 // 这里就不比较了, 因为我们之前说过哈希表的元素可以不具备可比较性.
  97.                 // 确定两个key是否相同,只能比equals是否相同; 通过compareTo比较相等,也不代表他们就是相等的
  98.                 // cmp = ((Comparable) k1).compareTo(k2);
  99.             } else if (searched) { 
  100.                 // 已经搜索过了
  101.                 cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
  102.             } else {  // 先进行扫描, 然后再根据内存地址大小决定,插入到左/右; searched == false 还没有搜索过
  103.                 if ((node.left != null && (result = node(node.left, k1)) != null)
  104.                         || (node.right != null && (result = node(node.right, k1)) != null)) { 
  105.                     // 已经存在这个key
  106.                     node = result;
  107.                     cmp = 0;
  108.                 } else { 
  109.                     // 不存在这个key
  110.                     searched = true;
  111.                     cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
  112.                 }
  113.             }
  115.             if (cmp > 0) { 
  116.                 // 插入的元素大于根节点的元素,插入到根节点的右边
  117.                 node = node.right;
  118.             } else if (cmp < 0) { 
  119.                 // 插入的元素小于根节点的元素,插入到根节点的左边
  120.                 node = node.left;
  121.             } else {  // 相等
  122.                 node.key = key;
  123.                 V oldValue = node.value;
  124.                 node.value = value;
  125.                 // 这里写不写都行,hash本来就等于h1; 因为key是相同(equals相同)的时候,才会来到这里,key相同,hash值也肯定相同
  126.                 node.hash = h1;
  127.                 return oldValue; // 返回之前node的value
  128.             }
  129.         } while (node != null);
  130.         // 看看插入到父节点的哪个位置
  131.         //Node<K, V> newNode = new Node<>(key, value, parent);
  132.         Node<K, V> newNode = createNode(key, value, parent);
  133.         if (cmp > 0) { 
  134.             parent.right = newNode;
  135.         } else { 
  136.             parent.left = newNode;
  137.         }
  138.         size++;
  140.         // 添加节点之后的逻辑
  141.         afterPut(newNode);
  142.         // 这里的key是第一次加进去的, 之前没有值, 所以返回null
  143.         return null;
  144.     }
  146.     @Override
  147.     public V get(K key) { 
  148.         Node<K, V> node = node(key);
  149.         return node != null ? node.value : null;
  150.     }
  152.     @Override
  153.     public V remove(K key) { 
  154.         return remove(node(key));
  155.     }
  157.     @Override
  158.     public boolean containsKey(K key) { 
  159.         return node(key) != null;
  160.     }
  162.     @Override
  163.     public boolean containsValue(V value) { 
  164.         if (size == 0) return false;
  165.         Queue<Node<K, V>> queue = new LinkedList<>();
  166.         // 遍历哈希表中的所有的桶, 然后根据每个桶中的红黑树根节点, 层序遍历, 看看是否存在value
  167.         for (int i = 0; i < table.length; i++) { 
  168.             // 说明哈希表中的table[i]的位置没有红黑树根节点, 也就是为空, 此时不用遍历比较.跳过
  169.             if (table[i] == null) continue;
  170.             queue.offer(table[i]);
  171.             while (!queue.isEmpty()) { 
  172.                 Node<K, V> node = queue.poll();
  173.                 if (Objects.equals(value, node.value)) return true;
  174.                 if (node.left != null) { 
  175.                     queue.offer(node.left);
  176.                 }
  177.                 if (node.right != null) { 
  178.                     queue.offer(node.right);
  179.                 }
  180.             }
  181.         }
  182.         return false;
  183.     }
  185.     @Override
  186.     public void traversal(Visitor<K, V> visitor) { 
  187.         if (size == 0 || visitor == null) return;
  188.         Queue<Node<K, V>> queue = new LinkedList<>();
  189.         // 遍历哈希表中的所有的桶, 然后根据每个桶中的红黑树根节点, 层序遍历, 看看是否存在value
  190.         for (int i = 0; i < table.length; i++) { 
  191.             // 说明哈希表中的table[i]的位置没有红黑树根节点, 也就是为空, 此时不用遍历比较.跳过
  192.             if (table[i] == null) continue;
  193.             queue.offer(table[i]);
  194.             while (!queue.isEmpty()) { 
  195.                 Node<K, V> node = queue.poll();
  196.                 // 返回为true, 就停止遍历
  197.                 if (visitor.visit(node.key, node.value)) return;
  198.                 if (node.left != null) { 
  199.                     queue.offer(node.left);
  200.                 }
  201.                 if (node.right != null) { 
  202.                     queue.offer(node.right);
  203.                 }
  204.             }
  205.         }
  206.     }
  208.     public void print() { 
  209.         if (size == 0) return;
  210.         for (int i = 0; i < table.length; i++) { 
  211.             final Node<K, V> root = table[i];
  212.             System.out.println("[index = " + i + "]");
  213.             BinaryTrees.println(new BinaryTreeInfo() { 
  214.                 @Override
  215.                 public Object root() { 
  216.                     return root;
  217.                 }
  219.                 @Override
  220.                 public Object left(Object node) { 
  221.                     return ((Node<K, V>) node).left;
  222.                 }
  224.                 @Override
  225.                 public Object right(Object node) { 
  226.                     return ((Node<K, V>) node).right;
  227.                 }
  229.                 @Override
  230.                 public Object string(Object node) { 
  231.                     return node;
  232.                 }
  233.             });
  234.             System.out.println("----------------------------------");
  235.         }
  236.     }
  238.     /** * 为了拓展, HashMap子类可以创建自己的Node结点 * @param key * @param value * @param parent * @return */
  239.     protected Node<K, V> createNode(K key, V value, Node<K, V> parent) { 
  240.         return new Node<>(key, value, parent);
  241.     }
  243.     /** * @param willNode 即将要删除的节点 * @param removeNode 实际删除的节点 */
  244.     protected void afterChildRemove(Node<K, V> willNode, Node<K, V> removeNode) { 
  245.     }
  247.     /** * 扩容 */
  248.     private void resize() { 
  249.         // 装填因子 <= 0.75, 不扩容
  250.         if (size / table.length <= DEFAULT_LOAD_FACTOR) return;
  251.         Node<K, V>[] oldTable = table;
  252.         table = new Node[oldTable.length << 1];
  253.         Queue<Node<K, V>> queue = new LinkedList<>();
  254.         for (int i = 0; i < oldTable.length; i++) { 
  255.             if (oldTable[i] == null) continue;
  256.             // 层序遍历
  257.             queue.offer(oldTable[i]);
  258.             while (!queue.isEmpty()) { 
  259.                 Node<K, V> node = queue.poll();
  260.                 if (node.left != null) { 
  261.                     queue.offer(node.left);
  262.                 }
  263.                 if (node.right != null) { 
  264.                     queue.offer(node.right);
  265.                 }
  266.                 // 挪动代码,放到后面
  267.                 moveNode(node);
  268.             }
  269.         }
  270.     }
  272.     /** * 将之前哈希表中的节点, 挪动到扩容后的哈希表中 * * @param newNode */
  273.     private void moveNode(Node<K, V> newNode) { 
  274.         // 首先重置挪动过来node的left,right,parent
  275.         newNode.parent = null;
  276.         newNode.left = null;
  277.         newNode.right = null;
  278.         newNode.color = RED;
  280.         // 哈希表中的索引
  281.         int index = index(newNode);
  282.         // 取出index位置(数组中)的红黑树根节点(因为哈希表中存储的就是红黑树的根节点(键值对))
  283.         Node<K, V> root = table[index];
  284.         if (root == null) { 
  285.             root = newNode;
  286.             table[index] = root;
  287.             afterPut(root);
  288.             return;
  289.         }
  290.         Node<K, V> parent = root; // 这个是第一次比较的父节点
  291.         Node<K, V> node = root;
  292.         int cmp = 0;
  293.         K k1 = newNode.key;
  294.         int h1 = newNode.hash;
  295.         do { 
  296.             parent = node; // 记录其每一次比较的父节点
  297.             K k2 = node.key;
  298.             int h2 = node.hash;
  299.             // 先比较哈希值, 因为是挪动, 所以不用equals比较key, 肯定没有相同的key
  300.             if (h1 > h2) { 
  301.                 cmp = 1;
  302.             } else if (h1 < h2) { 
  303.                 cmp = -1;
  304.             } else if (k1 != null && k2 != null
  305.                     && k1.getClass() == k2.getClass()
  306.                     && k1 instanceof Comparable
  307.                     && (cmp = ((Comparable) k1).compareTo(k2)) != 0) { 
  308.             } else { 
  309.                 cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
  310.             }
  312.             if (cmp > 0) { 
  313.                 // 插入的元素大于根节点的元素,插入到根节点的右边
  314.                 node = node.right;
  315.             } else if (cmp < 0) { 
  316.                 // 插入的元素小于根节点的元素,插入到根节点的左边
  317.                 node = node.left;
  318.             }
  319.         } while (node != null);
  320.         // 看看插入到父节点的哪个位置
  321.         newNode.parent = parent;
  322.         if (cmp > 0) { 
  323.             parent.right = newNode;
  324.         } else { 
  325.             parent.left = newNode;
  326.         }
  327.         // 添加节点之后的逻辑
  328.         afterPut(newNode);
  329.     }
  331.     protected V remove(Node<K, V> node) { 
  332.         if (node == null) return null;
  333.         Node<K, V> willNode = node; // 本来要删除的节点,由于红黑树中度为2的节点删除方式, 和链表中的删除方式不同,所以要做交换
  335.         // node 不为空, 必然要删除结点, 先size--;
  336.         size--;
  338.         V oldValue = node.value;
  340.         // 删除node是度为2的结点
  341.         if (node.hasTwoChildren()) { 
  342.             /*//1 找到后继(也可以找到前驱) Node<E> successor = successor(node); //2 用后继结点的值覆盖度为2结点的值 node.element = successor.element; //3 删除后继节点 node = successor;*/
  344.             //1、找到前驱
  345.             Node<K, V> predecessor = predecessor(node);
  346.             //2、用前驱节点的值覆盖度为2节点的值
  347.             node.key = predecessor.key;
  348.             node.value = predecessor.value;
  349.             node.hash = predecessor.hash;
  350.             //3、删除前驱节点
  351.             node = predecessor;
  352.         }
  353.         // 删除node,即删除后继节点 (node节点必然是度为1或0)
  354.         // 因为node只有一个子节点/0个子节点, 如果其left!=null, 则用node.left来替代, node.left==null, 用node.right来替代,
  355.         // 若node为叶子节点, 说明, node.left==null, node.right也为null, 则replacement==null;
  356.         Node<K, V> replacement = node.left != null ? node.left : node.right;
  357.         // 获取要删除节点的索引(就是红黑树所在桶的索引)
  358.         int index = index(node);
  359.         // 删除node是度为1的结点
  360.         if (replacement != null) { 
  361.             // 更改parent
  362.             replacement.parent = node.parent;
  363.             // 更改parent的left、right的指向
  364.             if (node.parent == null) {   // node是度为1且是根节点
  365.                 table[index] = replacement;
  366.             } else if (node == node.parent.left) { 
  367.                 node.parent.left = replacement;
  368.             } else if (node == node.parent.right) { 
  369.                 node.parent.right = replacement;
  370.             }
  371.             // 删除结点之后的处理
  372.             afterRemove(node, replacement);
  373.             // 删除node是叶子节点, 且是根节点
  374.         } else if (node.parent == null) { 
  375.             table[index] = null;
  376.             // 删除结点之后的处理
  377.             afterRemove(node, null);
  378.         } else {  // node是叶子结点, 且不是根节点
  379.             if (node == node.parent.left) { 
  380.                 node.parent.left = null;
  381.             } else {   // node == node.parent.right
  382.                 node.parent.right = null;
  383.             }
  384.             // 删除结点之后的处理
  385.             afterRemove(node, null);
  386.         }
  387.         // 交给子类处理的
  388.         afterChildRemove(willNode, node);
  389.         return oldValue;
  390.     }
  392.     /** * 根据一个key, 找到对应的节点 * * @param key * @return */
  393.     private Node<K, V> node(K key) { 
  394.         Node<K, V> root = table[index(key)];
  395.         return root == null ? null : node(root, key);
  396.     }
  398.     private Node<K, V> node(Node<K, V> node, K k1) { 
  399.         //int h1 = k1 == null ? 0 : k1.hashCode();
  400.         int h1 = hash(k1);
  401.         // 存储查找结果
  402.         Node<K, V> result = null;
  403.         int cmp = 0;
  404.         // 递归去左右子树查找
  405.         while (node != null) { 
  406.             K k2 = node.key;
  407.             int h2 = node.hash;
  408.             // 先比较哈希值
  409.             if (h1 > h2) { 
  410.                 node = node.right;
  411.             } else if (h1 < h2) { 
  412.                 node = node.left;
  413.                 // 哈希值相同, 看看k1,k2是否相同,如果相同,则表示找到
  414.             } else if (Objects.equals(k1, k2)) { 
  415.                 return node;
  416.                 // 哈希值相同, equals不同, 看看是否具备可比较性
  417.             } else if (k1 != null && k2 != null
  418.                     && k1.getClass() == k2.getClass()
  419.                     && k1 instanceof Comparable
  420.                     && (cmp = ((Comparable) k1).compareTo(k2)) != 0) { 
  421.                 // 具备可比较性
  422.                 //cmp = ((Comparable) k1).compareTo(k2); // 和put相同,compareTo相同不应该确定key就相同,应该继续向下搜索节点的key
  423.                 if (cmp > 0) { 
  424.                     node = node.right;
  425.                 } else if (cmp < 0) { 
  426.                     node = node.left;
  427.                 }
  428. // else { 
  429. // return node;
  430. // }
  431.                 // 哈希值相同,equals不同, 不具备可比较性
  432.             } else if (node.right != null && (result = node(node.right, k1)) != null) { 
  433.                 return result;
  434.             } else { 
  435.                 node = node.left; // 优化下面的6行代码, 减少一次递归调用
  436.             }
  437. // } else if (node.left != null && (result = node(node.left, k1)) != null) { 
  438. // return result;
  439. // } else { 
  440. // // 没找到
  441. // return null;
  442. // }
  443.         }
  444.         return null;
  445.     }
  448.     /** * 计算key的索引(在哈希表(数组)的哪个索引位置) * * @param key * @return */
  449.     private int index(K key) { 
  450. // if (key == null) return 0; // 如果key为空, 插入到哈希表的0位置
  451. // int hash = key.hashCode();
  452. // // 同Double,Long的hashCode类似实现,因为key.hashCode()是我们自己实现的,在JDK底层又作了一次混合运算
  453. // // 拿到我们自己实现的hash值, 将hash值和hash值无符号右移16位再做一次运算
  454. // hash = hash ^ (hash >>> 16);
  455. // return hash & (table.length - 1);
  457.         return hash(key) & (table.length - 1);
  458.     }
  460.     /** * 扰动计算哈希值 * * @param key * @return */
  461.     private int hash(K key) { 
  462.         if (key == null) return 0;
  463.         int hash = key.hashCode();
  464.         return hash ^ (hash >>> 16);
  465.     }
  467.     /** * 根据传入的node,计算它在数组中的哪个索引位置(即使它不是根节点) * * @param node * @return */
  468.     private int index(Node<K, V> node) { 
  469.         return node.hash & (table.length - 1);
  470.     }
  472.     private void afterPut(Node<K, V> node) { 
  473.         Node<K, V> parent = node.parent;
  475.         // 添加的是根节点(染成黑色)
  476.         if (parent == null) { 
  477.             black(node);
  478.             return;
  479.         }
  481.         // ------------- 一共 12 种情况--------------
  482.         // 不需要处理的4种情况: 如果父节点是黑色, 直接返回
  483.         if (isBlack(parent)) return;
  485.         // 根据uncle节点的颜色来判断其他的各4种情况
  486.         Node<K, V> uncle = parent.sibling();
  487.         // 祖父节点
  488.         Node<K, V> grand = parent.parent;
  490.         // 需要处理的4种情况: 叔父节点是红色
  491.         if (isRed(uncle)) { 
  492.             black(parent);
  493.             black(uncle);
  494.             // 把祖父节点染成红色, 当做新添加的节点处理(递归调用afterAdd)
  495.             afterPut(red(grand));
  496.             return;
  497.         }
  499.         /* 因为这4种情况, RBTree需要对节点进行旋转操作; 此时就需要使用到AVLTree中的旋转代码, 因为AVLTree和RBTree都是平衡二叉搜索树(BalanceBinarySearchTree),BBST在BST的基础上增加了旋转功能; 为了程序的拓展性, 我们在创建一个BBST 继承 BST, AVLTree和RBTree再 继承 BBST */
  500.         // 需要处理的4种情况: 叔父节点不是红色(叔父节点为空)
  501.         if (parent.isLeftChild()) {  // L
  502.             // LL,LR, grand都要染成红色
  503.             red(grand);
  504.             if (node.isLeftChild()) {  // LL
  505.                 black(parent);
  506.             } else {  // LR
  507.                 black(node);
  508.                 rotateLeft(parent);
  509.             }
  510.             // LL,LR, grand最后都要右旋转
  511.             rotateRight(grand);
  512.         } else {  // R
  513.             red(grand);
  514.             if (node.isLeftChild()) {  // RL
  515.                 black(node);
  516.                 rotateRight(parent);
  517.             } else {  // RR
  518.                 black(parent);
  519.             }
  520.             rotateLeft(grand);
  521.         }
  523.     }
  525.     private void afterRemove(Node<K, V> node, Node<K, V> replacement) { 
  526.         // 删除的节点, 都是叶子节点
  528.         // 如果删除的节点为红色,则不需要处理
  529.         if (isRed(node)) return;
  531.         // 用于取代node的节点replacement为红色
  532.         if (isRed(replacement)) { 
  533.             // 将替代节点染为黑色
  534.             black(replacement);
  535.             return;
  536.         }
  538.         // 删除的是根节点
  539.         Node<K, V> parent = node.parent;
  540.         if (parent == null) return;
  542.         // 删除黑色的叶子节点(肯定会下溢)
  543.         // 判断被删除的node是左还是右(如果直接通过sibling()方法,拿到的不准确,因为在remove方法中已经将node置为null了,然后才调用的afterRemove
  544.         boolean left = parent.left == null || node.isLeftChild();
  545.         Node<K, V> sibling = left ? parent.right : parent.left;
  546.         if (left) {  // 被删除的节点在左边, 兄弟节点在右边
  547.             if (isRed(sibling)) { 
  548.                 black(sibling);
  549.                 red(parent);
  550.                 rotateLeft(parent);
  551.                 sibling = parent.right;
  552.             }
  553.             // 兄弟节点必然是黑色
  554.             if (isBlack(sibling.left) && isBlack(sibling.right)) {   // 表示node的黑兄弟节点的left,right子节点都是黑节点
  555.                 boolean parentBlack = isBlack(parent);
  556.                 black(parent);
  557.                 red(sibling);
  558.                 if (parentBlack) { 
  559.                     afterRemove(parent, null);
  560.                 }
  561.             } else {  // 表示兄弟节点至少有一个红色子节点,可以向被删除节点的位置借一个节点
  562.                 if (isBlack(sibling.right)) { 
  563.                     rotateRight(sibling);
  564.                     sibling = parent.right;
  565.                 }
  566.                 color(sibling, colorOf(parent));
  567.                 black(sibling.right);
  568.                 black(parent);
  569.                 rotateLeft(parent);
  570.             }
  571.         } else {  // 被删除节点在右边, 兄弟节点在左边
  572.             if (isRed(sibling)) {  // 兄弟节点是红色
  573.                 black(sibling);
  574.                 red(parent);
  575.                 rotateRight(parent); // 旋转之后,改变兄弟节点,然后node的兄弟节点就为黑色了
  576.                 // 更换兄弟节点
  577.                 sibling = parent.left;
  578.             }
  580.             // 兄弟节点必然是黑色
  581.             if (isBlack(sibling.left) && isBlack(sibling.right)) {   // 表示node的黑兄弟节点的left,right子节点都是黑节点
  582.                 // 兄弟节点没有一个红色子节点(不能借一个节点给你), 父节点要向下跟node的兄弟节点合并
  583.                 /* 首先这里要判断父节点parent的颜色(如果为parent为红色,则根据B树红色节点向其黑色父节点合并原则,parent向下合并,肯定不会 发生下溢; 如果parent为黑色,则说明parent向下合并后,必然也会发生下溢,这里我们当作移除一个叶子节点处理,复用afterRemove */
  584.                 boolean parentBlack = isBlack(parent);
  585.                 // 下面两行染色的代码,是说明parent为红色的情况
  586.                 black(parent);
  587.                 red(sibling);
  588.                 if (parentBlack) { 
  589.                     afterRemove(parent, null);
  590.                 }
  592.             } else {  // 表示兄弟节点至少有一个红色子节点,可以向被删除节点的位置借一个节点
  593.                 // 兄弟节点的左边是黑色, 先将兄弟节点左旋转; 旋转完之后和后面两种的处理方式相同,都是再对父节点进行右旋转
  594.                 if (isBlack(sibling.left)) { 
  595.                     rotateLeft(sibling);
  596.                     sibling = parent.left; // 因为旋转之后,要更改node的sibling,才能复用下面的染色代码.不然出现bug
  597.                 }
  598.                 // 旋转之后的中心节点继承parent的颜色; 旋转之后的左右节点染为黑色
  599.                 // 先染色,再旋转: 肯定要先对node的sibling先染色
  600.                 color(sibling, colorOf(parent));
  601.                 black(sibling.left);
  602.                 black(parent);
  603.                 rotateRight(parent);
  604.             }
  605.         }
  606.     }
  608.     /** * 对node进行左旋转 * * @param grand */
  609.     private void rotateLeft(Node<K, V> grand) { 
  610.         Node<K, V> parent = grand.right;
  611.         Node<K, V> child = parent.left;
  612.         grand.right = child;
  613.         parent.left = grand;
  615.         afterRotate(grand, parent, child);
  616.     }
  618.     /** * 对node进行右旋转 * * @param grand */
  619.     private void rotateRight(Node<K, V> grand) { 
  620.         Node<K, V> parent = grand.left;
  621.         Node<K, V> child = parent.right;
  622.         grand.left = child;
  623.         parent.right = grand;
  625.         afterRotate(grand, parent, child);
  626.     }
  628.     /** * 旋转之后, 更新它们的parent; 并且更新旋转后的高度 * * @param grand * @param parent * @param child */
  629.     private void afterRotate(Node<K, V> grand, Node<K, V> parent, Node<K, V> child) { 
  630.         // 让parent为子树的根节点
  631.         parent.parent = grand.parent;
  632.         // 如果grand是其父节点的left, 则将grand.parent.left = parent;
  633.         if (grand.isLeftChild()) { 
  634.             grand.parent.left = parent;
  635.         } else if (grand.isRightChild()) { 
  636.             grand.parent.right = parent;
  637.             // grand是根节点
  638.         } else { 
  639.             // 更改原来的红黑树根节点(就是哪个桶的位置)
  640.             //table[index(grand.key)] = parent;
  641.             table[index(grand)] = parent;
  642.         }
  644.         // 更新child的parent
  645.         if (child != null)
  646.             child.parent = grand;
  648.         // 更新grand的parent
  649.         grand.parent = parent;
  650.     }
  652.     /** * 根据传入的节点, 返回该节点的前驱节点 (中序遍历) * * @param node * @return */
  653.     private Node<K, V> predecessor(Node<K, V> node) { 
  654.         if (node == null) return node;
  656.         // (中序遍历)前驱节点在左子树当中(node.left.right.right.right...)
  657.         Node<K, V> p = node.left;
  658.         // 左子树存在
  659.         if (p != null) { 
  660.             while (p.right != null) { 
  661.                 p = p.right;
  662.             }
  663.             return p;
  664.         }
  666.         // 程序走到这里说明左子树不存在; 从父节点、祖父节点中寻找前驱节点
  667.         /* * node的父节点不为空 && node是其父节点的左子树时. 就一直往上寻找它的父节点 * 因为node==node.parent.right, 说明你在你父节点的右边, 那么node.parent就是其node的前驱节点 */
  668.         while (node.parent != null && node == node.parent.left) { 
  669.             node = node.parent;
  670.         }
  672.         // 能来到这里表示: 两种情况如下
  673.         // node.parent == null 表示没有父节点(根节点),返回空 ==> return node.parent;
  674.         // node==node.parent.right 说明你在你父节点的右边, 那么node.parent就是其node的前驱节点 ==> return node.parent;
  675.         return node.parent;
  676.     }
  678.     /** * 将node染成color色 * * @param node 需要染色的节点 * @param color 染成的颜色 * @return 返回染色的节点 */
  679.     private Node<K, V> color(Node<K, V> node, boolean color) { 
  680.         if (node == null) return node;
  681.         node.color = color;
  682.         return node;
  683.     }
  685.     /** * 传进来的节点染成黑色 * * @param node * @return */
  686.     private Node<K, V> black(Node<K, V> node) { 
  687.         return color(node, BLACK);
  688.     }
  690.     /** * 传进来的节点染成红色 * * @param node * @return */
  691.     private Node<K, V> red(Node<K, V> node) { 
  692.         return color(node, RED);
  693.     }
  695.     /** * 返回当前节点的颜色 * * @param node * @return 如果传入的节点为空, 默认为黑色 */
  696.     private boolean colorOf(Node<K, V> node) { 
  697.         return node == null ? BLACK : node.color;
  698.     }
  700.     /** * 节点是否为黑色 * * @param node * @return */
  701.     private boolean isBlack(Node<K, V> node) { 
  702.         return colorOf(node) == BLACK;
  703.     }
  705.     /** * 节点是否为红色 * * @param node * @return */
  706.     private boolean isRed(Node<K, V> node) { 
  707.         return colorOf(node) == RED;
  708.     }
  710.     protected static class Node<K, V> { 
  711.         int hash;
  712.         K key;
  713.         V value;
  714.         boolean color = RED;
  715.         Node<K, V> left;
  716.         Node<K, V> right;
  717.         Node<K, V> parent;
  719.         public Node(K key, V value, Node<K, V> parent) { 
  720.             this.key = key;
  721.             int hash = key == null ? 0 : key.hashCode();
  722.             this.hash = hash ^ (hash >>> 16);
  723.             this.value = value;
  724.             this.parent = parent;
  725.         }
  727.         public boolean isLeaf() { 
  728.             return left == null && right == null;
  729.         }
  731.         public boolean hasTwoChildren() { 
  732.             return left != null && right != null;
  733.         }
  735.         public boolean isLeftChild() { 
  736.             return parent != null && this == parent.left;
  737.         }
  739.         public boolean isRightChild() { 
  740.             return parent != null && this == parent.right;
  741.         }
  743.         public Node<K, V> sibling() { 
  744.             if (isLeftChild()) { 
  745.                 return parent.right;
  746.             }
  748.             if (isRightChild()) { 
  749.                 return parent.left;
  750.             }
  751.             return null;
  752.         }
  754.         @Override
  755.         public String toString() { 
  756.             return "Node_" + key + "_" + value;
  757.         }
  758.     }
  759. }

发表评论

表情：
评论列表 （有 0 条评论，45人围观）

还没有评论，来说两句吧...

相关阅读