HashMap、HashTable和Tree的解析及区别(深度)(一)

前言

正如介绍ArrayList和LinkedList和Vector的区别一样,HashMap不管是在日常开发,还是面试中,也都是必须掌握的知识点,并且很多问题,在网上很难见到合适的讲解,在此,我会专挑疑难杂症来和大家一起走进神秘的Map

首先我们来观察写Map相关的UML图:

类结构

从类图中我们可以看出,这三个类直接或者间接的实现了Map接口。并且他们的继承类有两个,一个是AbstractMap,另一个是Dictionary

在这一节中,我们主要分析这三个类

他们的核心是Map接口,我们先从Map入手

Map

官方释意

map是一个包含key,value的数据接口,一个key只可以对应一个value

在实现类中,Entry就是每个键值对,里面有每个键值对的Key和Value

除了putgetremove方法,Map中还定义了一些接口包括

ContainKeyContainValuekeySetvalues这些方法都没有去实现,所以我们在这里不再深纠,而在它的派生类AbstractMap中有初步的实现,那么我们首先来看AbstractMap里面的代码

AbstractMap

成员变量

除了方法以外,其内部有两个静态内部类和两个变量,分别是:

  • transient Set keySet; key的集合
  • transient Collection values; value的集合
  • SimpleEntry<K,V> 内部类
  • SimpleImmutableEntry<K,V> 静态内部类

SimpleImmutableEntry<K,V>官方描述:一个不变的key-value映射,尽管是这个名字,但是它的子类都可能是可变的
为什么是不可变的?因为其没有set方法,其set方法抛出异常。

关于KeySet()和valus()两个方法,其内部进行了实现:

KeySet()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new AbstractSet<K>() {
public Iterator<K> iterator() {
return new Iterator<K>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();

public boolean hasNext() {
return i.hasNext();
}

public K next() {
return i.next().getKey();
}

public void remove() {
i.remove();
}
};
}

public int size() {
return AbstractMap.this.size();
}

public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}

public void clear() {
AbstractMap.this.clear();
}

public boolean contains(Object k) {
return AbstractMap.this.containsKey(k);
}
};
keySet = ks;
}
return ks;
}

这里只po上keySet()方法,其实就是通过了entrySet()拿到了所有的键值对集合,然后遍历集合拿到所有的key

对于values()方法也时候一样的思路也是拿到了所有的Entry,然后进行遍历每个Entry的value

  • KeySetHashMap中的静态内部类,继承于AbstractSet
  • Values也是HashMap中的静态内部类,继承于AbstractCollection
  • AbstractSet继承于AbstractCollectionAbstract的都是抽象类

remove() 、get()、containKey()、containValue()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public V remove(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
Entry<K,V> correctEntry = null;
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}

V oldValue = null;
if (correctEntry !=null) {
oldValue = correctEntry.getValue();
i.remove();
}
return oldValue;
}

这四个为什么要写在一个标题里呢?

因为他们的实现都很类似,都是拿到了所有的EntrySet()之后遍历所有的Entry,从而达到方法本身的目的。

并且在标题里面为什么没有写put方法?因为put方法在此抽象类中没有实现

其中要注意的地方是这里允许移除空的对象。对于entryKey()entryValue也是一样的。

Dictionary

开始也想如何描述Dictionary抽象类,但是全被我删了,不易于理解,简单的解释是一个轻量级的AbstractMap。并且在类的注释中有一句

NOTE: This class is obsolete. New implementations should implement the Map interface, rather than extending this class

注意,这个类是废弃的,新的实现需要实现Map接口,而不是此类。

看来这是java早先的实现Key、value 键值对的方法,之后出来的键值对的数据结构应该都是继承于Map。

并且在它的方法中也看到,这个抽象类类包含了Map中最基本的方法。都是抽象方法,没有具体的实现。

HashMap

与传统的文章解析不同,我一直试图发现HashMap不为人知的一面,为此我参考了很多文章,希望能够带给大家一些收获。

首先我们需要知道,HashMap在Java1.7Java1.8进行了改版,我们秉着由易到难的原则来分析,首先来看1.7的HashMap,我们还是需要了解它普通的一面:

按照惯例先拜一拜各位作者:

1
2
3
4
* @author  Doug Lea
* @author Josh Bloch
* @author Arthur van Hoff
* @author Neal Gafter

主要成员变量

  • static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 //默认大小为16
  • static final int MAXIMUM_CAPACITY = 1 << 30; //最大的容量大小
  • static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认扩容阈值
  • final float loadFactor;//扩容阈值
  • int threshold;

构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
threshold = initialCapacity;
init();
}
1
2
3
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

HashMap的构造,默认传入了一个大小为16,并且加载因子为0.75。就是咱们刚刚介绍成员变量的常量啦。

另外对initialCapacity的限制是不可以小于0

数据结构 bucket+List

hashMap的数据结构有两部分组成,一部分是数组

1
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

数组里面的每一个元素HashMap称之为bucket,英文翻译为桶,桶里面存放的是一个链表的头结点。

记下来介绍桶,这个数据结构,其实就是在之前介绍AbstractMap的中Entry(存储键值对的地方)的实现:

1
2
3
4
5
6
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;//存储的key
V value;//存储的value
Entry<K,V> next;//指向下一个节点
int hash;//此几点的hash值
}

其中keyvaluenext都好理解,hash呢?我们来猜测一下:

这个值一定是在构造Entry的时候传入的,那么除了初始化,就一定在加入一个新的节点的时候传入。由此找到创建新节点的方法createEntry()

1
2
3
4
5
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}

果然!在构造的时候传入了一个hash,顺藤摸瓜,是addEntry方法,看addEntry!:

HashMap的扩容

我们先把寻找Hash的问题放一放,这里遇到了HashMap的扩容机制

1
2
3
4
5
6
7
8
9
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}

createEntry(hash, key, value, bucketIndex);
}

如果当前的大小大于了threshold,那么就会执行resize方法,这里注意:传入的参数为原来table的二倍

为什么是二倍卖个关子后面讲。

如何理解threshold

我们看到在addEntry中会判断size是否大于thresholdthreshold在构造函数中提到过,如果没有指定的话传入的是默认大小16。其他时候的计算是。

1
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

数组大小*装载因子

我们知道默认的装载因子loadFactor为0.75,假如数组超过了扩容之后的0.75倍,则会进行下一次扩容

0.75这是开发者进行计算过的,为了让HashMap连续插入的时候先准备好扩容,所以这个不能太大,有为了不让HashMap的扩容不能太频繁,所以这个不能太小

扩容时候的重新分配

拿到原来数组大小的二倍之后执行了resize方法

1
2
3
4
5
6
7
8
void resize(int newCapacity) {
····//忽略代码无关紧要

Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

总之在resize()方法中是先创建了一个新的数组后,执行了一个transfer()方法,这个方法是用来将原来的HashMap重新分配到新的数组当中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}

关于这个方法在网上搜了一圈,很多人都没明白这个方法,为了方便说明,特意画了一套图便于大家理解

假设从table中到了一个Entry,其实是一个链表头结点是A,下个节点是B

首先做的事情是把B节点存了起来,叫next

然后我们重新计算hash值后得到要插入新的节点的位置i

1
int i = indexFor(e.hash, newCapacity);

下面这一句可以理解为A要和原来的子节点(B)说拜拜了,它将A的next指向了新数组的某个节点。

1
e.next = newTable[i];

然后将新数组的节点替换为e,e是谁,e就是A呀,既然吧A放到了这个newTable当中,那么原来的Entry就脱离了newTable

1
newTable[i] = e;

HashMap就是这样重新的被分配到了链表当中,用的是链表的头插法。

还有最后一句

1
e = next;

这个不要想太多,e指向了下一个节点,也就是B,这样才能遍历整个链表。这一句完全是为了while的遍历而存在的~

由此可见,HashMap的重新分配是非常有消耗的,因此我们要尽量的避免消耗,最好在最初的时候指定可预见的table大小,以及负载因此不要太小

我是华丽的分割线


不要忘了我们的目的,我们是在找hash是从哪里传递过来的,我们从addEntry()继续找调用出,终于找到了put()方法

put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}
  1. put方法其实就是拿到了当前对象的hash值。
  2. 再获取hash对应在数组上的的位置。
  3. 接下来获取到对应数组的实体后,遍历查找链表,如果链表中的hash值与这个key的hash值其相等说明之前存在,就将其value改变。
  4. 如果hash不存在就新建一个插入到链表当中

我们先不分析第一步,首先看第二步,我们要拿到当前对象的hash值后查找在数组中对应的位置,那么我们应该放在哪里呢?

1
2
3
4
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);
}

为什么是2的幂次方

这里有个注释,length必须是2的幂次方。这一点在前面已经说明了,那么它的作用是什么呢?

用hash 与 length-1

比如length为16 那么其二进制位 10000将其减去1就是0 1111

再假设hash是1001 1111 1010 1000 1010 1010 1011 1111

那么16-1与上hash就得到了1111

1111就是我们的在table里面的位置。


终于到了hash计算的地方也就是put方法四个步骤的第一步了

HashMap中的hash算法

1
2
3
4
5
6
7
8
9
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

hash算法是为了做什么呢?

我们考虑几种状况,首先作为基本类型int类型有32位这是毋庸置疑的,并且大家需要知道^是异或的意思

  • 1^1=0
  • 1^0=1
  • 0^1=1
  • 0^0=0

那么我们接下来分析上面的几个操作

1
2
3
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);

其中h^(h>>>7)^(h>>>4) 结果中的位运行标识是把h>>>7 换成 h>>>8来看。

即最后h^(h>>>8)^(h>>>4) 运算后hashCode值每位数值如下:

8=8

7=7^8

6=6^7^8

5=5^8^7^6

4=4^7^6^5^8

3=3^8^6^5^8^4^7

2=2^7^5^4^7^3^8^6

1=1^6^4^3^8^6^2^7^5

结果中的1、2、3三位出现重复位^运算

3=3^8^6^5^8^4^7 -> 3^6^5^4^7

2=2^7^5^4^7^3^8^6 -> 2^5^4^3^8^6

1=1^6^4^3^8^6^2^7^5 -> 1^4^3^8^2^7^5

这样就保证了高位和地位能够尽量的能与地位进行异或操作,从而得到各个位置的值都是不相同。

而代码中看到了h一共异或了四次,>>> 20>>> 12>>> 7>>> 4

也就是2的四次方也正好是8,那么异或的重合最多有8次

也就是说图中的1位置,最多能进行8此异或,这大大的提高了hash值低位不重复的概率。

这个概念有点晦涩,请大家反复研究。

get

1
2
3
4
5
6
7
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);

return null == entry ? null : entry.getValue();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}

int hash = (key == null) ? 0 : hash(key);
for (Entry<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;
}

get方法没什么值得研究的地方,只是拿到了keyhash值后,依次遍历链表,有的话就取出value没有则返回null

进阶

接下来我们要讨论的是通过代码看不明白的一些问题。

rehash的判断

我们在扩容时的传入方法时看到一个值rehash

1
transfer(newTable, initHashSeedAsNeeded(newCapacity));

rehash其实就是initHashSeedAsNeeded(newCapacity)的值

1
2
3
4
5
6
7
8
9
10
11
12
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;//判断hashSeed是否被赋值过
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}

首先判断了currentAltHashing如果hashSeed被赋值过则为0;接下来是:

capacity >=Holder.ALTERNATIVE_HASHING_THRESHOLD

其中Holder实在类构造的时候创建的,饿汉式初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
private static class Holder {

/**
* Table capacity above which to switch to use alternative hashing.
*/
static final int ALTERNATIVE_HASHING_THRESHOLD;

static {
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold"));

int threshold;
try {
threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;

// disable alternative hashing if -1
if (threshold == -1) {
threshold = Integer.MAX_VALUE;
}

if (threshold < 0) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}

ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
}

这里的解释引用http://java-performance.info/changes-to-string-java-1-7-0_06/#comments中翻译

正如你所想那样,这些新特性只用于String类型的Key。如果你想启用这个特性,你可以将系统参数 jdk.map.althashing.threshold设置为非负数(默认为-1),这个值将会成为集合大小的阈值,新的哈希算法将会在超越阈值时使用。提醒一下:哈希算法的只会在重算hash时改变(当没有多余空间的时候)。所以,如果一个集合上一次rehash时的大小为160,而 jdk.map.althashing.threshold = 200,则新的哈希算法将会在集合大小到达320(大概)时启用。

也就是说ALTERNATIVE_HASHING_THRESHOLD是针对一个stringhash值来初始化的,默认情况下其是-1则之前的代码:

1
boolean useAltHashing = sun.misc.VM.isBooted() &&(capacity >= 			Holder.ALTERNATIVE_HASHING_THRESHOLD);

一般情况下是`,那么我们通过下面这句

boolean switching = currentAltHashing ^ useAltHashing;

如果currentAltHashingtrue的话(其不为0)

switching = 1 ^ 0 =1,switching一定为true,返回了true就需要rehash

roundUpToPowerOf2

在扩容的时候如果table为空的时候,也就是hashmap刚刚构造出来的时候,会进行一次inflateTable

其作用就是讲threshold转化为2的幂次方,因为自己在构造的时候可能传入的threshold值不是2的幂次方,

1
2
3
4
5
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
}
1
2
3
4
5
6
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

这里是怎么做的呢?其实核心代码就是Integer.highestOneBit方法

1
2
3
4
5
6
7
8
9
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}

比如i是

1
1000 0000 0000 0000 0000 0000 0000 0000

i>>1无符号右移一位为

1
1100 0000 0000 0000 0000 0000 0000 0000

i|=(i>>1) 也就是 i = i|(i>>1)

结果是

1
1100 0000 0000 0000 0000 0000 0000 0000

同理

i |= (i >> 2);为

1
1111 0000 0000 0000 0000 0000 0000 0000

移动到最后为

1
1111 1111 1111 1111 1111 1111 1111 1111

得到的结果再有符号位移一位(i >>> 1);

0111 1111 1111 1111 1111 1111 1111 1111

最后i - (i >>> 1)

得到结果为

1
1000 0000 0000 0000 0000 0000 0000 0000

是不是还是它本身?因为它是2的幂次方

试想一下如果i不是2的幂次方呢?得到的结果也是一样的,最高位为1,其他都是0


到这里我们HashMap的问题就全部分析完啦,我们的其他结合HashTableTreeMap放在下篇文章里面讲解。

如文章写的有问题,请指正~

谢谢老铁们的支持~

参考

http://java-performance.info/changes-to-string-java-1-7-0_06/#comments

hashMap的hash算法

谢谢您的鼓励~