hashMap sdk25解析 以及简单提及26的区别

2018-02-27 11:33:04来源:https://www.jianshu.com/p/a3417cb0f51e作者:Dynamic_2018人点击

分享


hashMap作为一个典型的数据结构,之前或多或少都了解一些,这一次就详细的看一下它管理hashshu以及(链表、红黑树),对阈值的管理扩容,以及hashmap在多线程里面存在的非线程安全。
在jdk1.7和1.8hashMap的实现稍有变化,对应于android里面的sdk25 26;从我们熟知的数组+链表,变成了数组+链表或者红黑树。红黑树的作用查找方便,从链表从头结点往下找的O(N)变成O(lgn);
由于sdk25的hashMap不含红黑树的操作,所以这个相对简单一些,从这个入手。


构造函数:

hashMap主要是3个参数 初始容量 负载因子 阈值
初始容量决定初始阈值,当前节点数量>阈值*负载因子时会触发扩容,扩容很耗时
通常我们使用时 Hashmap map = new HashMap();


public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

static final int DEFAULT_INITIAL_CAPACITY = 4;
会使用默认的容量 4,负载因子0.75;


在sdk26里面默认值是16和0.75;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


put:
  public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//hash方法 根据key获取hash值,尽量使值散列在低位
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
//位运算取余数 也就是hash值位于哪个hash桶
int i = indexFor(hash, table.length);
//遍历这个链表,如果有hash值相同且key相等的则值替换为新值,并且返回旧值
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//从这里可以联想到为什么重新obj的equals时 也要重写hash方法
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//如果这个链表没有,则说明之前没有put过多对应的,需要新加一个进去
modCount++;
addEntry(hash, key, value, i);
return null;
}

从上面的代码和注释可以看到通过对key进行hash运算得到hash值,然后取余拿到Index。如果index对应的链表存在了,则更新key对应的value;如果没有则需要addEntry,并返回null表示不存在相同的值。
hash运算暂时不用深究,可以知道的是,hash出来的hash值必然是尽量散列在低位的,因为Index是根据取余求出来的。如果不同的key都散列在高位,低位基本不变,必然导致index冲突非常严重,hash碰撞。


 static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}

因为length是2的次方(主要由扩容的逻辑保证),length-1在二进制必然是11....11的形式,与运算也相当于求余了,计算机运算得更快一些。


addEntry:

addEnty在put新元素的时候调用。因为在sdk25里面元素叫做hashMapEntry的原因吧。在26里面称为Node;不过貌似也只是换了个名字,也是继承map.entry ,变量及方法都一样。


 void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}

因为涉及到新加元素了,所以要判断一下是否要扩容了,如果不需要扩容,就直接加到链表里面去。


 void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
//可以看到是放入到链头
HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}

可以看到添加到链表的逻辑,实际上是把新加的元素作为node,它的next指向之前的node,也就是每次新加的其实是加到链表的表头,而不是链尾巴哦。可能是觉得


如果addEntry的时候发现当前的size已经到阈值了,这时候就要扩容了resize;


resize:
  void resize(int newCapacity) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//hashMapEntry数组变成两倍,只是元素需要重新计算index;
//因为如果之前的长度0-15 在index=0位置的0、16、32、48这些就不会都在index=0这个位置了
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (HashMapEntry<K,V> e : table) {
while(null != e) {
HashMapEntry<K,V> next = e.next;
//在两倍长的数组里重新计算index
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}

如代码注释扩容时重新计算index,以及所有元素在新的数组的位置。看到这个操作把所有的元素都检查了一遍,对比查找get的遍历单个链表(红黑树上耗时更低),这个transfer确实是非常耗时了。


在sdk26 put方法多了检查当前节点是否是树节点的操作,如果是红黑树的结构,就是通过树查找。而且熟悉树的都知道,树的查找速度快大部分是因为维护树比较麻烦,所以红黑树扩容更加麻烦。


get:

如果put的逻辑搞懂了,get就是超级简单了


 final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}

通过key得到hash值,取余得到index;遍历查找key和hash都相等的,如果没有就返回空。


hashmap非线程安全

在多线程并发的情况下,比如多个线程都在put,addEntry 当前的头结点是preNode,线程的结果新加一个node在链头,但是大家都以为之前的头结点是preNode,然后 newNode.next = preNode,那么必然导致其他同时在操作的线程的结果被覆盖掉。
在resize扩容的时候,如果一个线程先扩容完成了,第二个线程再扩容,但是里面的table已经变成了扩容后的,这些都是会引起问题的,比如链表死循环的问题。


如何解决这个问题呢?线程同步的问题,我们可以用同步手段处理。但是Java提供了更有效的ConcurrentHashMap。








最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台