先看一下HashMap中几个重要的变量
-
DEFAULT_INITIAL_CAPACITY : Map默认的容量,1<<4(左移四位,二进制 10000 ,十进制表示16)
-
MAXIMUM_CAPACITY : Map的最大的容量, 1<<30 (2^30超大的一个值)
-
DEFAULT_LOAD_FACTOR : 负载因子(加载因子),默认是 0.75
-
transient Node<K,V>[] table: Node类型的数组,底层最主要的数组 -
transient int size;集合中元素的个数 -
int threshold;临界值、阀值; 他的作用就是当元素的个数超过它时就去扩大集合的容量 -
final float loadFactor这个也是负载因子,源码中真正操作的是这个属性,这里并没有赋值
看源码前先了解一下HashMap的结构图
HasMap结构图.png
构造方法
在 JDK1.7 与 JDK1.8 中两个构造方法是不一样的,
1.7中的空构造函数
在此版本中,调用空构造的时候会进行一些重要的初始化,比如设置默认的容量和负载因子
public HashMap() {
//这两个值分别是默认的16和0.75
//this(16, 0.75)
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//由于我是1.8版本的,所以下面这个方法并不是1.7的内容,但是方法是同一个,内容有些差别
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
……省略部分代码
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
1.8中的构造函数
在1.8中的空构造并没有像上面那样调用另一个构造,这里只是初始化了负载因子的值
public HashMap() {
//设置0.75
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
先看一下 put() 方法,详细的都写在putVal方法注释了
put 方法中会调用到 hash() 方法,这个方法比之前的要简单一点了,还记得之前要进行好几步的运算就是为了 减少哈希碰撞 简而言之就是为了让算出来的值尽量不一样
现在这个没有之前那么复杂了,主要是因为用到了红黑树处理二进制中大量的冲突,以一种简单的方式进行位运算、异或运算,为得就是减少系统的开销
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//总的数组
Node<K,V>[] tab;
//数组的第一个元素（链表的第一个元素）
Node<K,V> p;
//n 是 数组tab(或者是table)的长度，i 是index,表示数组的下标
int n, i;
//将数组 table 赋给 tab
if ((tab = table) == null || (n = tab.length) == 0){
//resize()方法重新设置table的长度并返回table对象
n = (tab = resize()).length;
}
//如果数组中 table[(n - 1) & hash] 这个位置上是null ,直接放到数组上,这是链表的第一个元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//说明些index上有数据(链表结构或者是红黑树结构)
Node<K,V> e; K k;
//判断hash值是否相等并且key是否相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//将链表中的元素赋给e,(下面会使用put进来的value去覆盖),为的是处理key值相同的情况
//具体的是否覆盖需要看onlyIfAbsent这个参数,普通的put方法是覆盖的,putIfAbsent方法不覆盖
e = p;
else if (p instanceof TreeNode)//判断是否已经是树型结构,TreeNode就是红黑树的模型
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//链表结构
for (int binCount = 0; ; ++binCount) {
//判断是否是链表中最后一个元素(在链表中最后一个元素后面插入新元素)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//当链表大于等于8个元素时,转成树
treeifyBin(tab, hash);
break;
}
//不链表中最后一个元素,这个判断的目的和上面的一样,处理key值相同的情况
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//下一个元素,进入下一次循环
p = e;
}
}
//处理key相同的情况
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent 判断是否覆盖老的value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//这里 threshold 是数组容量的75% 大小,会在第一次put时在resize()方法中进行初始化
//size 是数组的总容量
if (++size > threshold){
//达到数组总大小的75%时会进行扩容
resize();
}
afterNodeInsertion(evict);
return null;
}
get()方法的逻辑与put()很相似,这里就不写了,
resize()是对table数组进行扩容,然后将老的数组释放,(赋值null)
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//值为 数组总大小 * 0.75
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 以指2的倍数增加(8->16->32->64)
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {//第一次put 时会执行到这(JDK1.8)
//临界值。总大小的75%
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 对老数组释放
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
...省略代码
}
}
}
return newTab;
}
完!!!
网友评论