HashMap是java的基本数据类型,是一种基于key和value的数据类型。因为其通过hash值来进行寻址,所以hashmap在数据量比较的的集合类型中还是比较快的一种数据存储方式。
我们通过之前的分析知道,list和set是同根同源的。set也是又list演变而来。那么map又是怎么样的呢?
因为jdk7和jdk8中的hashmap是不一样的。当然是jdk8比较厉害了。所以我们还是直接分析jdk8吧,这分析的过程中我们也会对jdk7有一个简单的介绍。
想想看,如果你是一个编程大师,那你如何定义个map的类型,也就是映射的类型。通过一个字然后找到其他的数据。显然我们会用数学的方式,通过某种计算然后找到我们的目标。而在hashMap中,这种算法叫做hash算法。
那么如果我们这么干,会遇到什么问题?如果我们设计一个list,然后在创建的时候指定容量,然后我们通过hase计算其下标,然后将值存入到里边。那么显然会有一部分列表处于空的状况,如果我们的hase算法不够优秀。那么我们的list的空置率同样很大。那么会消耗很多内存。
即便我们的hase算法能够让list的空置率降低到10%,那么如果随着加入的数据越来越多,势必有很多空间被无情浪费。这是我们无法忽视的。所以jdk采用的方式list只做索引,也就是通过hase算法计算的值,通过确定list的位置,然后在这个list的空间下挂链表的方式。
如果我们传入的值得hase值大概相同,就挂到这个链表下。如果重复元素就覆盖掉。在java8中则采用链表+红黑树的方式。我们知道红黑树树寻址的数学期望是最优的,使用红黑树进一步降低了链表遍历的时间消耗。这是jdk开发工程师的策略,如果让我们去想这样一套流程,我们或许会想一些别的方式,或许更加厉害,但是对于像我这样的初级人员来说设计算法的这种事情太遥远。核心的因素还是数学呀!
那么我们就怀着对jdk工程师的崇拜开启我们对haseMap的学习。希望能够从中学一点心学。
可以看到hashMap中特别复杂,里边有很多内部类,一般来说有内部类的基本都是定制的。也就是只对这个类有作用。同样也说明这个类的基础性和不可变性。而根据上边我们的逻辑,那么HashMap的这些内部类必然实现了更加复杂的功能,因为我们可能只对Node比较熟悉。
所以咱们还是避免正面对接,还是按照初始化、添加元素、删除元素的方式从侧面看看这些内部类到底干了什么事。
我们看到hashmap有4个初始化方式。
在HashMap中的变量loadFactor是一个加载因子,也只有第一种方式可以我没人为的指定加载因子,其他情况的下都是采用默认值 static final float DEFAULT_LOAD_FACTOR = 0.75f;至于为何是0.75,的问题,我们后边再进行解释。除此之外我们看到容量这个单词,也就是说hashmap对容量是有要求的,不能大于最大值。
而最大值 static final int MAXIMUM_CAPACITY = 1 << 30;应该是一个很大的值了,看到了没,jdk中也是将一些特殊的值用静态变量进行声明的,为啥呐?复用比较好。否则变动起来很难。
也就是初始化的主要就是对这些参数进行赋值,然后对传入的值进行判断。然后对初始容量进行定值,如果没有传入容量大小,则直接采用默认容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16至于为啥是16?可能和hase算法有关。当然我们看到初始化的过程并没有进行容量大小的设置,仅是对容量的设置,并没有初始化Node数组。
目前来说我们知道了这些值决定着hashMap的一些基础,而这些值肯定和我们操作的容器有关系了。看看Node是什么结构的。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
看的出来这个类比较简单,主要有int类型的hase值,K的key,然后就V类型的value。然后就直接是next了,那么我们估计hashmap的主体容器也就是这个了,通过List这个Node做List,然后这个Node还有链表的特效。显然Node下边又可以挂自己。貌似是一石二鸟。
我们看到这个Node类的HashCode方法,是通过Objects.haseCode方法对传入的k和v进行与操作。显然如果我们传入两个一样的key和value,那么得到的haseCode值是一样的。这里的equals方法对传入key和value进行判断的,也就是上边我们传入如果是同样的K和V基本在equals这里判了死刑。
那么hashMap如果组织这Node?作为基础的承重器,按照之前的说法肯定要有一个list呀,至于链表,Node自带了。哈哈
如图所示Node的数组出现了,我本以为它应该是一个list,没想到是个数组。或许是咱们对数组使用过少有些陌生的原因吧。
现在容器也有了,限制条件也有了。我觉得我们可以向操作部分进军了。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
添加元素的时候,看到调用的是putVal方法,第一个参数将key的hase值作为参数,第三个参数是value的值。这里计算hase的时候,把key的hasecode的值右移16位,然后与本身进行异或操作。也就是高位该在额都在,后边的不一定。这么做的作用就能让我们的Node数组的聚合度高一点。也就是把以下haseCode大概相同都能拉到同一个链表上来。
意思就是这里的hase并不是实际意义上的hase。而是经过处理的结果。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
//这里的table就是真实的容器,如果容器还是空的
if ((tab = table) == null || (n = tab.length) == 0)
//就给对tab进行重新初始化,然后进行将tab的容量大小设置到n,这里的tab和n应该都是零时变量。这里的resize()就是进行Node数组的初始化过程。
n = (tab = resize()).length;
//因为n表示是数组的大小,那么i就是数组的最后一位的下标,通过这个下标与hash值得与操作,基本就是末尾端数据了。也就是定位到了数组的具体元素上,然后看这个元素是否为空
if ((p = tab[i = (n - 1) & hash]) == null)
//如果为空,那么就将这个新值创建一个节点填入到这个位置中。
tab[i] = newNode(hash, key, value, null);
else {
//如果发生冲突
Node<K,V> e; K k;
//用冲突节点的hash值与当前的hash值进行比对,如果数组中的hash与新填入的hash以及key进行比较,
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//相同的话就将冲突的赋值给e
e = p;
else if (p instanceof TreeNode)
//如果p节点是一个树节点,显然这个TreeNode应该是继承了Node。那么就把这个元素压入到红黑树中
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);
//如果节点数目大于转换为红黑树的转化限制8,也就是当大于8的时候就将其转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//这块应该是跳转红黑树了
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;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 添加一个元素之后对modCount进行加一操作
++modCount;
//对hashMap的容量进行加一操作,如果size大于了threshod就重新调整
if (++size > threshold)
//重做hashMap,相当于扩容了
resize();
afterNodeInsertion(evict);
return null;
}
那么这个扩容是怎么扩的呐?这块感觉肯定是比较复杂了,毕竟那写hash值得重新计算了。基本类似于一场财富再分配过程。场面比较血腥。
final Node<K,V>[] resize() {
//拿到老的数组
Node<K,V>[] oldTab = table;
//老的数组容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//老的重做限制,这个threshold和加载因子有关系
int oldThr = threshold;
新容量
int newCap,
新的重做限制
newThr = 0;
if (oldCap > 0) {
// 超过最大值就不再扩充了,就只好随你碰撞
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值,就扩充为原来的2倍,并且还要不小于最大容量限制
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)
//把oldThresh扩大两倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// 如果为0,就是初始化的那种状态,就让容量等于初始化容量
newCap = DEFAULT_INITIAL_CAPACITY;
//设置扩容上限
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//声明新的数组,进行resize操作了。
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把老的Node数据逐步移动到新的Node数组中,相对于重新做一遍
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//用e缓存老的节点
if ((e = oldTab[j]) != null) {
// 清除原来table[i]中的值
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
如果是红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 链表操作
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 计算出的索引值等于现在的索引值。
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap,不是原索引,就移动原来的长度
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到Node数组中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到Node数组中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
到这里put方法基本已经明确了
那么get方法是怎么样的?
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e;
int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
如果命中了Node数组元素,直接取出Node返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果不是Node数组的元素,则查询链表
if ((e = first.next) != null) {
if (first instanceof TreeNode)
//如果是红黑树,则从红黑树中取
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//否则从链表中遍历
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
另外tableSizeFor方法看起来挺神秘,但是好像也是处理的容量大小。好像要表达的意思是我们传入的容量其实并不是HashMap接受的容量,真实的容量应该是这里运算之后的结果。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
我们看到的是先把我们传入的容量-1,然后进行右移,然后与本身进行或运算。这样的效果必然是首位一大堆1,当然右移之后右边也是1;
比如cap=5,5-1=4),
0100|0010=0110
0110|0011=0111
之后不断的右移,最后的结果就是0111,也就是4+2+1=7,然后7+1=8,也就是最终的容量是8.差了一下资料,这块的意思就是要让Node数组的容量为2的多少次幂。刚才做了那么多运算,也确实,先让第一位之后的所有不管是1还是0都变成1,然后在加1,让最后一位变成0,这样最后的结果显然是2^n,也就达到了最后的目标。