上一章手写 LinkedList 核心源码, 本章我们来手写 Java HashMap 的核心源码.
我们来先了解一下 HashMap 的原理. HashMap 字面意思 hash + map,map 是映射的意思, HashMap 就是用 hash 进行映射的意思. 不明白? 没关系. 我们来具体讲解一下 HashMap 的原理.
HashMap 使用分析
- //1 存
- HashMap<String,String> map = new HashMap<>();
- map.put("name","tom");
- //2 取
- System.out.println(map.get("name"));// 输出 tom
使用就是这么简单.
HashMap 原理分析
我们知道, Object 类有一个 hashCode() 方法, 返回对象的 hashCode 值, 可以理解为返回了对象的内存地址, 暂且不管返回的是内存地址或者其它什么也好, 先不管, 至于 hashCode() 方法回返的数是怎么算的? 我们也不管
第 1 我们只需要记住: 这个函数返回的是一个数就行了.
第 2 HashMap 内部是用了一个数组来存放数据
1 HashMap 是如何把 name,tom 存放的?
下面我们用一张图来演示
从上图可以看出:
注: 上图中数组的大小是 7, 是多少都行, 只是我们这里就画了 7 个元素, 我们就以数组大小为 7 来说明 HashMap 的原理.
数组的大小是 7, 那么数组的索引范围是 [0 , 6]
取得 key 也就是 "name" 的 hashCode, 这是一个数, 不管这个数是多少, 对 7 进行取余数, 那么范围肯定是 [0 , 6], 正好和数组的索引是一样的.
"name".hashCode() % 7 的值假如为 2 , 那么 value 也就是 "tom" 应该存放的位置就是 2
data[2] = "tom" , 存到数组中. 是不是很巧妙.
2 下面再来看看如何取?
也用一张图来演示底层原理, 如下
由上图可知:
首先也是获取 key 也就是 "name" 的 hashCode 值
用 hashCode 值对数组的大小 7 进行取余数, 和存的时候运行一样, 肯定也是 2
从数组的第 2 个位置把 value 取出, 即: String value = data[2]
注: 有几点需要注意
某个对象的 hashCode() 方法返回的值, 在任何时候调用, 返回的值都是一样的
对一个数 n 取余数 , 范围是 [ 0, n - 1 ]
注: 有几个问题需要解决
存的时候, 如果不同的 key 的 hashCode 对数组取余数, 都正好相同了, 也就是都映射在了数组的同一位置, 怎么办? 这就是 hash 冲突问题
比如 9 % 7 == 2 , 16 % 7 == 2 都等于 2
答: 数组中存放的是一个节点的数据结构, 节点有 next 属性, 如果 hash 冲突了, 单链表进行存放, 取的时候也是一样, 遍历链表
如果数组已经存满了怎么办?
答: 和 ArrayList 一样, 进行扩容, 重新映射
直接使用 hashCode() 值进行映射, 产生 hash 冲突的概论很大, 怎么办?
答: 参考 JDK 中 HashMap 中的实现, 有一个 hash() 函数, 再对 hashCode() 的值进行运行一下, 再进行映射
由上可知: HashMap 是用一个数组来存放数据, 如果遇到映射的位置上面已经有值了, 那么就用链表存放在当前的前面. 数组 + 链表结构, 是 HashMap 的底层结构
假如我们的数组里面存放的元素是 QEntry, 如下图:
手写 HashMap 核心源码
上面分析了原理, 接下来我们用最少的代码来提示 HashMap 的原理.
我们就叫 QHashMap 类, 同时数组里面的元素需要也需要定义一个类, 我们定义在 QHashMap 类的内部. 就叫 QEntry
QEntry 的定义如下:
// 底层数组中存放的元素类 public static class QEntry<K, V> { K key; // 存放 key V value; // 存放 value int hash; //key 对应的 hash 值 //hash 冲突时, 也就是映射的位置上已经有一个元素了 // 那么新加的元素作为链表头, 已经存放的放在后面 // 即保存在 next 中, 一句话: 添加新元素时, 添加在表头 QEntry<K, V> next; public QEntry(K key, V value, int hash, QEntry<K, V> next) { this.key = key; this.value = value; this.hash = hash; this.next = next; } }
QEntry 类的定义有了, 下面看下 QHashMap 类中需要哪些属性?
QHashMap 类的定义如下图:
public class QHashMap<K, V> { // 默认的数组的大小 private static final int DEFAULT_INITIAL_CAPACITY = 16; // 默认的扩容因子, 当数据中元素的个数越多时, hash 冲突也容易发生 // 所以, 需要在数组还没有用完的情况下就开始扩容 // 这个 0.75 就是元素的个数达到了数组大小的 75% 的时候就开始扩容 // 比如数组的大小是 100, 当里面的元素增加到 75 的时候, 就开始扩容 private static final float DEFAULT_LOAD_FACTOR = 0.75f; // 存放元素的数组 private QEntry[] table; // 数组中元素的个数 private int size; ...... }
只需要两个常量和两个变量就够了.
下面我们看下 QHashMap 的构造函数, 为了简单, 只实现一个默认的构造函数
public QHashMap() { // 创建一个数组, 默认大小为 16 table = new QEntry[DEFAULT_INITIAL_CAPACITY]; // 此时元素个数是 0 size = 0; }
我们来看下 QHashMap 是如何存放数据的 map.put("name","tom")
put() 函数的实现如下:
/** * 1 参数 key,value 很容易理解 * 2 返回 V, 我们知道, HashMap 有一个特点, * 如果调用了多次 map.put("name","tom"); map.put("name","lilei"); * 后面的值会把前面的覆盖, 如果出现这种情况, 返回旧值, 在这里返回 "tom" */ public V put(K key, V value) { //1 为了简单, key 不支持 null if (key == null) { throw new RuntimeException("key is null"); } // 不直接用 key.hashCode(), 我们对 key.hashCode() 再作一次运算作为 hash 值 // 这个 hash() 的方法我是直接从 HashMap 源码拷贝过来的. 可以不用关心 hash() 算法本身 // 只需要知道 hash() 输入一个数, 返回一个数就行了. int hash = hash(key.hashCode()); // 用 key 的 hash 值和数组的大小, 作一次映射, 得到应该存放的位置 int index = indexFor(hash, table.length); // 看看数组中, 有没有已存在的元素的 key 和参数中的 key 是相等的 // 相等则把老的值替换成新的, 然后返回旧值 QEntry<K, V> e = table[index]; while (e != null) { // 先比较 hash 是否相等, 再比较对象是否相等, 或者比较 equals 方法 // 如果相等了, 说明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值 if (e.hash == hash && (key == e.key || key.equals(e.key))) { V oldValue = e.value; e.value = value; return oldValue; } e = e.next; } // 如果数组中没有元素的 key 与传的 key 相等的话 // 把当前位置的元素保存下来 QEntry<K, V> next = table[index]; //next 有可能为 null, 也有可能不为 null, 不管是否为 null //next 都要作为新元素的下一个节点 (next 传给了 QEntry 的构造函数) // 然后新的元素保存在了 index 这个位置 table[index] = new QEntry<>(key, value, hash, next); // 如果需要扩容, 元素的个数大于 table.length * 0.75 (别问为什么是 0.75, 经验) if (size++>= (table.length * DEFAULT_LOAD_FACTOR)) { resize(); } return null; }
注释很详细, 这里有几个函数
hash() 函数是直接从 HashMap 源码中拷贝的, 不用纠结这个算法.
indexFor(), 传入 hash 和数组的大小, 从而知道我们应该去哪个位置查找或保存
这两个函数的源码如下:
// 对 hashCode 进行运算, JDK 中 HashMap 的实现, 直接拷贝过来了 static int hash(int h) { h ^= (h>>> 20) ^ (h>>> 12); return h ^ (h>>> 7) ^ (h>>> 4); } // 根据 h 求 key 落在数组的哪个位置 static int indexFor(int h, int length) { // 或者 return h & (length-1) 性能更好 // 这里我们用最容易理解的方式, 对 length 取余数, 范围就是 [0,length - 1] // 正好是 table 数组的所有的索引的范围 h = h> 0 ? h : -h; // 防止负数 return h % length; }
还有一个扩容函数. 当元素的个数大于 table.length * 0.75 时, 我们就开始扩容
resize() 的源码如下 :
// 扩容, 元素的个数大于 table.length * 0.75 // 数组扩容到原来大小的 2 倍 private void resize() { // 新建一个数组, 大小为原来数组大小的 2 倍 int newCapacity = table.length * 2; QEntry[] newTable = new QEntry[newCapacity]; QEntry[] src = table; // 遍历旧数组, 重新映射到新的数组中 for (int j = 0; j <src.length; j++) { // 获取旧数组元素 QEntry<K, V> e = src[j]; // 释放旧数组 src[j] = null; // 因为 e 是一个链表, 有可能有多个节点, 循环遍历进行映射 while (e != null) { // 把 e 的下一个节点保存下来 QEntry<K, V> next = e.next; //e 这个当前节点进行在新的数组中映射 int i = indexFor(e.hash, newCapacity); //newTable[i] 位置上有可能是 null, 也有可能不为 null // 不管是否为 null, 都作为 e 这个节点的下一个节点 e.next = newTable[i]; // 把 e 保存在新数组的 i 的位置 newTable[i] = e; // 继续 e 的下一个节点的同样的处理 e = next; } } // 所有的节点都映射到了新数组上, 别忘了把新数组的赋值给 table table = newTable; }
相比 put() 函数来说, get() 就简单多了.
只需要通过 hash 值找到相应的数组的位置, 再遍历链表, 找到一个元素里面的 key 与传的 key 相等就行了.
put() 方法的源码如下:
// 根据 key 获取 value public V get(K key) { // 同样为了简单, key 不支持 null if (key == null) { throw new RuntimeException("key is null"); } // 对 key 进行求 hash 值 int hash = hash(key.hashCode()); // 用 hash 值进行映射, 得到应该去数组的哪个位置上取数据 int index = indexFor(hash, table.length); // 把 index 位置的元素保存下来进行遍历 // 因为 e 是一个链表, 我们要对链表进行遍历 // 找到和 key 相等的那个 QEntry, 并返回 value QEntry<K, V> e = table[index]; while (e != null) { // 比较 hash 值是否相等 if (hash == e.hash && (key == e.key || key.equals(e.key))) { return e.value; } // 如果不相等, 继续找下一个 e = e.next; } return null; }
上面就是 QHashMap 的核心源码, 我们没有实现删除.
下面是把 QHashMap 整个类的源码发出来
QHashMap 完整源码如下:
public class QHashMap<K, V> { // 默认的数组的大小 private static final int DEFAULT_INITIAL_CAPACITY = 16; // 默认的扩容因子, 当数组的大小大于或者等于当前容量 * 0.75 的时候, 就开始扩容 private static final float DEFAULT_LOAD_FACTOR = 0.75f; // 底层用一个数组来存放数据 private QEntry[] table; // 数组大小 private int size; // 一个点节, 数组中存放的单位 public static class QEntry<K, V> { K key; V value; int hash; QEntry<K, V> next; public QEntry(K key, V value, int hash, QEntry<K, V> next) { this.key = key; this.value = value; this.hash = hash; this.next = next; } } public QHashMap() { table = new QEntry[DEFAULT_INITIAL_CAPACITY]; size = 0; } // 根据 key 获取 value public V get(K key) { // 同样为了简单, key 不支持 null if (key == null) { throw new RuntimeException("key is null"); } // 对 key 进行求 hash 值 int hash = hash(key.hashCode()); // 用 hash 值进行映射, 得到应该去数组的哪个位置上取数据 int index = indexFor(hash, table.length); // 把 index 位置的元素保存下来进行遍历 // 因为 e 是一个链表, 我们要对链表进行遍历 // 找到和 key 相等的那个 QEntry, 并返回 value QEntry<K, V> e = table[index]; while (e != null) { // 比较 hash 值是否相等 if (hash == e.hash && (key == e.key || key.equals(e.key))) { return e.value; } // 如果不相等, 继续找下一个 e = e.next; } return null; } /** * 1 参数 key,value 很容易理解 * 2 返回 V, 我们知道, HashMap 有一个特点, * 如果调用了多次 map.put("name","tom"); map.put("name","lilei"); * 后面的值会把前面的覆盖, 如果出现这种情况, 返回旧值, 在这里返回 "tom" */ public V put(K key, V value) { //1 为了简单, key 不支持 null if (key == null) { throw new RuntimeException("key is null"); } // 不直接用 key.hashCode(), 我们对 key.hashCode() 再作一次运算作为 hash 值 // 这个 hash() 的方法我是直接从 HashMap 源码拷贝过来的. 可以不用关心 hash() 算法本身 // 只需要知道 hash() 输入一个数, 返回一个数就行了. int hash = hash(key.hashCode()); // 用 key 的 hash 值和数组的大小, 作一次映射, 得到应该存放的位置 int index = indexFor(hash, table.length); // 看看数组中, 有没有已存在的元素的 key 和参数中的 key 是相等的 // 相等则把老的值替换成新的, 然后返回旧值 QEntry<K, V> e = table[index]; while (e != null) { // 先比较 hash 是否相等, 再比较对象是否相等, 或者比较 equals 方法 // 如果相等了, 说明有一样的 key, 这时要更新旧值为新的 value, 同时返回旧的值 if (e.hash == hash && (key == e.key || key.equals(e.key))) { V oldValue = e.value; e.value = value; return oldValue; } e = e.next; } // 如果数组中没有元素的 key 与传的 key 相等的话 // 把当前位置的元素保存下来 QEntry<K, V> next = table[index]; //next 有可能为 null, 也有可能不为 null, 不管是否为 null //next 都要作为新元素的下一个节点 (next 传给了 QEntry 的构造函数) // 然后新的元素保存在了 index 这个位置 table[index] = new QEntry<>(key, value, hash, next); // 如果需要扩容, 元素的个数大于 table.length * 0.75 (别问为什么是 0.75, 经验) if (size++>= (table.length * DEFAULT_LOAD_FACTOR)) { resize(); } return null; } // 扩容, 元素的个数大于 table.length * 0.75 // 数组扩容到原来大小的 2 倍 private void resize() { // 新建一个数组, 大小为原来数组大小的 2 倍 int newCapacity = table.length * 2; QEntry[] newTable = new QEntry[newCapacity]; QEntry[] src = table; // 遍历旧数组, 重新映射到新的数组中 for (int j = 0; j <src.length; j++) { // 获取旧数组元素 QEntry<K, V> e = src[j]; // 释放旧数组 src[j] = null; // 因为 e 是一个链表, 有可能有多个节点, 循环遍历进行映射 while (e != null) { // 把 e 的下一个节点保存下来 QEntry<K, V> next = e.next; //e 这个当前节点进行在新的数组中映射 int i = indexFor(e.hash, newCapacity); //newTable[i] 位置上有可能是 null, 也有可能不为 null // 不管是否为 null, 都作为 e 这个节点的下一个节点 e.next = newTable[i]; // 把 e 保存在新数组的 i 的位置 newTable[i] = e; // 继续 e 的下一个节点的同样的处理 e = next; } } // 所有的节点都映射到了新数组上, 别忘了把新数组的赋值给 table table = newTable; } // 对 hashCode 进行运算, JDK 中 HashMap 的实现, 直接拷贝过来了 static int hash(int h) { h ^= (h>>> 20) ^ (h>>> 12); return h ^ (h>>> 7) ^ (h>>> 4); } // 根据 h 求 key 落在数组的哪个位置 static int indexFor(int h, int length) { // 或者 return h & (length-1) 性能更好 // 这里我们用最容易理解的方式, 对 length 取余数, 范围就是 [0,length - 1] // 正好是 table 数组的所有的索引的范围 h = h> 0 ? h : -h; // 防止负数 return h % length; } }
上面就是 QHashMap 的原理. 下面我们写一段测试代码来看下我们的 QHashMap 能不能正常运行. 测试代码如下:
public static void main(String[] args) { QHashMap<String, String> map = new QHashMap<>(); map.put("name", "tom"); map.put("age", "23"); map.put("address", "beijing"); String oldValue = map.put("address", "shanghai"); //key 一样, 返回旧值, 保存新值 System.out.println(map.get("name")); System.out.println(map.get("age")); System.out.println("旧值 =" + oldValue); System.out.println("新值 =" + map.get("address")); }
输出如下:
tom
23
旧值 = beijing
新值 = shanghai
通过上面的简单的实现了 QHashMap, 还有好多功能没有实现, 比较 remove,clear,containsKey() 等, 还有遍历相关, 有兴趣的读者可以自己实现
来源: https://www.cnblogs.com/start1225/p/10030114.html