集合框架之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时的特殊处理。