15_哈希表(Hash Table)

哈希表初识

哈希表，也叫做散列表

它是如何实现高效处理数据的？
假设我们利用哈希表来实现映射，存储三对数据：
put("jack",666)
put("Rose",777)
put("kate",888)

Snip20200907_2.png

  • 利用哈希表添加、搜索、删除的流程都是类似的
    1. 利用哈希函数生成key对应的index，时间复杂度O(1)
    2. 根据index操作定位数组元素，时间复杂度也是O(1)
  • 哈希表是时间换空间的典型应用
  • 哈希函数，也叫做散列函数
  • 哈希表内部的数组元素，很多地方也叫Bucket（桶），整个数组叫Buckets或者Bucket Array

哈希冲突

哈希冲突也叫做哈希碰撞，是指2个不同的key，经过哈希函数计算出相同的结果
key1 != key2,hash(key1) == hash(key2)

解决哈希冲突的常见方法
  • 开发地址法：按照一定的规则向其他地址探测，直到遇到空桶，例如
    • 线性探测，不断的向下探测，直到探测到空桶；
    • 平方探测，按照1^2 、2^2 、3^2不断的向下探测，知道探测到空桶
  • 再哈希法：设计多个哈希函数
  • 链地址法：比如通过链表将同一index的元素串起来
JDK1.8的哈希冲突解决方案
  • 默认使用单向链表将元素串起来
  • 在添加元素时，可能会由单向链表转为红黑树来存储元素，比如当哈希表容量>=64且单向链表的节点数量大于8时
  • 当红黑树节点数量少到一定程度时，又会转为单向链表
  • JDK1.8中的哈希表是使用链表+红黑树解决哈希冲突
  • 为什么使用单链表呢？单次都是从头节点开始遍历、单向链表比双向链表少一个指针，可以节省内存空间
Snip20200907_2.png

哈希函数

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

  1. 先生成key的哈希值（必须是整数）

  2. 再让key的哈希值跟数组的大小进行相关运算，生成一个索引值


    Snip20200907_3.png
  • 为了提高效率，可以使用&位运算取代%运算（前提：将数组的长度设计为2的幂(2^n)，来保证得到的index取值在0～length-1）
    • 2^n 与二进制变换
      2^0 = 1
      2^1 = 10
      2^2 = 100
      2^3 = 1000

    • 2^n - 1 与二进制变换
      2^0 -1 = 0
      2^1 -1 = 01
      2^2 -1 = 011
      2^3 -1 = 0111


      Snip20200907_4.png
  • 良好的哈希函数，让哈希值更加均匀分布，从而减少哈希冲突次数，提高哈希表的性能
如何生成key的哈希值
  • key的常见种类可能有：整数、浮点数、字符串、自定义对象
  • 不同种类的key，哈希值的生成方式不一样，但目标是一致的
    • 尽量让每个key的哈希值是唯一的
    • 尽量让key的所有信息参与运算
1. 整数

整数值当做哈希值，比如10的哈希值就是10，5489的哈希值就是5489 ，也就是 5 * 10^3 + 4 * 10^ + 8 * 10^1 + 9 * 10^0

   public static int hashCode(int value){
        return value;
   }
2. 浮点数

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

public static int hashCode(float value){
      return java.lang.Float.floatToIntBits(value);
}
3. Long和Double
public static int hashCode(long value){
        return (int)(value ^(value>>>32));
    }
public static int hashCode(double value){
        long bits = java.lang.Double.doubleToLongBits(value);
        return (int)(bits ^(bits>>>32));
    }

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

Snip20200907_6.png

4. 字符串的哈希值
  • 字符串是由若干个字符组成的
  • 比如字符串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
  • 在JDMK中，乘数n为31，因为31是一个奇素数，31 * i等价于 (i<<5) - i，JVM已经将31 * i优化成(i<<5) - i
  • 关于31
    • 素数与其他数相乘的结果比其他方式更容易产生唯一性，减少哈希冲突
    • 最终选择31是经过观测分布结构后的选择
public int hashCode(String value) {
        int hashCode = 0;
        int length = value.length();
        for (int i  = 0;i<length;i++){
            char c = value.charAt(i);
            // (hashCode << 5) - hashCode + c
            hashCode = 31 * hashCode + c;
        }
        return hashCode;
    }
5. 自定义对象

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

  • equals：用以解决哈希冲突，判断2个key是否为同一个key，equals需要满足的性质:
    1. 自反性：对于任何非null的x，x.equals(x)必须返回true
    2. 对称性：对于任何非null的x，y，如果x.equals(y)返回true,y.equals(x)必须返回true
    3. 传递性：对于任何非null的x、y、z，如果x.equals(y)、y.equals(z)返回true，那么x.equals(z)必须返回true
    4. 一致性：对于任何非null的x、y，只要equals的比较操作在对象中所用的信息没有被修改，多次调用x.equals(y)就会一致地返回true，或者一致地返回false
    5. 对于任何非null的x，x.equals(null)必须返回false
  • hashCode：用来生成对应索引，必须保证equals为true的2个key的哈希值一样，但是hashCode相等的key，不一定equals为true
  • 在java中，不重写hashCode方法只重写equals会有什么后果？
    可能会导致2个equals为true的key同时存在哈希表中
public class Person {
    private int age;
    private float height;
    private String name;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age &&
                Float.compare(person.height, height) == 0 &&
                Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        int hash = Integer.hashCode(age);
        hash = 31 * hash + Float.hashCode(height);
        hash = 31 * hash + ((name != null) ?name.hashCode():0);
        return hash;
    }
}
哈希值的进一步处理：扰动计算
private int hash(K key){
    if(key == null) return 0;
    int hash = key.hashCode();
    return hash ^ (hash >>> 16);
}

装填因子

装填因子：也叫做负载因子，节点总数量/哈希表桶数组的长度

在JDK1.8的HashMap中，如果装填因子超过0.75，就扩容为原来的2倍

TreeMap vs HashMap

  • 何时选择treeMap
    元素具备可比较性且要求升序遍历
  • 何时选择HashMap
    无序遍历

关于使用%来计算索引

如果使用%来计算索引，建议把哈希表的长度设计为素数（质数），可以大大减少哈希冲突。
不同数据规模对应的最佳素数如下


Snip20200909_1.png

特点：

  • 每个素数略小于前一个素数的2倍
  • 每个素数尽可能接近2的幂(2^n)

HashMap的代码实现

package HashTable;

import Map.LZTreeMap;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class LZHashMap<K,V> {

    private static final boolean RED = false;
    private static final boolean BLACK = true;
    // 数组的初始容量
    private static final int DEFAULT_CAPACITY = 1 << 4;

    //装填因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //节点总数量
    private int size;

    //数组
    private Node<K,V>[] table;

    public LZHashMap(){
        table = new Node[DEFAULT_CAPACITY];
    }

    /**
     * map的大小
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * map是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 清空map
     */
    public void clear(){
        if (size == 0) return;
        size = 0;
        for (int i = 0;i< table.length;i++){
            table[i] = null;
        }
    }

    /**
     * 设值
     */
    public void put(K key,V value){
        //扩容
        resize();

        //生成索引
        int index = index(key);
        Node<K,V> root = table[index];

        // index位置没有元素，也就是不需要解决hash冲突
        // 直接将元素放到index位置即可，也就是index位置红黑树的根节点
        if (root == null){
            root = createNode(key,value,null);
            table[index] = root;
            size++;
            fixAfterPut(root);
            return;
        }

        //index位置有数据，利用红黑树解决哈希冲突
        Node<K,V> parent = root;
        Node<K,V> node = root;
        int cmp = 0;
        K k1 = key;
        int h1 = hash(k1);
        Node<K,V> result = null;
        boolean searched = false; //是否已经搜索过这个key
        do{
            K k2 = node.key;
            int h2 = node.hash;
            if (h1>h2){
                //如果key的哈希值大于node的哈希值，则在node节点的右侧找
                cmp = 1;
            }else if(h1 < h2){
                //如果key的哈希值小于node的哈希值，则在node节点的左侧找
                cmp = -1;
            }else if(Objects.equals(k1,k2)){
                //如果key和node的key相等，说明key相等，则用新的值覆盖原来的值
                cmp = 0;

            } //能来到下面，说明key和node的key不相等
            else if(k1 != null && k2 != null && k1.getClass() == k2.getClass() &&
                    k1 instanceof Comparable && (cmp = ((Comparable)k1).compareTo(k2)) != 0){
                // 如果key和node的key都不等于空，并且是属于同一个类，并且实现了comparable方法，
                // 则利用comparable比较的结果向node的左侧或者右侧找
                // 注意：如果比较的结果相等，也不能说明key相等，这时候需要继续比较
            }else if(searched){
                //如果之前已经搜索过，说明红黑树中没有key与新key相等，那么直接利用内存地址进行比较
                cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
            } else if((node.left != null && node.left != null && (result = node(k1,node.left)) != null) ||
                    (node.right != null && node.right != null && (result = node(k1,node.right)) != null)
                    ){
                // 遍历红黑树的左子树、红黑树的右子树，
                // 如果发现有node的key与key相等，则用新的值覆盖原来的值
                node = result;
                cmp = 0;
            }else {
                // 如果遍历之后没有发现有key相等，
                // 那么说明在这颗红黑树上没有节点的key与新增加的key相等，
                // 那么将新节点添加到节点的左右子树都可以，这里利用内存地址进行比较
                searched = true;
                cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
            }
            parent = node;
            if (cmp<0){
                node = node.left;
            }else if(cmp>0){
                node = node.right;
            }else {
                node.key = key;
                node.value = value;
                node.hash = h1;
                return;
            }
        }while (node != null);

        Node<K,V> newNode = createNode(key,value,parent);
        if (cmp>0){
            parent.right = newNode;
        }else {
            parent.left = newNode;
        }
        size++;

        //添加新节点之后的处理
        fixAfterPut(newNode);
    }

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

    /**
     * 是否包含某个key
     */
    public boolean containsKey(K key){
        return node(key) != null;
    }

    /**
     * 是否包含某个value
     * 遍历数组中的所有节点，判断value是否相等
     */
    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(node.value,value)) return true;
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
        }
        return false;
    }

    /**
     * 遍历
     * 遍历数组中的所有节点
     * @param visitor
     */
    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);
                }
            }
        }
    }

    /**
     * 删除
     * 根据key删除元素
     * @param key
     */
    public void remove(K key){

        //找到key对应的节点，将节点删除
        remove(node(key));
    }

    /**
     * 扩容
     *
     * 扩容方法解析：
     * 1. 扩容条件：装填因子大于0.75
     * 2. 新数组大小：原数组大小的2倍
     * 3. 遍历原数组，发现index位置不为空，则利用队列层序遍历红黑树，
     *    取出每个节点添加到新数组中，注意：由于原数组的key具有唯一性，
     *    所以在将节点添加到新数组中时，不需要考虑key相等的情况，
     *    也就是当发生冲突时不需要遍历红黑树上面的节点来判断key是否存在
     *
     */
    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 = newNode.left = newNode.right = null;
        newNode.color = RED;

        int index = index(newNode);
        Node<K,V> root = table[index];
        if (root == null){
            root = newNode;
            table[index] = root;
            fixAfterPut(root);
            return;
        }

        //添加新的节点到红黑树上面
        Node<K,V> parent = root;
        Node<K,V> node = root;
        int cmp = 0;
        K k1 = newNode.key;
        int h1 = newNode.hash;
        do {
            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);
            }

            parent = node;
            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;
        }
        fixAfterPut(newNode);
    }

    /**
     * 删除node节点
     * @param node
     */
    private void remove(Node<K,V> node){

        //如果node不存在，直接返回
        if (node == null) return;

        // 准备删除的节点，这里为了提供给子类使用，
        // 当删除的是度为2的节点时 ，真正删除的是它的前驱或者后继节点，
        // 为了保证链表中元素的顺序是按照添加顺序，
        // 这时需要将链表中的两个节点互换位置
        Node<K,V> willNode = node;

        size--;

        // 删除的是度为2的节点
        if (node.left != null && node.right != null){
            Node<K,V> s = successor(node); //找到后继节点
            node.key = s.key; //用后继节点的值覆盖度为2的节点的值
            node.value = s.value;
            node.hash = s.hash;
            node = s; //删除后继节点
        }

        //删除node节点，node节点的度必然是1或者0
        //删除叶子节点
        if (node.left == null && node.right == null){
            if (node.parent == null){ //删除的是根节点
                table[index(node)] = null;
            }else if(node == node.parent.left){ // 如果删除节点位于父节点的左侧
                node.parent.left = null;
            }else { // 删除节点位于父节点右侧
                node.parent.right = null;
            }
            //删除节点之后的修复
            fixAfterRemove(node,null);
        }else { //删除度为1的节点，子节点替代删除节点的位置
            Node<K,V> replacement = node.left != null?node.left:node.right;
            replacement.parent = node.parent;
            if (node.parent == null){ //删除的是根节点
                table[index(node)] = replacement;
            }else if (node == node.parent.left){ // 如果删除节点位于父节点的左侧
                node.parent.left = replacement;
            }else { // 删除节点位于父节点右侧
                node.parent.right = replacement;
            }
            //删除节点之后的处理
            fixAfterRemove(node,replacement);
        }

        // 当遍历要求按照添加顺序时，交给子类去处理
        afterRemove(willNode,node);

    }


    /**
     * 根据key找到对应的节点
     * @param key
     * @return
     */
    private Node<K,V> node(K key){
        // index位置的根节点
        Node<K,V> node = table[index(key)];

        // 如果node为空，说明key对应的节点不存在
        // 如果node不为空，判断key是否与这颗红黑树上某个节点的key相等，
        // 相等的节点就是key对应的节点
        return node == null?null:node(key,node);
    }

    /**
     * 判断key是否与红黑树上某个节点的key相等
     * @param k1
     * @param node 红黑树的根节点
     * @return
     */
    private Node<K,V> node(K k1,Node<K,V> node){
        int h1 = hash(k1);
        int cmp = 0;
        Node<K,V> result = null;
        while (node != null){
            K k2 = node.key;
            int h2 = node.hash;
            // 比较哈希值
            if (h1>h2){
                node = node.right;
            }else if(h1 < h2){
                node = node.left;
            }else if(Objects.equals(k1,k2)){ //比较是否equeals
                return node;
            }else if (k1 != null && k2 != null && k1.getClass() == k2.getClass() &&
            k1 instanceof  Comparable && ((cmp = ((Comparable)k1).compareTo(k2)) != 0)){
                // 比较Comparable
                node = cmp>0?node.right:node.left;
            }else if(node.right != null && ((result = node(k1,node.right))!= null)){
                //遍历右子树
                return result;
            }else {
                //遍历左子树
                node = node.left;
            }
        }
        return null;
    }

    /**
     * 根据key生成对应的索引（在桶数组中的位置）
     * @param key
     * @return
     */
    private int index(K key){
        return (hash(key)  & (table.length -1));
    }

    /**
     * 根据节点生成对应的索引（在桶数组中的位置）
     * @param node
     * @return
     */
    private int index(Node<K,V> node){
        return node.hash & (table.length - 1);
    }

    /**
     * 根据key生成对应的hashCode
     * @param key
     * @return
     */
    private int hash(K key){
        if(key == null) return 0;
        int hash = key.hashCode();
        return hash ^ (hash >>> 16);
    }

    /**
     * 添加之后的修复操作
     * 为了维护红黑树的性质
     * @param node
     */
    private void fixAfterPut(Node<K,V> node) {
        //判断情况1，是否是根节点
        if (node.parent == null) {
            black(node);
            return;
        }

        //判断情况2，父节点是否是黑色
        if(isBlack(node.parent)) return;

        //判断情况4，叔父节点是否是红色，如果是红色，不需要旋转，B树节点溢出
        if (isRed(node.parent.sibling())){
            black(node.parent);
            black(node.parent.sibling());
            Node<K,V> parent = red(node.parent.parent);
            fixAfterPut(parent);
            return;
        }

        //符合情况3，旋转，B树节点不会溢出
        Node<K,V> parent = node.parent;
        Node<K,V> grand = red(parent.parent); //将祖父节点染成红色

        if (parent.isLeftChild()){  //L
            if (node.isLeftChild()){ //LL
                black(parent);
            }else { //LR
                black(node);
                rotateLeft(parent);
            }
            rotateRight(grand);
        }else { //R
            if (node.isLeftChild()){ //RL
                black(node);
                rotateRight(parent);
            }else {  //RR
                black(parent);
            }
            rotateLeft(grand);
        }
    }

    /**
     * 删除之后的修复操作
     * @param node
     * @param replaceNode
     */
    private void fixAfterRemove(Node<K,V> node, Node<K,V> replaceNode) {

        //如果符合情况1，被删除节点是红色节点，那么直接删除即可
        if (isRed(node)) return;

        //如果符合情况2，被删除节点的替代节点是红色节点，那么将替代节点染成黑色即可
        if (isRed(replaceNode)){
            black(replaceNode);
            return;
        }

        //符合情况三，被删除节点是黑色叶子节点
        Node<K,V> parent = node.parent;

        //3.1 被删除节点是根节点，那么直接删除即可
        if (parent == null) return;

        // 判断被删除的node是左还是右
        boolean left = parent.left == null || node.isLeftChild();
        Node<K,V> sibling = left ? parent.right : parent.left;
        // 黑色叶子节点被删除后，会导致B树节点下溢
        if (left){  //被删除的节点在左边，兄弟节点在右边
            // 3.2 兄弟节点是红色
            // 染色：兄弟节点染成黑色，父节点染成红色
            // 旋转：父节点左旋，让兄弟节点的左子节点成为兄弟节点，让原来的兄弟节点成为祖父节点
            if (isRed(sibling)){
                black(sibling);
                red(parent);
                rotateLeft(parent);
                //更换兄弟节点
                sibling = parent.right;
            }

            // 兄弟节点必然是黑色，
            // 3.3 如果兄弟节点至少有一个红色子节点，可以向兄弟节点借一个
            if (isRed(sibling.left) || isRed(sibling.right)){
                // 兄弟节点的左侧是红色子节点，
                // 符合RL的情况，让兄弟节点先左旋，使红色子节点成为新的兄弟节点
                if (isBlack(sibling.right)){
                    rotateLeft(sibling);
                    sibling = parent.right;
                }

                //染色
                color(sibling,colorOf(parent));
                black(parent);
                black(sibling.right);

                //父节点右旋
                rotateLeft(parent);
            }else{
                // 3.4 兄弟节点没有一个红色子节点，父节点向下合并
                boolean parentBlack = isBlack(parent);
                red(sibling);
                black(parent);
                //如果parent是黑色节点，会导致parent也下溢
                if (parentBlack){
                    fixAfterRemove(parent,null);
                }
            }
        }else { //被删除的节点在右边，兄弟节点在左边

            // 3.2 兄弟节点是红色
            // 染色：兄弟节点染成黑色，父节点染成红色
            // 旋转：父节点右旋，让兄弟节点的右子节点成为兄弟节点，让原来的兄弟节点成为祖父节点
            if (isRed(sibling)){
                black(sibling);
                red(parent);
                rotateRight(parent);
                //更换兄弟节点
                sibling = parent.left;
            }

            // 兄弟节点必然是黑色，
            // 3.3 如果兄弟节点至少有一个红色子节点，可以向兄弟节点借一个
            if (isRed(sibling.left) || isRed(sibling.right)){
                // 兄弟节点的右侧是红色子节点，
                // 符合LR的情况，让兄弟节点先左旋，使红色子节点成为新的兄弟节点
                if (isBlack(sibling.left)){
                    rotateLeft(sibling);
                    sibling = parent.left;
                }

                //染色
                color(sibling,colorOf(parent));
                black(parent);
                black(sibling.left);

                //父节点右旋
                rotateRight(parent);
            }else{
                // 3.4 兄弟节点没有一个红色子节点，父节点向下合并
                boolean parentBlack = isBlack(parent);
                red(sibling);
                black(parent);
                //如果parent是黑色节点，会导致parent也下溢
                if (parentBlack){
                    fixAfterRemove(parent,null);
                }
            }
        }
    }

    //左旋
    private void rotateLeft(Node<K,V> grand){
        Node<K,V> parent = grand.right;
        Node<K,V> child = parent.left;
        grand.right = child;
        parent.left = grand;
        afterRote(grand,parent,child);
    }

    //右旋
    private void rotateRight(Node<K,V> grand){
        Node<K,V> parent = grand.left;
        Node<K,V> child = parent.right;
        grand.left = child;
        parent.right = grand;
        afterRote(grand,parent,child);
    }

    private void afterRote(Node<K,V> grand, Node<K,V> parent, Node<K,V> child){

        // 更新parent的父节点
        parent.parent = grand.parent;

        if (grand.isLeftChild()){
            grand.parent.left = parent;
        }else if(grand.isRightChild()){
            grand.parent.right = parent;
        }else {
            table[index(grand)] = parent;
        }

        //更新child
        if (child != null){
            child.parent = grand;
        }

        //更新grand的父节点
        grand.parent = parent;
    }

    /**
     * 找到后继节点
     */
    public Node<K,V> successor(Node<K,V> node){
        if(node == null) return null;
        if (node.right != null){
            Node<K,V> rightNode = node.right;
            while (rightNode.left != null){
                rightNode = rightNode.left;
            }
            return rightNode;
        }

        while (node.parent != null && node == node.parent.right){
            node = node.parent;
        }
        return node.parent;
    }

    /**
     * 将节点染色
     * @param node
     * @param color
     * @return 染色后的节点
     */
    private Node<K,V> color(Node<K,V> node, boolean color){
        if (node == null) return node;
        node.color = color;
        return node;
    }

    /**
     * 将节点染成红色
     * @param node
     * @return
     */
    private Node<K,V> red(Node<K,V> node){
        return color(node,RED);
    }

    /**
     * 将节点染成黑色
     * @param node
     * @return
     */
    private Node<K,V> black(Node<K,V> node){
        return color(node,BLACK);
    }

    /**
     * 返回节点的颜色
     * @param node
     * @return
     */
    private boolean colorOf(Node<K,V> node){
        return node == null ? BLACK: node.color;
    }

    /**
     * 判断节点是否是黑色节点
     * @param node
     * @return
     */
    private boolean isBlack(Node<K,V> node){
        return colorOf(node) == BLACK;
    }

    /**
     * 判断节点是否是红色节点
     * @param node
     * @return
     */
    private boolean isRed(Node<K,V> node){
        return colorOf(node) == RED;
    }

    /**
     * 创建节点
     * 这里是主要为了当遍历顺序要求按照添加顺序的时候，提供给子类使用，
     * 需要维护一个链表将所有的节点按照添加串起来，
     * 链表的节点需要继承自Node，并且维护prev和next属性
     * @param key
     * @param value
     * @param parent
     * @return
     */
    protected Node<K,V> createNode(K key,V value,Node<K,V> parent){
        return new Node<>(key,value,parent);
    }

    /**
     * 删除节点之后的操作
     * 这里是主要为了当遍历顺序要求按照添加顺序的时候，提供给子类使用，
     * 需要维护一个链表将所有的节点按照添加串起来
     * 当删除某个元素的时候，需要将链表上面的元素一起删除
     * @param willNode 要删除的节点
     * @param removeNode 真正删除的节点
     */
    protected void afterRemove(Node<K,V> willNode,Node<K,V> removeNode){ }

    /**
     * 节点
     * @param <K>
     * @param <V>
     */
    protected static class Node<K,V>{
        public K key;
        public int hash;
        public V value;
        public Node<K,V> left;
        public Node<K,V> right;
        public Node<K,V> parent;
        boolean color = RED;
        public Node(K key, V value, Node<K,V> parent){
            this.key = key;
            int hash = key == null ? 0: key.hashCode();
            this.hash = hash ^ (hash >>>16);
            this.value = value;
            this.parent = parent;
        }

        /**
         * 是否是叶子节点
         * @return
         */
        public boolean isLeaf() {
            return left == null && right == null;
        }

        /**
         * 是否有两个子树
         * @return
         */
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        /**
         * 是否是父节点的左子节点
         * @return
         */
        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        /**
         * 是否是父节点的右子节点
         * @return
         */
        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

        /**
         * 返回兄弟节点
         * @return 返回兄弟节点
         */
        public Node<K,V> sibling(){
            if (isLeftChild()) {
                return parent.right;
            }

            if (isRightChild()) {
                return parent.left;
            }
            return null;
        }

    }

    public static abstract class Visitor<K,V>{
        boolean stop;
        public abstract boolean visit(K key,V value);
    }

}

LinkedHashMap

在HashMap的基础上维护元素的添加顺序，使得遍历的结果是遵从添加顺序的

代码实现：


 *  为了维护节点的添加顺序，能够满足按照节点添加顺序遍历节点的需求
 *  LZLinkedHashMap 继承自 LZHashMap
 */
package HashTable;

import java.util.Objects;

public class LZLinkedHashMap<K,V> extends LZHashMap<K,V>{

    //指向链表的第一个节点
    private LinkedNode<K,V> first;
    //指向链表的最后一个节点
    private LinkedNode<K,V> last;

    /**
     * 创建节点之后，添加到链表的尾部
     * @param key
     * @param value
     * @param parent
     * @return
     */
    @Override
    protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
        LinkedNode<K,V> node = new LinkedNode<>(key,value,parent);
        if (first == null){
            first = last = node;
        }else {
            last.next = node;
            node.prev = last;
            last = node;
        }

        return node;
    }

    /**
     * 在删除节点之后，将节点从链表中删除
     * 这里要注意，如果删除的是度为2的节点，真正删除的是前驱或者后继节点
     * 为了维护节点的添加顺序，需要先将两个节点互换位置
     * @param willNode 要删除的节点
     * @param removeNode 真正删除的节点
     */
    @Override
    protected void afterRemove(Node<K, V> willNode, Node<K, V> removeNode) {
        LinkedNode<K,V> node1 = (LinkedNode<K,V>)willNode;
        LinkedNode<K,V> node2 = (LinkedNode<K,V>)removeNode;

        if (node1 != node2){
            // 交换linkedWillNode和linkedRemovedNode在链表中的位置

            //交换prev
            LinkedNode<K,V> tmp = node1.prev;
            node1.prev = node2.prev;
            node2.prev = tmp;
            if (node1.prev == null){
                first = node1;
            }else {
                node1.prev.next = node1;
            }

            if (node2.prev == null){
                first = node2;
            }else {
                node2.prev.next = node2;
            }

            //交换next
            tmp = node1.next;
            node1.next = node2.next;
            node2.next = tmp;

            if (node1.next == null){
                last = node1;
            }else {
                node1.next.prev = node1;
            }

            if (node2.next == null){
                last = node2;
            }else {
                node2.next.prev = node2;
            }

        }

        // 删除node
        LinkedNode<K,V> prev = node2.prev;
        LinkedNode<K,V> next = node2.next;
        if (prev == null){
            first = next;
        }else {
            prev.next = next;
        }

        if (next == null){
            last = prev;
        }else {
            next.prev = prev;
        }
    }

    /**
     * 清空哈希表
     */
    @Override
    public void clear() {
        super.clear();
        first = null;
        last = null;
    }

    /**
     * 是否包含value
     * @param value
     * @return
     */
    @Override
    public boolean containsValue(V value) {
        // 直接遍历链表元素
        LinkedNode<K,V> node = first;
        while (node != null){
            if (Objects.equals(value,node.value)) return true;
            node = node.next;
        }
        return false;
    }

    /**
     * 遍历
     * @param visitor
     */
    @Override
    public void traversal(Visitor<K, V> visitor) {
        // 遍历链表、即按照添加顺序遍历哈希表元素
        if (visitor == null) return;
        LinkedNode<K,V> node = first;
        while (node != null){
            if (visitor.visit(node.key, node.value)) return;
            node = node.next;
        }
    }

    /**
     * LinkedNode 继承自 Node
     * 维护prev和next属性
     * @param <K>
     * @param <V>
     */
    private static class LinkedNode<K,V> extends Node<K,V>{
        LinkedNode<K,V> prev;
        LinkedNode<K,V> next;
        public LinkedNode(K key, V value, Node<K, V> parent){
            super(key, value, parent);
        }
    }

}

根据需求，也可以使用HashMap或者LinkedHashMap来实现集合（Set）

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 202,100评论 5赞 474
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 84,862评论 2赞 378
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 148,993评论 0赞 335
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,309评论 1赞 272
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,303评论 5赞 363
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,421评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,830评论 3赞 393
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,501评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,689评论 1赞 295
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,506评论 2赞 318
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,564评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,286评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,826评论 3赞 305
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,875评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,114评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,705评论 2赞 348
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,269评论 2赞 341