HashMap源码解析
前言
- 本文是关于HashMap的源码解析
- 将讲解JDK1.7 & 1.8的HashMap
- 会将两个版本作为对比来进行解析和学习
源码解析
JDK 1.7
- 基本参数
// HashMap的初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 4;
// HashMap的最大容量
static final int MAXIMUM_CAPACITY = 1 30;
// HashMap的扩容因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 键值对的个数
transient int size;
- 构造函数
/** * initialCapacity 就是初始容量
* loadFactor 就是它的负载因子
*/
public HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity)
public HashMap(Map<? extends K, ? extends V> m) {
public HashMap()
好了,现在我们把基本的一些参数方法都列了出来,让我们开始分析。 我们先一步步来。从我们最开始 Map userMap = new HashMap()
;点进源码,找到他的构造方法,里面方法体长这个样子: 这里面还调用的另一个构造方法,我们继续跟进: 在这里,它传入了两个值,initialCapacity
是初始容量 loadFactor
是负载因子,哦吼,有丶意思,让我们来研究一下。
/** 在这段代码里
*/
public HashMap(int initialCapacity, float loadFactor) {
// 先判断初始容量是不是0, HashMap的最大容量(这里最大容量是2的30次方
// 如果结果为true的话 就让传进来的输 === 最大容量
if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;
// 判断 传进来的负载因子 是否合法 或者>0, 结果为true 就抛错
if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor; threshold = initialCapacity; init();
}
这就是构造函数的分析了 接下来我们应该看看put方法,看看HashMap到底是怎样存值的
public V put(K key, V value) {
// 先判断了table是否为空,为空才去初始化
// 这里有一个知识点,只有table为空的时候在去进行初始化。 所以有的面试官会问:
// HashMap是不是在new的时候就进行了初始化,这里可以很明显的看到,HashMap在第一个put的时候才去进行的初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 大家都知道 HashMap是可以存null值的,null也可以当作键值去存值
// 这里就是HashMap可以存null值的具体实现了
// 这段代码详细写了 key==null时
// 会将value值放入首位
// 这时候如果再传入null值 会将旧值替换成新值
if (key == null) return putForNullKey(value);
// 计算hash
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//这里是判断HashMap里是否已经有了这个值,如果有了,则用新值替换掉旧值,这也就是说,为什么 map里的key不能重复
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
modCount++;
// 将key value传入map addEntry(hash, key, value, i);
return null;
}
这里额外讲一下怎么计算索引,也就是value存放的地方 在put方法中:计算完哈希后,根据哈希和数组长度去计算对应的索引,也就是这个key应该在数组里哪里存储。 我们发现每次put的时候都需要重新计算hash。HashMap的数据结构是数组+链表,数组特点是查询快增删慢,链表的特点是增删快,查询慢。我们用HashMap肯定主要是为了查询的呀。所以从应用的角度考虑,我们肯定希望这些元素能均匀的分布在数组的不同格子里,这样做查询的时候就会快。 对于计算出来的Hash值,不管是二进制还是字母还是啥啥啥,反正能转换为二进制就是了,能转成二进制那是否就能转成十进制,反正你是个数字,对吧,每个key的hash不一样,那么对数组长度取余是否就算是平均分了。这时候我们先看一眼计算hash的方法
这里发现好多的左移右移的位运算符。目的是通过各种右移能够让高位也参与运算,最大化的避免高位相同低位不同分到同一个索引。
这里计算索引讲完了,接下来我们讲一下存储。废话不多说,上代码
void addEntry(int hash, K key, V value, int bucketIndex) {
//当前的元素个数大于等于扩容阈值的时候,并且分配给新元素的这个位置以及有值,则扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容为原来的数组长度乘2
resize(2 * table.length);
//如果key=null,则hash为0
hash = (null != key) ? hash(key) : 0;
//根据新数组长度重新计算索引
bucketIndex = indexFor(hash, table.length);
}
// 存储
createEntry(hash, key, value, bucketIndex);
}
这里需要讲的是,HashMap的初始值为16,这个16是一个经验值,规定HashMap的容量必须为2的n次方,初始太小了要频繁扩容,太大了又浪费,所以为了平衡选择16。
HashMap的第一次扩容发生在容量达到12的时候,16*0.75=12。
JDK1.8 HashMap
1.8相比1.7 在基本属性上多了两个
// 树化阈值
static final int TREEIFY_THRESHOLD = 8;
// 非树化阈值
static final int UNTREEIFY_THRESHOLD = 6;
1.7的数据结构是:数组+链表
1.8的数据结构是:数组+链表+红黑树