java数据结构之红黑树实现hashMap源码的代码详情-代码-最代码

首页>代码>java数据结构之红黑树实现hashMap源码>/hashMap/src/com/mjy/map/HashMap.java
001package com.mjy.map;
002 
003import com.mjy.printer.BinaryTreeInfo;
004import com.mjy.printer.BinaryTrees;
005 
006import java.util.LinkedList;
007import java.util.Objects;
008import java.util.Queue;
009 
010/**
011 * ***************************************************
012 * 
013 * @ClassName HashMap
014 * @Description 描述
015 * @Author maojianyun
016 * @Date 2020/1/10 13:53
017 * @Version V1.0 ****************************************************
018 **/
019@SuppressWarnings({ "unchecked", "unused" })
020public class HashMap<K, V> implements Map<K, V> {
021 
022    private final static boolean RED = false;
023    private final static boolean BLACK = true;
024    private Node<K, V>[] table;
025    private int size;
026    private static final int DEFAULT_CAPACITY = 1 << 4;
027    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
028    public HashMap() {
029        table = new Node[DEFAULT_CAPACITY];
030    }
031 
032    public int size() {
033        return size;
034    }
035 
036    public boolean isEmpty() {
037        return size == 0;
038    }
039 
040    public void clear() {
041        if (size == 0) {
042            return;
043        }
044        size = 0;
045        for (int i = 0; i < table.length; i++) {
046            table[i] = null;
047        }
048    }
049 
050    public V put(K key, V value) {
051        resize();
052        int index = index(key);
053        // 取出index位置的红黑树根节点
054        Node<K, V> root = table[index];
055        if (root == null) {
056            root = new Node<K, V>(key, value, null);
057            table[index] = root;
058            size++;
059            // 修复红黑树性质
060            afterPut(root);
061            return null;
062        }
063        // 添加新的节点到红黑树上面
064        Node<K, V> parent = root;
065        Node<K, V> node = root;
066        int cmp = 0;
067        K k1 = key;
068        int h1 = k1 == null ? 0 : k1.hashCode();
069        Node<K, V> result = null;
070        boolean searched = false; // 是否已经搜索过这个key
071        do {
072            parent = node;
073            K k2 = node.key;
074            int h2 = node.hash;
075            if (h1 > h2) {
076                cmp = 1;
077            } else if (h1 < h2) {
078                cmp = -1;
079            } else if (Objects.equals(k1, k2)) {
080                cmp = 0;
081            } else if (k1 != null && k2 != null
082                    && k1.getClass() == k2.getClass() 
083                    && k1 instanceof Comparable
084                    && (cmp = ((Comparable<K>) k1).compareTo(k2)) != 0) {
085 
086            } else if (searched) { // 已经扫描了
087                cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
088            } else {
089                if ((node.left != null && (result = node(node.left, k1)) != null)
090                        || (node.right != null && (result = node(node.right, k1)) != null)) {
091                    // 已经存在这个key
092                    node = result;
093                    cmp = 0;
094                } else { // 不存在这个key
095                    searched = true;
096                    cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
097                }
098            }
099            if (cmp > 0) {
100                node = node.right;
101            } else if (cmp < 0) {
102                node = node.left;
103            } else { // 相等
104                V oldValue = node.value;
105                node.key = key;
106                node.value = value;
107                node.hash = h1;
108                return oldValue;
109            }
110        } while (node != null);
111        Node<K, V> newNode = new Node<K, V>(key, value, parent);
112        if (cmp > 0) {
113            parent.right = newNode;
114        } else {
115            parent.left = newNode;
116        }
117        size++;
118        afterPut(newNode);
119        return null;
120    }
121 
122    public V get(K key) {
123        Node<K, V> node = node(key);
124        return node != null ? node.value : null;
125    }
126 
127    public V remove(K key) {
128        return remove(node(key));
129    }
130 
131    public boolean containsKey(K key) {
132        return node(key) != null;
133    }
134 
135    public boolean containsValue(V value) {
136        if (size == 0) {
137            return false;
138        }
139        for (int i = 0; i < table.length; i++) {
140            if (table[i] == null) {
141                continue;
142            }
143            Queue<Node<K, V>> queue = new LinkedList<>();
144            queue.offer(table[i]);
145            while (!queue.isEmpty()) {
146                Node<K, V> node = queue.poll();
147                if (Objects.equals(value, node.value)) {
148                    return true;
149                }
150                if (node.left != null) {
151                    queue.offer(node.left);
152                }
153                if (node.right != null) {
154                    queue.offer(node.right);
155                }
156            }
157        }
158        return false;
159    }
160 
161    public void traversal(Visitor<K, V> visitor) {
162        if (size == 0 || visitor.stop) {
163            return;
164        }
165        Queue<Node<K, V>> queue = new LinkedList<>();
166        for (int i = 0; i < table.length; i++) {
167            if (table[i] == null) {
168                continue;
169            }
170            queue.offer(table[i]);
171            while (!queue.isEmpty()) {
172                Node<K, V> node = queue.poll();
173                visitor.stop = visitor.visit(node.key, node.value);
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    }
183 
184    /**
185     * 删除node
186     *
187     * @param node
188     * @return
189     */
190    private V remove(Node<K, V> node) {
191        if (node == null) {
192            return null;
193        }
194        V oldValue = node.value;
195        if (node.hasTwoChildren()) { // 度为2的节点
196            // 找到后继节点
197            Node<K, V> su = successor(node);
198            // 用后继节点的值覆盖度为2的节点的值
199            node.key = su.key;
200            node.value = su.value;
201            node.hash = su.hash;
202            // 删除后继节点
203            node = su;
204        }
205        // 删除node节点（node的度必然是1或者0）
206        // 如果度为1、则返回的是其子节点
207        Node<K, V> replacement = node.left != null ? node.left : node.right;
208        int index = index(node);
209        if (replacement != null) { // 删除度为1的节点
210            replacement.parent = node.parent;
211            if (node.parent == null) {
212                table[index] = replacement;
213            } else if (node.isLeftChild()) {
214                node.parent.left = replacement;
215            }
216            if (node.isRightChild()) {
217                node.parent.right = replacement;
218            }
219            // 删除节点之后的处理
220            afterRemove(replacement);
221        } else if (node.parent == null) { // node是叶子节点并且是根节点
222            table[index] = null;
223        } else { // node是叶子节点，但不是根节点
224            if (node == node.parent.left) {
225                node.parent.left = null;
226            } else { // node == node.parent.right
227                node.parent.right = null;
228            }
229            // 删除节点之后的处理
230            afterRemove(node);
231        }
232        size--;
233        return oldValue;
234    }
235     
236    private void resize() {
237        // 装填因子 <= 0.75
238        if (size / table.length <= DEFAULT_LOAD_FACTOR) {
239            return;
240        }
241        Node<K, V> [] oldTable = table;
242        table = new Node[oldTable.length << 1];
243        Queue<Node<K, V>> queue = new LinkedList<Node<K,V>>();
244        for(int i = 0; i < oldTable.length; i++) {
245            if (oldTable[i] == null) {
246                continue;
247            }
248            queue.offer(oldTable[i]);
249            while(!queue.isEmpty()) {
250                Node<K, V> node = queue.poll();
251                if (node.left != null) {
252                    queue.offer(node.left);
253                }
254                if (node.right != null) {
255                    queue.offer(node.right);
256                }
257                // 挪动代码得放到最后面
258                moveNode(node);
259            }
260        }
261    }
262     
263    private void moveNode(Node<K, V> newNode) {
264        // 重置
265        newNode.parent = null;
266        newNode.left = null;
267        newNode.right = null;
268        newNode.color = RED;
269         
270        int index = index(newNode);
271        // 取出index位置的红黑树根节点
272        Node<K, V> root = table[index];
273        if (root == null) {
274            root = newNode;
275            table[index] = root;
276            afterPut(root);
277            return;
278        }
279         
280        // 添加新的节点到红黑树上面
281        Node<K, V> parent = root;
282        Node<K, V> node = root;
283        int cmp = 0;
284        K k1 = newNode.key;
285        int h1 = newNode.hash;
286        do {
287            parent = node;
288            K k2 = node.key;
289            int h2 = node.hash;
290            if (h1 > h2) {
291                cmp = 1;
292            } else if (h1 < h2) {
293                cmp = -1;
294            } else if (k1 != null && k2 != null
295                    && k1 instanceof Comparable
296                    && k1.getClass() == k2.getClass()
297                    && (cmp = ((Comparable<K>)k1).compareTo(k2)) != 0) {
298            } else {
299                cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
300            }
301             
302            if (cmp > 0) {
303                node = node.right;
304            } else if (cmp < 0) {
305                node = node.left;
306            }
307        } while (node != null);
308 
309        // 看看插入到父节点的哪个位置
310        newNode.parent = parent;
311        if (cmp > 0) {
312            parent.right = newNode;
313        } else {
314            parent.left = newNode;
315        }
316         
317        // 新添加节点之后的处理
318        afterPut(newNode);
319    }
320 
321    /**
322     * 得到节点的后继节点
323     *
324     * @param node
325     * @return
326     */
327    private Node<K, V> successor(Node<K, V> node) {
328        if (node == null)
329            return null;
330 
331        // 前驱节点在左子树当中（right.left.left.left....）
332        Node<K, V> p = node.right;
333        if (p != null) {
334            while (p.left != null) {
335                p = p.left;
336            }
337            return p;
338        }
339 
340        // 从父节点、祖父节点中寻找前驱节点
341        while (node.parent != null && node == node.parent.right) {
342            node = node.parent;
343        }
344        return node.parent;
345    }
346 
347    private Node<K, V> node(K key) {
348        Node<K, V> root = table[index(key)];
349        return root == null ? null : node(root, key);
350    }
351 
352    private Node<K, V> node(Node<K, V> node, K k1) {
353        int h1 = k1 == null ? 0 : k1.hashCode();
354        // 存储查找结果
355        Node<K, V> result = null;
356        int cmp = 0;
357        while (node != null) {
358            K k2 = node.key;
359            int h2 = node.hash;
360            // 先比较哈希值
361            if (h1 > h2) {
362                node = node.right;
363            } else if (h1 < h2) {
364                node = node.left;
365            } else if (Objects.equals(k1, k2)) {
366                return node;
367            } else if (k1 != null && k2 != null
368                && k1.getClass() == k2.getClass()
369                && k1 instanceof Comparable
370                && (cmp = ((Comparable<K>) k1).compareTo(k2)) != 0) {
371                node = cmp > 0 ? node.right : node.left;
372            } else if (node.right != null && (result = node(node.right, k1)) != null) { 
373                return result;
374            } else { // 只能往左边找
375                node = node.left;
376            }
377        }
378        return null;
379    }
380 
381    /**
382     * 得到hash索引（在数组中的索引下标）
383     *
384     * @param key
385     * @return
386     */
387    private int index(K key) {
388        if (key == null) {
389            return 0;
390        }
391        int hash = key.hashCode();
392        hash = hash ^ (hash >>> 16);
393        return hash & (table.length - 1);
394    }
395 
396    private int index(Node<K, V> node) {
397        if (node == null) {
398            return 0;
399        }
400        int hash = node.hash;
401        hash = hash ^ (hash >>> 16);
402        return hash & (table.length - 1);
403    }
404 
405    private void afterPut(Node<K, V> node) {
406        Node<K, V> parent = node.parent;
407        // 添加的是根节点 或者 上溢到达了根节点
408        if (parent == null) {
409            black(node);
410            return;
411        }
412        // 如果父节点是黑色，直接返回
413        if (isBlack(parent)) {
414            return;
415        }
416        // 叔父节点
417        Node<K, V> uncle = parent.sibling();
418        // 祖父节点
419        Node<K, V> grand = red(parent.parent);
420        if (isRed(uncle)) { // 叔父节点是红色【B树节点上溢】
421            black(parent);
422            black(uncle);
423            // 把祖父节点当做是新添加的节点
424            afterPut(grand);
425            return;
426        }
427        // 叔父节点不是红色
428        if (parent.isLeftChild()) { // L
429            if (node.isLeftChild()) { // LL
430                black(parent);
431            } else { // LR
432                black(node);
433                rotateLeft(parent);
434            }
435            rotateRight(grand);
436        } else { // R
437            if (node.isLeftChild()) { // RL
438                black(node);
439                rotateRight(parent);
440            } else { // RR
441                black(parent);
442            }
443            rotateLeft(grand);
444        }
445    }
446 
447    private void afterRemove(Node<K, V> node) {
448        // 如果删除的节点是红色
449        // 或者 用以取代删除节点的子节点是红色
450        if (isRed(node)) {
451            black(node);
452            return;
453        }
454        Node<K, V> parent = node.parent;
455        if (parent == null) {
456            return;
457        }
458        // 删除的是黑色叶子节点【下溢】
459        // 判断被删除的node是左还是右
460        boolean left = parent.left == null || node.isLeftChild();
461        Node<K, V> sibling = left ? parent.right : parent.left;
462        if (left) { // 被删除的节点在左边，兄弟节点在右边
463            if (isRed(sibling)) { // 兄弟节点是红色
464                black(sibling);
465                red(parent);
466                rotateLeft(parent);
467                // 更换兄弟
468                sibling = parent.right;
469            }
470 
471            // 兄弟节点必然是黑色
472            if (isBlack(sibling.left) && isBlack(sibling.right)) {
473                // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
474                boolean parentBlack = isBlack(parent);
475                black(parent);
476                red(sibling);
477                if (parentBlack) {
478                    afterRemove(parent);
479                }
480            } else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
481                // 兄弟节点的左边是黑色，兄弟要先旋转
482                if (isBlack(sibling.right)) {
483                    rotateRight(sibling);
484                    sibling = parent.right;
485                }
486 
487                color(sibling, colorOf(parent));
488                black(sibling.right);
489                black(parent);
490                rotateLeft(parent);
491            }
492        } else { // 被删除的节点在右边，兄弟节点在左边
493            if (isRed(sibling)) { // 兄弟节点是红色
494                black(sibling);
495                red(parent);
496                rotateRight(parent);
497                // 更换兄弟
498                sibling = parent.left;
499            }
500 
501            // 兄弟节点必然是黑色
502            if (isBlack(sibling.left) && isBlack(sibling.right)) {
503                // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
504                boolean parentBlack = isBlack(parent);
505                black(parent);
506                red(sibling);
507                if (parentBlack) {
508                    afterRemove(parent);
509                }
510            } else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
511                // 兄弟节点的左边是黑色，兄弟要先旋转
512                if (isBlack(sibling.left)) {
513                    rotateLeft(sibling);
514                    sibling = parent.left;
515                }
516 
517                color(sibling, colorOf(parent));
518                black(sibling.left);
519                black(parent);
520                rotateRight(parent);
521            }
522        }
523    }
524 
525    /**
526     * 给指定节点染指定的颜色
527     *
528     * @param node  节点
529     * @param color 颜色
530     * @return 节点
531     */
532    private Node<K, V> color(Node<K, V> node, boolean color) {
533        if (node != null) {
534            node.color = color;
535        }
536        return node;
537    }
538 
539    /**
540     * 节点染成红色
541     *
542     * @param node
543     * @return
544     */
545    private Node<K, V> red(Node<K, V> node) {
546        return color(node, RED);
547    }
548 
549    /**
550     * 节点染成黑色
551     *
552     * @param node
553     * @return
554     */
555    private Node<K, V> black(Node<K, V> node) {
556        return color(node, BLACK);
557    }
558 
559    /**
560     * 得到节点的颜色
561     *
562     * @param node
563     * @return
564     */
565    private boolean colorOf(Node<K, V> node) {
566        return node == null ? BLACK : node.color;
567    }
568 
569    /**
570     * 是否是黑色
571     *
572     * @param node
573     * @return
574     */
575    private boolean isBlack(Node<K, V> node) {
576        return colorOf(node) == BLACK;
577    }
578 
579    /**
580     * 是否是红色
581     *
582     * @param node
583     * @return
584     */
585    private boolean isRed(Node<K, V> node) {
586        return colorOf(node) == RED;
587    }
588 
589    private void rotateLeft(Node<K, V> grand) {
590        Node<K, V> parent = grand.right;
591        Node<K, V> child = parent.left;
592        grand.right = child;
593        parent.left = grand;
594        afterRotate(grand, parent, child);
595    }
596 
597    private void rotateRight(Node<K, V> grand) {
598        Node<K, V> parent = grand.left;
599        Node<K, V> child = parent.right;
600        grand.left = child;
601        parent.right = grand;
602        afterRotate(grand, parent, child);
603    }
604 
605    private void afterRotate(Node<K, V> grand, Node<K, V> parent, Node<K, V> child) {
606        // 让parent称为子树的根节点
607        parent.parent = grand.parent;
608        if (grand.isLeftChild()) {
609            grand.parent.left = parent;
610        } else if (grand.isRightChild()) {
611            grand.parent.right = parent;
612        } else { // grand是root节点
613            table[index(grand.key)] = parent;
614        }
615 
616        // 更新child的parent
617        if (child != null) {
618            child.parent = grand;
619        }
620 
621        // 更新grand的parent
622        grand.parent = parent;
623    }
624 
625    /**
626     * ***************************************************
627     *
628     * @ClassName Node<K , V>
629     * @Description 红黑树节点
630     * @Author maojianyun
631     * @Date 2020/1/9 22:06
632     * @Version V1.0 ****************************************************
633     **/
634    private static class Node<K, V> {
635        // 默认为红色
636        boolean color = RED;
637        int hash;
638        K key;
639        V value;
640        Node<K, V> left;
641        Node<K, V> right;
642        Node<K, V> parent;
643 
644        public Node(K key, V value, Node<K, V> parent) {
645            this.key = key;
646            this.hash = key == null ? 0 : key.hashCode();
647            this.value = value;
648            this.parent = parent;
649        }
650 
651        /**
652         * 是否是叶子节点
653         *
654         * @return
655         */
656        public boolean isLeaf() {
657            return left == null && right == null;
658        }
659 
660        /**
661         * 是否有两个孩子
662         *
663         * @return
664         */
665        public boolean hasTwoChildren() {
666            return left != null && right != null;
667        }
668 
669        /**
670         * 是否是左孩子
671         *
672         * @return
673         */
674        public boolean isLeftChild() {
675            return parent != null && this == parent.left;
676        }
677 
678        /**
679         * 是否是右孩子
680         *
681         * @return
682         */
683        public boolean isRightChild() {
684            return parent != null && this == parent.right;
685        }
686 
687        /**
688         * 得到兄弟节点
689         *
690         * @return
691         */
692        public Node<K, V> sibling() {
693            if (isLeftChild()) {
694                return parent.right;
695            }
696            if (isRightChild()) {
697                return parent.left;
698            }
699            return null;
700        }
701 
702        @Override
703        public String toString() {
704            return color + "_Node_" + key + "_" + value;
705        }
706    }
707 
708    public void print() {
709        if (size == 0)
710            return;
711        for (int i = 0; i < table.length; i++) {
712            final Node<K, V> root = table[i];
713            System.out.println("【index = " + i + "】");
714            BinaryTrees.println(new BinaryTreeInfo() {
715                @Override
716                public Object string(Object node) {
717                    return node;
718                }
719 
720                @Override
721                public Object root() {
722                    return root;
723                }
724 
725                @Override
726                public Object right(Object node) {
727                    return ((Node<K, V>) node).right;
728                }
729 
730                @Override
731                public Object left(Object node) {
732                    return ((Node<K, V>) node).left;
733                }
734            });
735            System.out.println("---------------------------------------------------");
736        }
737    }
738}