我的个人博客地址:http://swaiter.github.io
HashMap 简介
HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
值得注意的是HashMap不是线程安全的,如果想要线程安全的HashMap,可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。
Map map = Collections.synchronizedMap(new HashMap());
也可以使用ConcurrentHashMap
HashMap的数据结构
HashMap的底层主要是基于数组和链表来实现的,它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的,只要hashCode相同,计算出来的hash值就一样。如果存储的对象对多了,就有可能不同的对象所算出来的hash值是相同的,这就出现了所谓的hash冲突。
HashMap属性
//树化链表节点的阈值,当某个链表的长度大于或者等于这个长度,则扩大数组容量,或者数化链表
static final int TREEIFY_THRESHOLD = 8;
//初始容量,必须是2的倍数,默认是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大所能容纳的key-value 个数
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//存储数据的Node数组,长度是2的幂。
transient Node<K,V>[] table;
//keyset 方法要返回的结果
transient Set<Map.Entry<K,V>> entrySet;
//map中保存的键值对的数量
transient int size;
//hashmap 对象被修改的次数
transient int modCount;
// 容量乘以装在因子所得结果,如果key-value的 数量等于该值,则调用resize方法,扩大容量,同时修改threshold的值。
int threshold;
//装载因子
final float loadFactor;
构造方法
默认构造方法将使用默认的加载因子(0.75)初始化。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
put方法
执行逻辑:
1)根据key计算当前Node的hash值,用于定位对象在HashMap数组的哪个节点。
2)判断table有没有初始化,如果没有初始化,则调用resize()方法为table初始化容量,以及threshold的值。
3)根据hash值定位该key 对应的数组索引,如果对应的数组索引位置无值,则调用newNode()方法,为该索引创建Node节点
4)如果根据hash值定位的数组索引有Node,并且Node中的key和需要新增的key相等,则将对应的value值更新。
5)如果在已有的table中根据hash找到Node,其中Node中的hash值和新增的hash相等,但是key值不相等的,那么创建新的Node,放到当前已存在的Node的链表尾部。
如果当前Node的长度大于8,则调用treeifyBin()方法扩大table数组的容量,或者将当前索引的所有Node节点变成TreeNode节点,变成TreeNode节点的原因是由于TreeNode节点组成的链表索引元素会快很多。
5)将当前的key-value 数量标识size自增,然后和threshold对比,如果大于threshold的值,则调用resize()方法,扩大当前HashMap对象的存储容量。
6)返回oldValue或者null
put 方法比较经常使用的方法,主要功能是为HashMap对象添加一个Node 节点,如果Node存在则更新Node里面的内容。