本文共 6685 字，大约阅读时间需要 22 分钟。
实现HashMap
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实现
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; public HashMap_v0() { table = new Node [DEFAULT_CAPACITY]; } // ... 其余代码如下 ...}
节点类
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; } // ... 节点方法 ...}
HashMap实现细节
数组初始化
HashMap使用一个数组存储节点，数组的长度默认为1<<4（16个单元）。 节点颜色控制
节点颜色分为红色（false）和黑色（true），用于维护红黑树的平衡。 哈希计算
根据键的哈希值计算节点的位置。 红黑树修复
在进行插入、删除操作后，可能需要调整红黑树的颜色和结构以保持平衡。 插入操作
将新节点插入到红黑树中，并根据需要调整父节点的颜色和结构。 查找操作
通过哈希值快速定位节点，沿红黑树查找关键字。 删除操作
删除节点后，调整红黑树结构，确保树的平衡。 遍历操作
使用队列实现深度优先遍历。 测试用例
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; }} 测试函数
public class Main { static void test1Map(Map map, String[] words) { for (String word : words) { Integer count = map.get(word); map.put(word, count == null ? 0 : count + 1); } 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); map.put(new Object(), 2); map.put("jack", 3); map.put(10, 4); map.put(new Object(), 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(); } }} 红黑树优化
哈希冲突处理
采用双哈希函数，减少冲突概率。 红黑树维护
保持树的平衡，避免树的高度过高。 旋转操作
在树的插入、删除操作中，通过旋转调整树的高度。 颜色调整
保持树的红黑平衡，确保树的高度最优。 后继查找
通过红黑树的后继查找，快速定位节点的后继。 ##性能测试
哈希表性能
HashMap通过哈希表实现快速查找和插入，平均时间复杂度为O(1)。 红黑树性能
红黑树用于维护树的平衡，确保在最坏情况下也能快速查找。 内存管理
HashMap通过数组存储节点，节省内存，适合处理大量数据。 扩展性
HashMap支持动态调整数组大小，适应不同规模的数据量。 总结
HashMap通过哈希表和红黑树的结合，实现了高效的数据存储和查找操作。其灵活性和性能使其成为Java中常用的数据结构。
转载地址：http://htur.baihongyu.com/