HashMap 主要用来存放键值对,它基于哈希表的 Map 接口实现,是常用的 Java 集合之一,是非线程安全的。
HashMap
可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个
HashMap
默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。并且, HashMap
总是使用 2 的幂作为哈希表的大小。
2.负载因子
loadFactor 负载因子是控制数组存放数据的疏密程度,loadFactor 越趋近于 1,那么 数组中存放的数据(entry)也就越多,也就越密,也就是会让链表的长度增加,loadFactor 越小,也就是趋近于 0,数组中存放的数据(entry)也就越少,也就越稀疏。
loadFactor 太大导致查找元素效率低,太小导致数组的利用率低,存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。
给定的默认容量为 16,负载因子为 0.75。Map 在使用过程中不断的往里面存放数据,当数量超过了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容,而扩容这个过程涉及到 rehash、复制数据等操作,所以非常消耗性能。
3.增加元素
put 方法
HashMap 只提供了 put 用于添加元素,putVal 方法只是给 put 方法调用的一个方法,并没有提供给用户使用。
对 putVal 方法添加元素的分析如下:
-
如果定位到的数组位置没有元素 就直接插入。
-
如果定位到的数组位置有元素就和要插入的 key 比较,如果 key 相同就直接覆盖,如果 key 不相同,就判断 p 是否是一个树节点,如果是就调用
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)
将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。
我们再来对比一下 JDK1.7 put 方法的代码
对于 put 方法的分析如下:
-
① 如果定位到的数组位置没有元素 就直接插入。
-
② 如果定位到的数组位置有元素,遍历以这个元素为头结点的链表,依次和插入的 key 比较,如果 key 相同就直接覆盖,不同就采用头插法插入元素。
hashmap之前是使用头插法,后来改为尾插法,是因为头插法在多线程情况下会产生环形链表