iCMS

容器之路 HashMap、HashSet解析(一)

好喜欢专业转载优质博客文章的地方哦~

1.1 HashMap概述

相信大家在大学的时候都学习过散列表。

使用散列表的查找算法主要分为两步,第一步是利用散列函数将被查找的键转化为一个索引,理想情况下,所有不同的key都会被散列为不同的索引值,但是由于散列函数无法达到完美的散列,所以,我们通常还需要处理碰撞的情况。

处理碰撞的方法主要有两种,一种是拉链法,另一种是线性探测法。

在HashMap中,使用的是拉链法,也就是一个桶,由数组构成,数组的索引代表了散列值,每个数组后接了一个链表。当出现冲突碰撞的情况时,我们将判断这个key是否已经存在,如果存在,那么,替换value值,如果不存在,那么,将这个Entry链接到链表上。

//HashMap中的桶

transient Node<K,V>[] table;

容器之路 HashMap、HashSet解析(一)

那么,当我们查找时,先找到对应的索引值,然后,遍历链表,找到所需的内容。

这里,我们需要注意,如果大量数据的散列值相同,就会导致链表很长,查找效率也就变低了。因此,在JDK1.8中,当链表的长度超出阈值,我们会将链表进行树化,形成红黑树,让查找效率提高。

还有就是,关于Map的resize。Map中有一个参数叫做负载因子loadFactor,当桶中的数据量达到桶的长度乘上负载因子时,就会进行扩容。扩容过程中,会把桶的大小变为原来的2倍,并且,将原来Map中的内容进行重新散列,这部分内容也是HashMap中的一个难点,而且,这个算法十分巧妙。

下面是HashMap中节点的数据结构,是单链表结点

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;

}

}

1.2 插入数据

通常情况下,如果我们使用我们自己创建的类来作为HashMap中的key,那么,我们需要提供一个比较好的hashCode ,如果这个方法有问题,将会影响散列函数的效率。所以,通常情况下,推荐使用不可变类来作为key,例如String。

根据注释可以初步了解插入数据的流程

public V put(K key,V value) {

return putVal(hash(key),key,value,false,true);

}

final V putVal(int hash,boolean onlyIfAbsent,

boolean evict) {

Node<K,V>[] tab; Node<K,V> p; int n,i;

if ((tab = table) == null || (n = tab.length) == 0)

//新建后第一次插入数据会调用resize方法

n = (tab = resize()).length;

//如果找到的索引位置没有插入数据,那么直接新建节点,插入即可

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash,null);

else {

/**

* 如果该索引出已经有数据,可能是两种情况

* 一种是,当前插入节点的key值已经存在,那么需要替换value值

* 另外一种是,出现冲突,需要将结点增加到链表中

*/

Node<K,V> e; K k;

//第一种情况

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

e = p;

else if (p instanceof TreeNode)

//当链表中结点数目达到阈值,转化为树后,新增结点的操作也和普通链表不同

e = ((TreeNode<K,V>)p).putTreeVal(this,tab,hash,value);

else {

//遍历链表,判断是第一二种哪种情况

for (int binCount = 0; ; ++binCount) {

//遍历到最后一个结点

if ((e = p.next) == null) {

//遍历过程中没有找到相同的key,确定新增

p.next = newNode(hash,null);

//新增结点后,如果链表长度超过阈值即>=7,链表转化为红黑树

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;

}

}

//如果是已经存在的结点,替换value

if (e != null) { // existing mapping for key

V oldValue = e.value;

if (!onlyIfAbsent || oldValue == null)

e.value = value;

//HashMap中此方法为空,LinkedHashMap实现了这个方法

afterNodeAccess(e);

return oldValue;

}

}

++modCount;

//达到阈值,扩容

if (++size > threshold)

resize();

//HashMap中此方法为空,LinkedHashMap实现了这个方法

afterNodeInsertion(evict);

return null;

}

1.2.1 确定索引位置

当我们已经有了key的hash值,确定索引位置,也就是散列值的方法如下。

这里n是桶的长度

(n - 1) & hash

这种方式实际上是除留取余法,这种方法方便计算,使用运算符&比mod效率更高一点。

如果n=2^m,那么这样的方式我们就取得了hash值的低m位。

1.2.2 构造函数与tableSizeFor

这里首先介绍一下HashMap的构造函数,主要有以下两个。

public HashMap() {

//没有给出初始值,那么负载因子默认为0.75

this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

}

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;

//这里通过tableSizeFor方法获取到离给定值最近的2的幂

this.threshold = tableSizeFor(initialCapacity);

}

我们需要注意,在HashMap中,桶的大小,也就table的大小必须是2的幂,这样后面计算索引的时候更加方便,因此,我们需要一个算法来获取这个值。

tableSizeFor这里的算法十分巧妙,我也是参考了博客HashMap源码注解 之 静态工具方法hash()、tableSizeFor()(四) - 程序员 - CSDN博客,这里把精华部分摘录一下,再增加一点自己的理解,大家可以到上面的连接中查看详悉解析。

/**

* Returns a power of two size for the given target capacity.

*/

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;

}

首先,我们考虑如何取一个大于给定数字的并且离给定数字最近的2的幂。


容器之路 HashMap、HashSet解析(一)

关于这里为什么减1,后面又加一,实际上,如果给定数字已经是2的幂,这里给出的算法获得的将是其倍数,而不是本身。

下面来看一下JDK中的实现。

容器之路 HashMap、HashSet解析(一)

在这里,我们发现,初始化时,并没有给桶的大小赋初值,这个操作延迟到了放入数据的resize函数中,接下来,我们来看一下resize函数。

1.2.3 resize扩容

扩容主要分为两步,第一步是确定扩容后的桶的大小和再次扩容的阈值threshold,第二步是将原来HashMap中的数据移动到新的Map中。

final Node<K,V>[] resize() {

Node<K,V>[] oldTab = table;

int oldCap = (oldTab == null) ? 0 : oldTab.length;

int oldThr = threshold;

int newCap,newThr = 0;

//由于初始化时没有给table赋初值,所以这里指的时map已经有数据的情况

if (oldCap > 0) {

//已经达到最大值,不能扩容

if (oldCap >= MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return oldTab;

}

//否则,将桶的大小扩大为原来的两倍,并且检查是否超出最大值

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

oldCap >= DEFAULT_INITIAL_CAPACITY)

newThr = oldThr << 1; // double threshold

}

//初始化时,赋了初值,在此处将这个值赋newCap

else if (oldThr > 0) // initial capacity was placed in threshold

newCap = oldThr;

else {

//之前调用了没有参数的构造函数,这里使用默认值,阈值是DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY

newCap = DEFAULT_INITIAL_CAPACITY;

newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

}

//确定阈值

if (newThr == 0) {

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) {

//释放原有的空间,以便GC

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 { // preserve order

//如果后面有链表,那么我们需要特殊处理

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;

}

else {

if (hiTail == null)

hiHead = e;

else

hiTail.next = e;

hiTail = e;

}

} while ((e = next) != null);

//将两个链表连接到正确的位置

if (loTail != null) {

loTail.next = null;

newTab[j] = loHead;

}

if (hiTail != null) {

hiTail.next = null;

newTab[j + oldCap] = hiHead;

}

}

}

}

}

return newTab;

}

这段代码中,最为巧妙的地方就是如何找到已有结点在新map中的位置。

前面已经说过,一个entry的索引位置实际是hash值的低m位,那么扩容后,这个取值就会变为低m+1位。这样,如果hash值的第m+1位是0,那么这个数据还在原来的位置;如果这位为1,那么这个数据就会在原来位置加上oldCap的位置处。

理解了这部分内容,我们就可以了解上面的算法为什么将原来的一条链表分为两条了。

那么我们的重点就是获得这个m+1为的值,方法如下

e.hash & oldCap

容器之路 HashMap、HashSet解析(一)

至此,我们对扩容已经有了一个深入的了解。关于HashMap的树化,已经树化后扩容的移动问题,我们将在下一篇中介绍。

0

上一篇:

:下一篇

精彩评论

暂无评论...
验证码 换一张
取 消