自己手写HashMap——红黑树的Java实现

你好，这篇文章是《自己手写HashMap》的第一篇。 在 java 7之前，HashMap是用数组（hash桶）+链表的形式实现的，大概的原理就是对key求hashCode，hashCode对当前数组的大小求模即为key对应的数组下标，hashCode值相同放在同一个下标，按链表的形式储存， 大概像下面这样

（图片来自网络）

对，就是这么简单。当然java7以及以前，大家对HashMap的性能一直是存疑的，因为如果出现大量的hashCode碰撞的话，那就不可避免的要花费O(N)的查找时间，这跟普通线性表没啥区别。 所以在java8的时候对HashMap的结构进行了改整，基本结构依然是数组（hash桶）+链表的形式，但是求hashCode的时候加入了扰动函数用来减少碰撞，之前的普通链表也改为了红黑树（在元素个数极少的时候依然是普通链表）， 大概像下面这样

（图片来自网络） （以上图片仅供参考，并不代表真实数据）

这次主要讲的就是红黑树，进入正题。

1.红黑树的基本定义简单概述

红黑树是一棵二叉搜索树（什么是二叉搜索树？），跟普通的二叉树不同的是，它在每个结点上增加了一个颜色属性，就是red或black，然后通过颜色上的约束让数据比较均衡的分布在各个结点，红黑树就是一颗近似的平衡树，而为什么不直接使用平衡二叉树，当然是为了平衡各种操作的性能。 篇幅有限，具体红黑树性质点这里，但是不看也没关系，因为后边贴代码的时候会详细讲

2.为什么选择红黑树（红黑树的性能）

这里直接讲结论，一颗有n个内部结点的红黑树的高度最多为2lg(n+1)， 对红黑树的基本增删查操作，包括求最大最小值，其时间复杂度最坏为O(lgn)。

3.红黑树的基本操作（添加、遍历、删除）

接下来就是代码部分

（1）实体类组织结构

1.首先要有一个对象用来储存当前节点的信息，包含以下几个属性

1. 颜色，red或者black、
2. 当前结点的key和value
3. 父结点（根结点的父结点为null）
4. 左子结点
5. 右子结点

如下

import java.io.Serializable;
import java.util.Objects;

public class Node<K, V> implements Serializable , Comparable<Node<K, V>>{

    private int color;
    private K key;
    private V value;
    private Node<K, V> pro;
    private Node<K, V> left;
    private Node<K, V> right;

    public Node(int color, K key, V value, Node<K, V> pro, Node<K, V> left, Node<K, V> right) {
        this.color = color;
        this.key = key;
        this.value = value;
        this.pro = pro;
        this.left = left;
        this.right = right;
    }

    public Node() {
    }

    public int getColor() {
        return color;
    }

    public void setColor(int color) {
        this.color = color;
    }

    public K getKey() {
        return key;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public Node<K, V> getPro() {
        return pro;
    }

    public void setPro(Node pro) {
        this.pro = pro;
    }

    public Node<K, V> getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node<K, V> getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }


    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node<?, ?> node = (Node<?, ?>) o;
        return Objects.equals(key, node.key);
    }

    @Override
    public int hashCode() {
        return Objects.hash(key);
    }

    @Override
    public int compareTo(Node<K, V> o) {
        return this.hashCode() - o.hashCode();
    }
}

复制代码

这里重写了equals、hashCode和compareTo方法，主要是为了之后的代码写起来方便，因为经常要用到比较操作，并且这里加入了泛型

2.其次就是红黑树对象

1. 需要有一个属性来保存根结点

基本结构就像这样

public class Tree<K, V> implements Serializable, Iterable<Node<K, V>> {

    private Node<K, V> root;

    private int size;

    private int BLACK = 0;
    private int RED = 1;

    public Tree() {
        this.size = 0;
    }

    public int size() {
        return this.size;
    }
}
复制代码

继承Iterable是因为之后要实现迭代器

目前为止要实现一棵红黑树，用到的实体类就这么多。

（2）put操作

插入数据并不难，难的是必须要在数据插入之后当前树依然符合红黑树的性质，所以我们先来看一下红黑树的约束条件

1. 每个结点要么是红色的要么是黑色的
2. 根结点是黑色的
3. 红色结点的两个子结点必须是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点（最后一个没有分支的子结点）的简单路径上，均包含相同数目的黑色结点

乍一看规则还挺多，其实红黑树的最终追求就是希望结点可以平均分布，每个分支上的高度不要相差太多，之所以为每个结点添加颜色约束也是为了达到这个目的。 而为了实现这个目的，我们需要在插入数据之后，调整红黑树以符合性质

先一步一步来，写一个方法来将一个结点插入到当前树

public void put(K key, V value) {
        Node<K, V> z = new Node<>();
        z.setKey(key);
        z.setValue(value);
        z.setColor(RED);
        this.size++;

        Node<K, V> y = null;
        Node<K, V> x = root;
        while (x != null) {
            y = x;
            int sp = z.compareTo(x);
            if (sp < 0) {
                x = x.getLeft();
            } else if (sp > 0) {
                x = x.getRight();
            } else {
                x.setValue(value);
                this.size--;
                return;
            }
        }
        z.setPro(y);

        if (y == null) {
            root = z;
        } else if (z.compareTo(y) < 0) {
            y.setLeft(z);
        } else if (z.compareTo(y) > 0) {
            y.setRight(z);
        }


        //调整红黑树
        this.fixup(z);

    }
复制代码

以上，我们一开始新建了一个红色结点，将key value 值 set进去，并将树的大小加一，之所以要把新结点设成红色，是因为插入一个红色结点要比插入一个黑色结点要简单的多，下边会详细讲。 之后通过循环将新结点和当前节点比较大小，来确定新结点插入的位置，小的插入左子节点，大的插入右子结点，当然如果结点相等，直接覆盖就好了。 这还不算完，找到插入位置后要设置一下新结点的父结点，并将父结点的子结点指向新结点，如果当前根结点为空，就直接将新结点设置成根结点就好了， 最后，插入新的结点之后可能会违反红黑树的性质，所以我们调用fixup方法来调整红黑树

private void fixup(Node<K, V> z) {

        while (z.getPro() != null && z.getPro().getColor() == RED) {
            if (z.getPro().getPro() != null) {
                if (z.getPro().equals(z.getPro().getPro().getLeft())) {
                    Node<K, V> y = z.getPro().getPro().getRight();
                    if (y != null && y.getColor() == RED) {
                        z.getPro().setColor(BLACK);
                        y.setColor(BLACK);
                        z.getPro().getPro().setColor(RED);
                        z = z.getPro().getPro();
                    } else {
                        if (z.equals(z.getPro().getRight())) {
                            z = z.getPro();
                            this.leftRotate(z);
                        }
                        z.getPro().setColor(BLACK);
                        z.getPro().getPro().setColor(RED);
                        this.rightRotate(z.getPro().getPro());
                    }
                } else if (z.getPro().equals(z.getPro().getPro().getRight())) {
                    Node<K, V> y = z.getPro().getPro().getLeft();
                    if (y != null && y.getColor() == RED) {
                        z.getPro().setColor(BLACK);
                        y.setColor(BLACK);
                        z.getPro().getPro().setColor(RED);
                        z = z.getPro().getPro();
                    } else {
                        if (z.equals(z.getPro().getLeft())) {
                            z = z.getPro();
                            this.rightRotate(z);
                        }
                        z.getPro().setColor(BLACK);
                        z.getPro().getPro().setColor(RED);
                        this.leftRotate(z.getPro().getPro());
                    }
                }
            }
        }
        this.root.setColor(BLACK);
    }
复制代码

来简单的分析一下，当我们插入一个新结点的时候，哪些性质可能会被破坏，性质1肯定是成立的，因为我们插入的是一个红色结点，所以性质4也是成立的，但是性质2可能会被破坏，如果父结点也是红色的，那么性质3也会被破坏。 所以满足性质2和3是我们调整当前树的目标， 现在是不是在想，如果我们插入的是一个黑色结点，性质2、3不就满足了，但是如果那样的话，性质4就不满足了，我们可能需要调整非常多的结点才能满足所有性质，如果是插入一个红色结点的话，我们只需要把调整目标放在左或者右一边就好了，继续往下看， 我们知道了现在需要做的事情，就是调整树结构满足性质2和3， 简单思考一下，如果性质2被破坏，那么原因肯定是当前根节点为空，而违反性质3，那肯定是新结点的父节点为红色，因为根结点必须为黑色，所以新节点的父结点必然不是根结点， 所有性质2和3并不会同时违反，单次插入操作，只会违反其中一个 ，这样推理的话，情况就变的简单多了。 性质2比较好处理，直接将新结点或者说根结点设置成黑色就好，违反性质3就稍微了复杂一点，这里总共存在6种情况，但是因为插入左边和插入右边是对称操作的原因，我们只需要思考其中三种情况就好，另外三种反过来操作即可。

先声明一点，违反性质3仅在新结点的父结点是红色的情况下

1. 新结点的叔结点是红色的
2. 新结点的叔结点是黑色的且新结点是一个右子结点
3. 结点的叔结点是黑色的且新结点是一个左子结点

叔结点就是与当前节点的父结点平级的另一个结点

第一种情况就是新结点，父结点，叔结点都是红色的，试想一下，如果父节点是红色的，那么父结点的父结点必定是黑色的，所以将父结点和叔结点都着为黑色来满足性质3，但是因为黑色结点的增加，会违反性质4，所以将父节点的父节点着为红色（上边代码8-11行），至此情况一解决。 如下图  第二种情况，叔结点是黑色的，新结点是右子结点，聪明的同学可以想到，这个和情况三是对称的，所以我们可以通过一些操作，将这两种情况互转，然后处理其中一种即可，然而如何才能在保证其他三条性质不会违反的情况下转换树的结构呢，那就是旋转。 旋转分为左旋和右旋

左旋

解析一下左旋操作，左旋就是将当前结点（E）移动到左边，让它的右子结点（S）成为它的父结点并顶替之前它的位置，然后让它的右子结点的左子结点成为它的新右子结点，说起来很绕，但是看图其实很简单。

private void leftRotate(Node<K, V> x) {
        Node<K, V> y = x.getRight();
        x.setRight(y.getLeft());
        if (y.getLeft() != null) {
            y.getLeft().setPro(x);
        }
        y.setPro(x.getPro());
        if (x.getPro() == null) {
            this.root = y;
        } else if (x.equals(x.getPro().getLeft())) {
            x.getPro().setLeft(y);
        } else {
            x.getPro().setRight(y);
        }
        y.setLeft(x);
        x.setPro(y);
    }
复制代码

这样移动后我想大家最担心就是大小顺序问题了，我们看将右子节点（S）上移成为父结点，因为右子结点是肯定比当前节点（E）大的，换句话说就是E是肯定比S小的，所以让E成为S的左子结点并没有什么问题，同理S的左子结点也是比E要大的，因为比E小的节点并不会插入到S的子结点上。 左旋搞明白了，右旋就简单了，我们把刚才的操作反向再来一遍就是右旋了。

右旋

private void rightRotate(Node<K, V> x) {
        Node<K, V> y = x.getLeft();
        x.setLeft(y.getRight());
        if (y.getRight() != null) {
            y.getRight().setPro(x);
        }
        y.setPro(x.getPro());
        if (x.getPro() == null) {
            this.root = y;
        } else if (x.equals(x.getPro().getLeft())) {
            x.getPro().setLeft(y);
        } else {
            x.getPro().setRight(y);
        }

        y.setRight(x);
        x.setPro(y);
    }
复制代码

（图片来自网络）

我们通过一个简单的左旋，可以将情况2转换为情况3（13-16），因为新结点和父节点都为红色，所以并不会影响除性质3以外的其他性质，然后我们处理情况3，最直观的办法就是把父结点着为黑色，这样性质3就不会冲突了，但是性质4又不符合了，那怎么办，为了平衡性质4，我们再把父结点的父结点着为红色，这样做性质3性质4就都满足了。但是仔细想想，如果父结点的父结点是根结点怎么办，岂不是又不符合性质2了，所以目前来看只要解决最后一个问题，调整就可以立马完成，但是该如何解决最后一个问题呢， 其实这时候我们只需要在不违反其他性质的同时，转换树的结构就好——右旋 如下

至此，红黑树的调整工作就圆满达成了，其实以上的操作目的，都是尽量在移动最少的结点下，把红黑树调整到合法的状态 现在再想想如果我们一开始插入的是黑色结点而不是红色结点，那么每次插入的时候性质4都会被违反，但如果插入的是一个红色结点，那么只会可能违反性质2或性质3，也有可能不会违反任何性质。

总结

到此，插入一条数据过操作就结束了，我们来简单总结一下，先按照普通二叉搜索树的方式，将一条数据插入到合适的位置，然后如果红黑树的性质被违反的话，我们通过变色和旋转，局部调整树的结构，使其整体符合红黑树的约束条件，插入操作结束

（3）遍历、查找

红黑树的遍历跟普通二叉搜索树的遍历方式一样，遍历方式可分为中序、先序、后序遍历，当然也有层级遍历，我们先用中序遍历的方式来实现，所谓中序遍历，就是当前输出的结点对象，在其左子结点和右子结点的中间输出，以下是通过递归实现

public void inorder(Node<K, V> x){
        if(x!=null){
            inorder(x.getLeft());
            System.out.println(x.getKey() + ":" + x.getValue());
            inorder(x.getRight());
        }
    }
复制代码

然后测试一下

public static void main(String[] args) {
        Tree<String, Integer> tree = new Tree<>();
        tree.put("1", 333);
        tree.put("12", 3331);
        tree.put("41", 3313);
        tree.put("21", 3133);
        tree.put("4", 33343);
        tree.put("33", 3353);

       tree.inorder(tree.getRoot());


    }
复制代码

我们发现中序遍历就是按照从小到大输出的。

先序和后序遍历只要移动一下当前结点输出的位置即可。

递归的方式实现很简单，但是对于大多数情况下，递归需要频繁的压栈，我们可以通过迭代的方式来改善这种情况， 既然要迭代，我们就来实现一下jdk自带的迭代器好了，因为这样我们以后就可以用迭代器或增强for循环的方式来遍历了。

@Override
    public Iterator<Node<K, V>> iterator() {
        return new Iter();
    }

    private class Iter implements Iterator<Node<K, V>> {

        List<Node<K, V>> array;

        int cur;

        public Iter() {
            cur = 0;
            array = new ArrayList<>();
            Stack<Node<K, V>> stack = new Stack<>();
            Node<K, V> next = root;
            while (true) {
                while (next != null) {
                    stack.push(next);
                    next = next.getLeft();
                }
                if (stack.isEmpty()) break;
                next = stack.pop();
                array.add(next);
                next = next.getRight();
            }
        }

        @Override
        public boolean hasNext() {
            return cur < array.size();
        }

        @Override
        public Node<K, V> next() {
            Node<K, V> node = array.get(cur);
            cur++;
            return node;
        }
    }

复制代码

首先我们实现了迭代器，然后通过while循环的方式展开递归，先用类似于扫描的方式，循环把所有左子结点放入一个临时队列，最后将队列的结点取出，找到它的右子结点，进入下一次循环。

测试一下

public static void main(String[] args) {
        Tree<String, Integer> tree = new Tree<>();
        tree.put("1", 333);
        tree.put("12", 3331);
        tree.put("41", 3313);
        tree.put("21", 3133);
        tree.put("4", 33343);
        tree.put("33", 3353);

       for(Node node : tree){
           System.out.println(node.getKey() + ":" + node.getValue());
       }


    }
复制代码

相比遍历， 查找 就简单多了。

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

    private Node<K, V> getNode(K key) {
        if (this.root == null)
            return null;
        Node<K, V> x = this.root;
        while (x != null && !x.getKey().equals(key)) {
            if (key.hashCode() - x.getKey().hashCode() < 0) {
                x = x.getLeft();
            } else if (key.hashCode() - x.getKey().hashCode() > 0) {
                x = x.getRight();
            }
        }
        return x;
    }
复制代码

* 拓展 求最大值与最小值

public Node<K, V> getMaximum(Node<K, V> node) {
        while (node.getLeft() != null) {
            node = node.getRight();
        }
        return node;
    }
    public Node<K, V> getMinimum(Node<K, V> node) {
        while (node.getLeft() != null) {
            node = node.getLeft();
        }
        return node;
    }
复制代码