安科网

手写Java HashMap核心源码

spb

spb

2018-11-28

关注 关注

我们来先了解一下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存放的？

下面我们用一张图来演示

手写Java HashMap核心源码

从上图可以看出：

注：上图中数组的大小是7，是多少都行，只是我们这里就画了7个元素，我们就以数组大小为7来说明HashMap的原理。

  1. 数组的大小是7，那么数组的索引范围是[0 , 6]
  2. 取得key也就是"name"的hashCode，这是一个数，不管这个数是多少，对7进行取余数，那么范围肯定是 [0 , 6]，正好和数组的索引是一样的。
  3. "name".hashCode() % 7 的值假如为2 ，那么value也就是"tom"应该存放的位置就是2
  4. data[2] = "tom" ,存到数组中。是不是很巧妙。

2 下面再来看看如何取？

也用一张图来演示底层原理，如下

手写Java HashMap核心源码

由上图可知:

  1. 首先也是获取key也就是"name"的hashCode值
  2. 用hashCode值对数组的大小 7 进行取余数，和存的时候运行一样，肯定也是2
  3. 从数组的第 2 个位置把value取出，即: String value = data[2]

注：有几点需要注意

  1. 某个对象的hashCode()方法返回的值，在任何时候调用，返回的值都是一样的
  2. 对一个数 n 取余数 ,范围是 [ 0, n - 1 ]

注：有几个问题需要解决

  1. 存的时候，如果不同的key的hashCode对数组取余数，都正好相同了，也就是都映射在了数组的同一位置，怎么办？这就是hash冲突问题
  2. 比如 9 % 7 == 2 ， 16 % 7 == 2都等于2
  3. 答：数组中存放的是一个节点的数据结构，节点有next属性，如果hash冲突了，单链表进行存放，取的时候也是一样，遍历链表
  4. 如果数组已经存满了怎么办？
  5. 答：和ArrayList一样，进行扩容，重新映射
  6. 直接使用hashCode()值进行映射，产生hash冲突的概论很大，怎么办？
  7. 答：参考JDK中HashMap中的实现，有一个hash()函数，再对hashCode()的值进行运行一下，再进行映射

由上可知：HashMap是用一个数组来存放数据，如果遇到映射的位置上面已经有值了，那么就用链表存放在当前的前面。数组+链表结构，是HashMap的底层结构

假如我们的数组里面存放的元素是QEntry，如下图：

手写Java HashMap核心源码

手写 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()等，还有遍历相关，有兴趣的读者可以自己实现

hashmap 源码 hashcode hash 数组

spb

spb

0 关注 0 粉丝 0 动态

关注 关注

相关推荐

HashMap源码解析

HashMap是面试中经常问到的一个知识点，也是判断一个候选人基础是否扎实的标准之一，因为通过HashMap可以引出很多知识点，比如数据结构、equals和hashcode方法，除此之外还可以引出线程安全的问题，HashMap是我在初学阶段学到的设计的最为

happylife 2020-05-31

数据结构 - HashMap

Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。static final int MAXIMUM_CAPACITY = 1 << 30;从源码中可以看出，hash算法实际上就键的hashCode与ha

范范 2020-03-27

HashMap源码分析

HashMap 主要用来存放键值对，它基于哈希表的Map接口实现，是常用的Java集合之一。JDK1.8 之前 HashMap 底层是数组和链表结合在一起使用也就是链表散列。所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就

mbcsdn 2020-01-07

HashMap、lru、散列表

HashMap的数据结构：HashMap实际上是一个数组和链表的数据结构。底层就是一个数组结构，数组中的每一项又是一个链表。hashCode是一个对象的标识，Java中对象的hashCode是一个int类型值。发生碰撞后会把相同hashcode的对象放到同

hanyujianke 2020-01-01

48 容器（七）——HashMap底层：哈希表结构与哈希算法

哈希表是由数组+链表组成的，首先有一个数组，数组的每一个位置都用来存储一个链表，链表的基本节点为：，当存入一个键值对时，首先调用hashcode()方法获得key的hashcode，然后通过算法计算出hash值，当不同的key取到相同的hash值时，后面的

Happyunlimited 2019-12-11

HashMap源码阅读小记

public final String toString() { return key + "=" + value; }. 重写equals，当为同一个对象或是同一个key和同一个value都认为这两个对象相等。}与无符号右移的自己异或

newtrekWang 2019-07-01

HashMap源码分析和面试准备

本篇涉及到的知识面比较广，无论你是小白还是有经验人士，都可快速理解hashmap，目的是理解知识并能通过面试，一些过于深入和细节的东西不在这里讨论。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可

dbhllnr 2020-06-09

HashMap源码分析和面试准备

本篇涉及到的知识面比较广，无论你是小白还是有经验人士，都可快速理解hashmap，目的是理解知识并能通过面试，一些过于深入和细节的东西不在这里讨论。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可

shawsun 2020-06-09

HashMap源码解析&lt;一&gt;put()方法

HashMap在进行put操作时有很多细节设计的确值得我们去学习，下面是对put方法的一些接单的介绍，如果有什么不足之处还希望大佬能给与指出；既然说到集合的底层原理，首先要介绍一下HashMap的底层数据结构：。JDK1.8以前底层的结构为数组+链表；JD

Bloddy 2020-06-08

深入理解Java编程性能调优——深入浅出HashMap的设计与优化

HashMap 作为我们日常使用最频繁的容器之一，相信你一定不陌生了。今天我们就从HashMap 的底层实现讲起，深度了解下它的设计与优化。我在 05 讲分享 List 集合类的时候，讲过 ArrayList 是基于数组的数据结构实现的，LinkedLis

ipqtjmqj 2020-05-19

HashMap源码分析

HashMap是一个底层用数组+链表实现的存储KV键值对数据结构，它允许null键和null值。HashMap的存储规则是，根据K的hashCode运算得到hash值，然后根据hash值运算得到下标，如果数组中该下标没有值就放入，有值就一个一个比较是否ha

凉白开 2020-04-16

HashMap源码浅析

"HashMap"由“hash”和“map"两个单词组成，这里的”map"表示“映射”而不是“地图”的意思，两个单词连起来就是“哈希映射表”。Map是一个接口，它有TreeSet 、LinkedHashMap、Enu

zagnix 2020-02-21

如果你这么去理解HashMap就会发现它真的很简单

Java中的HashMap相信大家都不陌生，也是大家编程时最常用的数据结构之一，各种面试题更是恨不得掘地三尺的去问HashMap、HashTable、ConcurrentHashMap，无论面试题多么刁钻的问，只要我们真正的掌握了它的设计思想，便可以不变应

rein0 2020-02-03

Rust 两个数组的交集 II HashMap

给定两个数组，编写一个函数来计算它们的交集。输出：[4,9]这道题的解题思路就是，把第一个数组出现的数字当作钥匙记录起来，并且记录有几把钥匙，然后遍历下一个数组，数字当作锁，打开一把匹配的锁需要消耗一个钥匙。然后没有钥匙了就打不开。最后记录互相匹配的钥匙和

归去来兮 2020-07-28

ConcurrentHashMap原理分析

CHM 的使用 ConcurrentHashMap 是 J.U.C 包里面提供的一个线程安全并且高效的 HashMap，所以 ConcurrentHashMap 在并发编程的场景中使用的频率比较高，那么这一节课我们就从 ConcurrentHashMap

dxyadc 2020-06-26

HashMap 和 Hashtable 有什么区别？

1 存储：HashMap 运行 key 和 value 为 null，而 Hashtable 不允许。2 线程安全：Hashtable 是线程安全的，而 HashMap 是非线程安全的。3 推荐使用：在 Hashtable 的类注释可以看到，Hashtab

ZMichael 2020-06-02

HashMap 和 Hashtable 的区别

（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。。HashMap 默认的初始

luohui 2020-05-31

cc分享java：深入理解java各种集合的线程安全

多个线程同时操作同一个variable，就可能会出现不可预知的结果。根据上面的解释，很容易想出相应的scenario。这样就实现了所谓的线程安全。线程安全就是说多线程访问同一代码，不会产生不确定的结果。编写线程安全的代码是低依靠线程同步。　　Vector和

付春杰Blog 2020-05-31

HashMap和HashTable的区别

Hashtable是java一开始发布时就提供的键值映射的数据结构，而HashMap产生于JDK1.2。虽然Hashtable比HashMap出现的早一些，但是现在Hashtable基本上已经被弃用了。而HashMap已经成为应用最为广泛的一种数据类型了。

shayuchaor 2020-05-30

最常见的Java面试题及答案汇总（二）

Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有List与Set。Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对

alicelmx 2020-05-19
spb

spb

W3CSchool教程
HTML 教程
CSS 教程
Bootstrap 教程
Javascript 教程
jQuery 教程
后端教程
C 教程
Java 教程
PHP 教程
Python 教程
Go 教程
移动开发
Android 教程
Swift 教程
Kotlin 教程
jQuery Mobile 教程
ionic 教程
关于我们
新闻动态
联系方式
招聘英才
安科实验室
帮助与反馈

安科网(Ancii)，中国第一极客网

Copyright © 2013 - 2019 Ancii.com

京ICP备18063983号 京公网安备11010802014868号