本文共 17018 字，大约阅读时间需要 56 分钟。

• 写在前面：记录学习《恋上数据结构与算法》的过程。
• 课程链接地址：

目录

实现HashMap

• 数组+红黑树

• Map.java

package com.mj.map;public interface Map
   
     {	int size();	boolean isEmpty();	void clear();	V put(K key, V value);	V get(K key);	V remove(K key);	boolean containsKey(K key);	boolean containsValue(V value);	void traversal(Visitor
    
      visitor);		public static abstract class Visitor
     
       {		boolean stop;		public abstract boolean visit(K key, V value);	}}
     
    
   

HashMap.java

• 定义数组

public class HashMap_v0
   
     implements Map
    
      {	private static final boolean RED = false;	private static final boolean BLACK = true;	private int size;	private Node
     
      [] table;	private static final int DEFAULT_CAPACITY = 1 << 4;
     
    
   

• 定义节点

private static class Node
   
     {		int hash;		K key;		V value;		boolean color = RED;		Node
    
      left;		Node
     
       right;		Node
      
        parent;		public Node(K key, V value, Node
       
         parent) {			this.key = key;			this.hash = key == null ? 0 : key.hashCode();			this.value = value;			this.parent = parent;		}				public boolean hasTwoChildren() {			return left != null && right != null;		}				public boolean isLeftChild() {			return parent != null && this == parent.left;		}				public boolean isRightChild() {			return parent != null && this == parent.right;		}				public Node
        
          sibling() { if (isLeftChild()) { return parent.right; } if (isRightChild()) { return parent.left; } return null; }
        
       
      
     
    
   

• 设置数组默认长度

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

• 获取长度及清空操作

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

• 根据key生成对应的索引（在桶数组中的位置）

private int index(K key) {		if (key == null) return 0;		int hash = key.hashCode();		return (hash ^ (hash >>> 16)) & (table.length - 1);	}		private int index(Node
   
     node) {		return (node.hash ^ (node.hash >>> 16)) & (table.length - 1);	}
   

• 红黑树修复

private void afterRemove(Node
   
     node) {		// 如果删除的节点是红色		// 或者 用以取代删除节点的子节点是红色		if (isRed(node)) {			black(node);			return;		}				Node
    
      parent = node.parent;		if (parent == null) return;				// 删除的是黑色叶子节点【下溢】		// 判断被删除的node是左还是右		boolean left = parent.left == null || node.isLeftChild();		Node
     
       sibling = left ? parent.right : parent.left;		if (left) { // 被删除的节点在左边，兄弟节点在右边			if (isRed(sibling)) { // 兄弟节点是红色				black(sibling);				red(parent);				rotateLeft(parent);				// 更换兄弟				sibling = parent.right;			}						// 兄弟节点必然是黑色			if (isBlack(sibling.left) && isBlack(sibling.right)) {				// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并				boolean parentBlack = isBlack(parent);				black(parent);				red(sibling);				if (parentBlack) {					afterRemove(parent);				}			} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素				// 兄弟节点的左边是黑色，兄弟要先旋转				if (isBlack(sibling.right)) {					rotateRight(sibling);					sibling = parent.right;				}								color(sibling, colorOf(parent));				black(sibling.right);				black(parent);				rotateLeft(parent);			}		} else { // 被删除的节点在右边，兄弟节点在左边			if (isRed(sibling)) { // 兄弟节点是红色				black(sibling);				red(parent);				rotateRight(parent);				// 更换兄弟				sibling = parent.left;			}						// 兄弟节点必然是黑色			if (isBlack(sibling.left) && isBlack(sibling.right)) {				// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并				boolean parentBlack = isBlack(parent);				black(parent);				red(sibling);				if (parentBlack) {					afterRemove(parent);				}			} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素				// 兄弟节点的左边是黑色，兄弟要先旋转				if (isBlack(sibling.left)) {					rotateLeft(sibling);					sibling = parent.left;				}								color(sibling, colorOf(parent));				black(sibling.left);				black(parent);				rotateRight(parent);			}		}	}	private void afterPut(Node
      
        node) {		Node
       
         parent = node.parent;				// 添加的是根节点 或者 上溢到达了根节点		if (parent == null) {			black(node);			return;		}				// 如果父节点是黑色，直接返回		if (isBlack(parent)) return;				// 叔父节点		Node
        
          uncle = parent.sibling(); // 祖父节点 Node
         
           grand = red(parent.parent); if (isRed(uncle)) { // 叔父节点是红色【B树节点上溢】 black(parent); black(uncle); // 把祖父节点当做是新添加的节点 afterPut(grand); return; } // 叔父节点不是红色 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); } } private void rotateLeft(Node
          
            grand) { Node
           
             parent = grand.right; Node
            
              child = parent.left; grand.right = child; parent.left = grand; afterRotate(grand, parent, child); } private void rotateRight(Node
             
               grand) { Node
              
                parent = grand.left; Node
               
                 child = parent.right; grand.left = child; parent.right = grand; afterRotate(grand, parent, child); } private void afterRotate(Node
                
                  grand, Node
                 
                   parent, Node
                  
                    child) { // 让parent称为子树的根节点 parent.parent = grand.parent; if (grand.isLeftChild()) { grand.parent.left = parent; } else if (grand.isRightChild()) { grand.parent.right = parent; } else { // grand是root节点 table[index(grand)] = parent; } // 更新child的parent if (child != null) { child.parent = grand; } // 更新grand的parent grand.parent = parent; } private Node
                   
                     color(Node
                    
                      node, boolean color) { if (node == null) return node; node.color = color; return node; } private Node
                     
                       red(Node
                      
                        node) { return color(node, RED); } private Node
                       
                         black(Node
                        
                          node) { return color(node, BLACK); } private boolean colorOf(Node
                         
                           node) { return node == null ? BLACK : node.color; } private boolean isBlack(Node
                          
                            node) { return colorOf(node) == BLACK; } private boolean isRed(Node
                           
                             node) { return colorOf(node) == RED; }
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

•  put 添加元素

public V put(K key, V value) {		int index = index(key);		// 取出index位置的红黑树根节点		Node
   
     root = table[index];		if (root == null) {			root = new Node<>(key, value, null);			table[index] = root;			size++;			afterPut(root);			return null;		}				// 添加新的节点到红黑树上面		Node
    
      parent = root;		Node
     
       node = root;		int cmp = 0;		K k1 = key;		int h1 = k1 == null ? 0 : k1.hashCode();		Node
      
        result = null;		boolean searched = false; // 是否已经搜索过这个key		do {			parent = node;			K k2 = node.key;			int h2 = node.hash;			if (h1 > h2) {				cmp = 1;			} else if (h1 < h2) {				cmp = -1;			} else if (Objects.equals(k1, k2)) {				cmp = 0;			} else if (k1 != null && k2 != null 					&& k1.getClass() == k2.getClass()					&& k1 instanceof Comparable					&& (cmp = ((Comparable) k1).compareTo(k2)) != 0) {			} else if (searched) { // 已经扫描了				cmp = System.identityHashCode(k1) - System.identityHashCode(k2);			} else { // searched == false; 还没有扫描，然后再根据内存地址大小决定左右				if ((node.left != null && (result = node(node.left, k1)) != null)						|| (node.right != null && (result = node(node.right, k1)) != null)) {					// 已经存在这个key					node = result;					cmp = 0;				} else { // 不存在这个key					searched = true;					cmp = System.identityHashCode(k1) - System.identityHashCode(k2);				}			}						if (cmp > 0) {				node = node.right;			} else if (cmp < 0) {				node = node.left;			} else { // 相等				V oldValue = node.value;				node.key = key;				node.value = value;				node.hash = h1;				return oldValue;			}		} while (node != null);		// 看看插入到父节点的哪个位置		Node
       
         newNode = new Node<>(key, value, parent);		if (cmp > 0) {			parent.right = newNode;		} else {			parent.left = newNode;		}		size++;				// 新添加节点之后的处理		afterPut(newNode);		return null;	}
       
      
     
    
   

• compare 比较（存在问题，用node解决）

/**	 * 比较key大小	 * @param k1	 * @param k2	 * @param h1 k1的hashCode	 * @param h2 k2的hashCode	 * @return	 */	private int compare(K k1, K k2, int h1, int h2) {		// 比较哈希值		int result = h1 - h2;		if (result != 0) return result;				// 比较equals		if (Objects.equals(k1, k2)) return 0;				// 哈希值相等，但是不equals		if (k1 != null && k2 != null 				&& k1.getClass() == k2.getClass()				&& k1 instanceof Comparable) {			// 同一种类型并且具备可比较性			if (k1 instanceof Comparable) {				return ((Comparable) k1).compareTo(k2);			}		}				// 同一种类型，哈希值相等，但是不equals，但是不具备可比较性		// k1不为null，k2为null		// k1为null，k2不为null		return System.identityHashCode(k1) - System.identityHashCode(k2);	}

• 通过key找到节点（get () \ containsKey()）

public V get(K key) {		Node
   
     node = node(key);		return node != null ? node.value : null;	}    public boolean containsKey(K key) {		return node(key) != null;	}    private Node
    
      node(K key) {		Node
     
       root = table[index(key)];		return root == null ? null : node(root, key);	}	    private Node
      
        node(Node
       
         node, K k1) {		int h1 = k1 == null ? 0 : k1.hashCode();		// 存储查找结果		Node
        
          result = null; int cmp = 0; 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)) { return node; } else if (k1 != null && k2 != null && k1.getClass() == k2.getClass() && k1 instanceof Comparable && (cmp = ((Comparable) k1).compareTo(k2)) != 0) { node = cmp > 0 ? node.right : node.left; } else if (node.right != null && (result = node(node.right, k1)) != null) { return result; } else { // 只能往左边找 node = node.left; }// } else if (node.left != null && (result = node(node.left, k1)) != null) { // return result;// } else {// return null;// } } return null; }
        
       
      
     
    
   

• 删除 remove

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

• 后继

private Node
   
     successor(Node
    
      node) {		if (node == null) return null;				// 前驱节点在左子树当中（right.left.left.left....）		Node
     
       p = node.right;		if (p != null) {			while (p.left != null) {				p = p.left;			}			return p;		}				// 从父节点、祖父节点中寻找前驱节点		while (node.parent != null && node == node.parent.right) {			node = node.parent;		}		return node.parent;	}
     
    
   

• 查看是否存在某一指定值

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

• 遍历

public void traversal(Visitor
   
     visitor) {		if (size == 0 || visitor == null) return;				Queue
    
     
      > queue = new LinkedList<>();		for (int i = 0; i < table.length; i++) {			if (table[i] == null) continue;						queue.offer(table[i]);			while (!queue.isEmpty()) {				Node
      
        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);				}			}		}	}
      
     
    
   

• 注意compare与equals

• 测试用例

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

public class SubKey1 extends Key {	public SubKey1(int value) {		super(value);	}	@Override	public boolean equals(Object obj) {		if (obj == this) return true;		if (obj == null || 				(obj.getClass() != SubKey1.class 				&& obj.getClass() != SubKey2.class)) return false;		return ((Key) obj).value == value;	}}

public class SubKey2 extends Key {	public SubKey2(int value) {		super(value);	}		@Override	public boolean equals(Object obj) {		if (obj == this) return true;		if (obj == null || 				(obj.getClass() != SubKey1.class 				&& obj.getClass() != SubKey2.class)) return false;		return ((Key) obj).value == value;	}}

• 测试函数

package com.mj;import java.util.List;import com.mj.Times.Task;import com.mj.file.FileInfo;import com.mj.file.Files;import com.mj.map.HashMap;import com.mj.map.LinkedHashMap;import com.mj.map.Map;import com.mj.map.Map.Visitor;import com.mj.map.TreeMap;import com.mj.model.Key;import com.mj.model.SubKey1;import com.mj.model.SubKey2;public class Main {		static void test1Map(Map
   
     map, String[] words) {		Times.test(map.getClass().getName(), new Task() {			@Override			public void execute() {				for (String word : words) {					Integer count = map.get(word);					count = count == null ? 0 : count;					map.put(word, count + 1);				}				System.out.println(map.size()); // 17188								int count = 0;				for (String word : words) {					Integer i = map.get(word);					count += i == null ? 0 : i;					map.remove(word);				}				Asserts.test(count == words.length);				Asserts.test(map.size() == 0);			}		});	}		static void test1() {		String filepath = "C:\\Users\\MJ Lee\\Desktop\\src\\java\\util\\concurrent";		FileInfo fileInfo = Files.read(filepath, null);		String[] words = fileInfo.words();		System.out.println("总行数：" + fileInfo.getLines());		System.out.println("单词总数：" + words.length);		System.out.println("-------------------------------------");		test1Map(new TreeMap<>(), words);		test1Map(new HashMap<>(), words);		test1Map(new LinkedHashMap<>(), words);	}		static void test2(HashMap
    
      map) {		for (int i = 1; i <= 20; i++) {			map.put(new Key(i), i);		}		for (int i = 5; i <= 7; i++) {			map.put(new Key(i), i + 5);		}		Asserts.test(map.size() == 20);		Asserts.test(map.get(new Key(4)) == 4);		Asserts.test(map.get(new Key(5)) == 10);		Asserts.test(map.get(new Key(6)) == 11);		Asserts.test(map.get(new Key(7)) == 12);		Asserts.test(map.get(new Key(8)) == 8);	}		static void test3(HashMap
     
       map) {		map.put(null, 1); // 1		map.put(new Object(), 2); // 2		map.put("jack", 3); // 3		map.put(10, 4); // 4		map.put(new Object(), 5); // 5		map.put("jack", 6);		map.put(10, 7);		map.put(null, 8);		map.put(10, null);		Asserts.test(map.size() == 5);		Asserts.test(map.get(null) == 8);		Asserts.test(map.get("jack") == 6);		Asserts.test(map.get(10) == null);		Asserts.test(map.get(new Object()) == null);		Asserts.test(map.containsKey(10));		Asserts.test(map.containsKey(null));		Asserts.test(map.containsValue(null));		Asserts.test(map.containsValue(1) == false);	}		static void test4(HashMap
      
        map) {		map.put("jack", 1);		map.put("rose", 2);		map.put("jim", 3);		map.put("jake", 4);				map.remove("jack");		map.remove("jim");		for (int i = 1; i <= 10; i++) {			map.put("test" + i, i);			map.put(new Key(i), i);		}		for (int i = 5; i <= 7; i++) {			Asserts.test(map.remove(new Key(i)) == i);		}		for (int i = 1; i <= 3; i++) {			map.put(new Key(i), i + 5);		}		Asserts.test(map.size() == 19);		Asserts.test(map.get(new Key(1)) == 6);		Asserts.test(map.get(new Key(2)) == 7);		Asserts.test(map.get(new Key(3)) == 8);		Asserts.test(map.get(new Key(4)) == 4);		Asserts.test(map.get(new Key(5)) == null);		Asserts.test(map.get(new Key(6)) == null);		Asserts.test(map.get(new Key(7)) == null);		Asserts.test(map.get(new Key(8)) == 8);		map.traversal(new Visitor
       
        () {			public boolean visit(Object key, Integer value) {				System.out.println(key + "_" + value);				return false;			}		});	}		static void test5(HashMap
        
          map) { for (int i = 1; i <= 20; i++) { map.put(new SubKey1(i), i); } map.put(new SubKey2(1), 5); Asserts.test(map.get(new SubKey1(1)) == 5); Asserts.test(map.get(new SubKey2(1)) == 5); Asserts.test(map.size() == 20); } public static void main(String[] args) { test1(); test2(new HashMap<>()); test3(new HashMap<>()); test4(new HashMap<>()); test5(new HashMap<>()); }}
        
       
      
     
    
   

• Asserts .java

package com.mj;public class Asserts {	public static void test(boolean value) {		try {			if (!value) throw new Exception("测试未通过");		} catch (Exception e) {			e.printStackTrace();		}	}}

• index优化

​​​​​​​

转载地址：http://htur.baihongyu.com/