集合框架之HashMap
ArrayList的实现原理是数组+扩容技术(初始10,而后每次增加50%)
LikedList的实现原理是双向链表
HashMap的实现原理 JDK1.7 是数组+链表(单向)
JDK1.8是数组+红黑树
思想本质都是相同的,但是JDK1.8的效率提高了15%
先説一下为什么JDK底层不会基于ArrayList实现HashMap
使用ArrayList实现HashMap,那么其存储容器一定是一个ArrayList,其实就是数组。
公共方法,获取entry
基于这个容器实现put和get方法
从中我们可以看到,除了在添加元素时ArrayList需要扩容外,在添加和查询时都要循环一遍集合,而且是需要从头循环到尾,效率很低。
(ArrayList本身的查询效率很高,因为ArrayList使用下标查询,而上述是从头到尾查询全部,所以效率低)
基于数组+LinkedList实现HashMap
我们先理解一下,只基于数组的时候(使用hashcode进行存储,暂不考虑数组的扩容)
(先説一个hashcode的常识
两个对象比较,如果hashCode相同,两个对象不一定相同;
两个对象比较,如果equals相同,两个对象一定相同。)
所以,以上代码存在很明显的BUG:就算是保存的对象hashCode都不同,但是总会有余数相同的时候,这时候旧的数据就会被覆盖。
这时候链表就隆重的登场啦~~~~~
数据结构大致就长成这样子:
数组中每一个元素都是一个单项链表
在put时,先根据hashCode确定该对象应该在哪个下标的数组中,然后再根据equals判断是否跟已有的key相同,若有相同的key,则更改原来的value,不同,则开辟新的节点,存放数据;get方法类似。
如果存在冲突,新节点放在链表的最后。
(修改:if(entry.getKey().equals(key)) 改为:
if (entry.key.hashCode() == key.hashCode() && (entry.key == key || entry.key.equals(key))))
以上已经基本实现了hashMap的逻辑,但是还没有实现动态扩容的功能。
经过这么多的铺垫,下面就要正式开始JDK1.7的HashMap了
基于数组+单链表实现HashMap
JDK1.7的HashMap是由数组加单向链表构成
单向链表是什么?Node节点。
Node节点是什么?数据+next。
数据是什么?Entry。
Entry是什么?Key和Value
所以HashMap容器的数据结构已经确定下来了。
先封装一下节点
再创建Node节点实现Entry
下面开始HashMap
四个很关键的变量,不再一一解释了。
实现put方法
因为table容器使用懒加载,所以在添加元素之前先判断是否需要初始化。然后判断是否需要扩容。
这里说一下为什么要扩容,之前说过HashMap不论是在put还是get时,都要循环一遍,以查找是否有相同的key;而HashMap底层使用的是单链表,链表在增删时效率高,而在查询时效率很低,因为它没有下标,需要从头查到尾。所以在容器即将要满时进行扩容,以防止链表过长。
什么时候需要扩容呢?当容器实际所装载的数据>=容器的容量 * 负载因子 时进行扩容。负载因子小于1,所以就是说在容器还没有满的时候就开始扩容了;而负载因子越小,扩容的就越早,HashMap的下标冲突就越少。
每次扩容为原来容量的两倍,扩容时要重新安置容器中的元素。
从put方法中可以看出,HashMap中是可以放null键和null值的。
实现get方法
get方法的实现逻辑就比较简单了,不过在put和get方法中,都不要忘了对于key==null时的特殊处理。