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

上一节中我们在HashMap、HashTable和Tree的区别(深度解析)(一)

一文中具体解析了HashMap中的种种网上很难搜到的疑难问题,接下来我们来分析HashTable的相关问题

让我们回顾一下类结构:

从继承关系的角度来看HashTable相对于HashMap来说在实现继承有所不同

HashTable它继承的类是Dictionary,有关Dictionary在之前已经讨论过了是一个轻量级的Map,这里不多做讨论,开始分析吧.

数据结构 bucket+List

和HashMap的数据结构一样,是利用Bucket和链表的结合。

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

成员变量

成员变量也都和HashMap类似分别是:

1
2
3
4
5
6
7
8
9
private transient Entry<?,?>[] table;//数组

private transient int count;//整个HashTable的大小

private int threshold;//扩容大小

private float loadFactor;//加载因子

private transient int modCount = 0;//Fast-Faile标记

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public Hashtable() {
this(11, 0.75f);
}
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);

if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
initHashSeedAsNeeded(initialCapacity);
}

public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
  • 到其默认的构造函数传入两个值,一个是大小11,另一个是加载因此0.75f
  • 具体实现中initialCapacity不可以传入小于0的值,但是可以传入等于0的值,将其变为1后构造数组。
  • 如果传入的是一个MapHashTable的大小为Map的二倍

线程安全性

HashTable与其他非并发Map类最大的区别是它是线程安全的。大部分方法都加入了Synchoriezd关键字。

hash算法

1
2
3
4
private int hash(Object k) {
// hashSeed will be zero if alternative hashing is disabled.
return hashSeed ^ k.hashCode();
}

HashTable的hash算法相对于HashMap来说简单了很多,直接与hashSeed做了一个异或的操作,不知道为什么

Josh Bloch为什么不把它设计成和HashMap一样的算法,可能是大神懒了?

keys()与elements()的区别

1
2
3
public synchronized Enumeration<K> keys() {
return this.<K>getEnumeration(KEYS);
}
1
2
3
public synchronized Enumeration<V> elements() {
return this.<V>getEnumeration(VALUES);
}
1
2
3
4
5
6
7
private <T> Enumeration<T> getEnumeration(int type) {
if (count == 0) {
return Collections.emptyEnumeration();
} else {
return new Enumerator<>(type, false);
}
}

获取HashTable里面的所有key和所有value都用到了getEnumeration方法,其都是新建了一个Enumerator<>类,此类是HashTable的一个私有内部类。

开始我看到这个类的时候以为是类似于Set的一个集合,仔细一看Enumerator<>没有指定泛型,一看就不是一般类,看到里面发现:

1
2
3
4
5
6
7
private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
Entry[] table = Hashtable.this.table;
int index = table.length;
Entry<K,V> entry = null;
Entry<K,V> lastReturned = null;
int type;
}

它其实就是一份table的复制

1
2
3
4
Enumerator(int type, boolean iterator) {
this.type = type;
this.iterator = iterator;
}

而它的构造中将type传入,来区分是Key,还是Value。另一个参数是一个boolean

1
2
3
4
5
6
/**
* Indicates whether this Enumerator is serving as an Iterator
* or an Enumeration. (true -> Iterator).
*
*/
boolean iterator;

英文翻译是:表示在执行的时候Enumerator是一个Iterator还是一个Enumeration

那么Iterator我们好理解,是一个迭代器的模型,另一个Enumeration就是我们常见的枚举了我们在Vector中见到过它,那么它里面是什么呢?

1
2
3
4
public interface Enumeration<E> {
boolean hasMoreElements();
E nextElement();
}

很简单就是一个接口自己来实现里面的方法。从方法的字面意思也可以看出来其作用。

那么type的作用呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public T nextElement() {
Entry<K,V> et = entry;
int i = index;
Entry[] t = table;
/* Use locals for faster loop iteration */
while (et == null && i > 0) {
et = t[--i];
}
entry = et;
index = i;
if (et != null) {
Entry<K,V> e = lastReturned = entry;
entry = e.next;
return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
}
throw new NoSuchElementException("Hashtable Enumerator");
}

nextElement()方法中有体现,其从typekey还是value来从Entry中拿到对应的值,想不到你竟然是这样的类。。。

KeySet() 和 values()的区别

我们在看类Enumerator的时候

1
private class Enumerator<T> implements Enumeration<T>, Iterator<T> {

发现了它不仅仅实现了枚举,还实现了Iterator

1
2
3
4
5
public Set<K> keySet() {
if (keySet == null)
keySet = Collections.synchronizedSet(new KeySet(), this);
return keySet;
}

keySet()values()的迭代也是用了Enumerator<T>这个类,生成的两个方法的实现和HashMap一样,都继承到AbstractSetAbstractCollection类。

并且在生成的的时候用到了CollectionsSynchoriezd方法,保证了线程的同步性.是为了支持remove()方法。

从put中看是否可为空

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
public synchronized V put(K key, V value) {
if (value == null) {
throw new NullPointerException();
}
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}

modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();

tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}

// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}
  • 开始就是一个null判断,说明HashTable的value不能为空
  • Key进行hash算法,在之前已经介绍过,但是也没有null判断,如果key为空,则会报空指针异常。

HashTable的扩容重新分配

在上面的代码中很明确如果大小超出了阈值会执行rehash(),其实就是hashTable的扩容算法。

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
protected void rehash() {
int oldCapacity = table.length;
Entry<K,V>[] oldMap = table;

// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<K,V>[] newMap = new Entry[newCapacity];

modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
boolean rehash = initHashSeedAsNeeded(newCapacity);

table = newMap;

for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;

if (rehash) {
e.hash = hash(e.key);
}
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}
  • int newCapacity = (oldCapacity << 1) + 1;中可得知扩容大小而原大小的二倍
  • threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);新的阈值为扩容后的大小* 加载因子(0.75)

HashTable的扩容其实不是我贴上rehash的目的,这里还是看其如何重新分配,看到这段代码后有种似曾相识的感觉,没错用的就是HashMap的头插法重新分配,没有明白的话可以参考我的上一篇文章。

containsKey(Object key)和contains(Object value)的区别

第一个方法的意思顾名思义,第二个方法是是否包含value的方法(吐槽:为什么不写成ContainsValue)

代码很简单,就不贴了,直接总结:

  • ContainsKey:获取key在buckets中的位置然后遍历其Entry,一层循环找Key。复杂度O(n)

  • Contains : 遍历所有buckets然后遍历其Entry,两层循环找value,复杂度O(n的平方)

谢谢您的鼓励~