上一章手写LinkedList核心源码,本章我们来手写Java HashMap的核心源码。 我们来先了解一下HashMap的原理。HashMap 字面意思 hash + map,map是映射的意思,HashMap就是用hash进行映射的意思。不明白?没关系。我们来具体讲解一下HashMap的原理。
//1 存 HashMap<String,String> map = new HashMap<>(); map.put("name","tom"); //2 取 System.out.println(map.get("name"));//输出 tom 复制代码
使用就是这么简单。
我们知道,Object类有一个hashCode()方法,返回对象的hashCode值,可以理解为返回了对象的内存地址,暂且不管返回的是内存地址或者其它什么也好,先不管,至于hashCode()方法回返的数是怎么算的?我们也不管
第1 我们只需要记住:这个函数返回的是一个数就行了。 第2 HashMap内部是用了一个数组来存放数据
1 HashMap是如何把 name,tom存放的?下面我们用一张图来演示
从上图可以看出: 注:上图中数组的大小是7,是多少都行,只是我们这里就画了7个元素,我们就以数组大小为7来说明HashMap的原理。
2 下面再来看看如何取?也用一张图来演示底层原理,如下
由上图可知:
存的时候,如果不同的key的hashCode对数组取余数,都正好相同了,也就是都映射在了数组的同一位置,怎么办?这就是hash冲突问题 比如 9 % 7 == 2 , 16 % 7 == 2
都等于2 答:数组中存放的是一个节点的数据结构,节点有next属性,如果hash冲突了,单链表进行存放,取的时候也是一样,遍历链表
如果数组已经存满了怎么办? 答:和ArrayList一样,进行扩容,重新映射
直接使用hashCode()值进行映射,产生hash冲突的概论很大,怎么办? 答:参考JDK中HashMap中的实现,有一个hash()函数,再对hashCode()的值进行运行一下,再进行映射
由上可知:HashMap是用一个数组来存放数据,如果遇到映射的位置上面已经有值了,那么就用链表存放在当前的前面。数组+链表结构,是HashMap的底层结构 假如我们的数组里面存放的元素是QEntry,如下图:
594516-20181128085125518-59591486.png
上面分析了原理,接下来我们用最少的代码来提示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整个类的源码发出来
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()等,还有遍历相关,有兴趣的读者可以自己实现