java 集合—— Map 实现类之 HashMap

HashMap 是 Map 的一个实现类，继承了 AbstractMap<K,V> 类，实现了 Map<K,V>、 Cloneable、Serializable 接口。

HashMap 存储的key - value 对。

源码基于jdk 1.7.81

存储思想

HashMap 采用的是链地址法来存储，解决了哈希冲突。

用一个 table 数组来存储元素，每一个元素都是 Entry 类型的，Entry 存储的是一个键值对，许多个 Entry 一起就组成了一个单向链表。

HashMap 的基本操作

插入 key - value 对

先根据算出 key 算出它的 hash 值，根据 hash 找到它的索引值，在 table 数组里面根据 索引值找到单向链表，遍历单向链表，将单向链表中的 key 分别与 当前 key 值相比，如果相等，则覆盖原来的 value 值，若 key 不存在单向链表中，则将新的 key - value对插入到链表头中。

删除 key - value 对

根据 key 计算 hash 值，根据 hash 值找到索引，在 table 数组中找到索引，遍历单向链表，如果链表里面有包含当前索引，就删除当前索引。

 

 

 

HashMap 的扩容

HashMap 的扩容为原来的 2 倍