HashMap原理与源码解析

HashMap原理

数组是一块连续的内存空间，所以有可能造成内存空间浪费

链表是不连续的空间，但是只能通过顺序访问

总结：

• 数组：查改快
• 链表：增删快

HashMap的数据结构：

数组+链表

JDK1.8 后用红黑树

HashMap说到底也是一个Map的结构，Map是一组键值对

如何去存储这样一个键值对呢？

最简单的思路就是用一个数组去存

但是数组的索引是下标(即数字)，不能直接通过key获取到value值

如上图，还是得通过一个个遍历的方式才能获取到key所对应的value

所以就需要有hash()操作：将key转化为数字（即下标）

但是还会存在一个哈希碰撞的问题：

所以就会出现链表的结构，将冲突的数据直接添加在后面

数组+链表的结构在代码中如何实现呢？

只需要在原先的结构上再添加一个next的结构

还有一个问题：这样存储键值对的数组大小应该开多少呢？

总不能只存储一个键值对也采取整个int范围吧？

上图采用了999的数组大小(这里只是举个例子)

如果hash() 值大于999时，则需要对其进行mod操作来防止数组越界

所以当两个产生哈希碰撞的对象进行比较时，应该首先比较它们的hash值，因为这样比比较两个对象高效的多

所以也需要存储对象的Hash值：

HashMap 1.7 源码解析

1.7 HashMap 底层数据结构：

构造方法

构造方法：无参构造函数会调用这个双参数构造函数

arg1：默认的数组大小 (默认是16)

arg2：默认的满载率 (默认是0.75f)

双参数构造函数:

先做边界判断，再赋值满载率和数组大小

调用init()方法：（空方法，是给子类如LinkedHashMap进行实现的）

这个数组所对应的成员变量：Entry<K, V>[] table

Entry结构：对应着刚才将的key，value， next 和 hash值

put方法

put()方法:

先判断是否为EMPTY_TABLE, 使用inflateTable() 将这个table创建出来

inflateTable()：

将大小设置为传入参数的接近2的幂次的大小 ( roundUpToPowerOf2() 方法的作用 )

在这里进行数组创建

( 这里可以忽略initHashSeedAsNeeded() 这个方法)

putForNullKey(): Key为Null的情况

modCount 对HashMap进行增加和操作时会进行++，如果有多个线程进行访问，则会抛出异常

HashMap不是线程安全的

继续看put() 方法：

hash()方法获取key的hash值：

indexFor(hash, table.length) 达到取模的效果：

获取到索引之后：遍历该索引上的列表判断是否为相同的key （先判断hash值，再判断key对象）

如果碰到相同的key就进行更新操作

如果不存在相同的key，则modCount++

调用addEntry()方法：

先判断是否需要扩容

createEntry() :

插入过程：如果索引位置上有节点，那么原本的结点会被新的节点挤到后面（头插法）

扩容操作：

transfer(): 将旧HashMap上的节点转移到新的HashMap上：注意此时hash的值是与新的长度相&的结果，所以位置有可能会改变

put() 过程总结：

习题

HashMap 1.8 源码解析

1.8 HashMap 底层数据结构

构造方法：

put() 方法

hash() 方法：

putValue(）方法：