HashTable源码分析
2019-10-22 本文已影响0人
九点半的马拉
Map的架构
[图片上传失败...(image-7ca267-1571749288939)]
从上面图中可以看出，Map类型的子类主要有TreeMap、HashMap和HashTable等。
其中，TreeMap和HashMap主要继承的是AbstractMap，也同时实现了Map接口，而HashTable则继承了Directionary，同时也实现了Map接口。
HashMap和HashTable的内容都是键值对，都不保证次序，但HashMap是线程不安全的，而HashTable是线程安全的，它的key和value都不允许为空。
HashTable的继承情况如下：
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
其中，Dictionary抽象类定义了键值对的基本操作。
public abstract
class Dictionary<K,V> {
public Dictionary() {
}
abstract public int size();
abstract public boolean isEmpty();
abstract public Enumeration<K> keys();
abstract public Enumeration<V> elements();
abstract public V get(Object key);
abstract public V put(K key, V value);
abstract public V remove(Object key);
}
HashTable源码分析
- HashTable成员变量
// 键值对数组
private transient Entry<?,?>[] table;
//数组的实际数量
private transient int count;
//阈值，用来判断是否要调整HashTable的容量 （threshold = 容量 * loadFactor）
private int threshold;
//加载因子
private float loadFactor;
//被修改的次数
private transient int modCount = 0;
//版本序列号
private static final long serialVersionUID = 1421746759512286392L;
- 构造函数
HashMap的构造函数有四种形式，你可以手动设置数组的初始化容量和加载因子，如果没有设置，默认的初始化容量值为11，加载因子为0.75, 也可以将一个给定的同等类型的Map构造映射为新的HashTable.
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); }
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f); }
public Hashtable() {
this(11, 0.75f); }
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t); }
- 判断是否包含该value
首先将该键值对数组赋值给tab数组，然后从尾到头逆向查找,然后在该位置的单向链表中进行依次查找，找到后返回true
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
Entry<?,?> tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false; }
- 判断是否包含该key
在获取到该key的hash值后，会与0x7FFFFFFF执行按位与操作，这样做是为了保证index的第一位是0，也就是为了保证得到的是一个正数，因为有符号数的第一位是0时代表为正数，1表示为负数。
然后根据index找到该key所在数组中的位置，然后开始单向遍历该位置的链表。如果该节点的hash值与要查找的key的hash值相等，并且key值相等，则返回true。
public synchronized boolean containsKey(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
}
return false; }
返回该key上的值的原理同上
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
- HashTable扩容
首先将原来table赋值给oldMap数组，然后将新的数组长度扩展为原来数组长度的2倍+1，如果超出最大值，将设置新的数组长度为最大值。之后，创建一个该新长度的数组。
修改次数+1，并设置新的阈值。
开始初始化HashTable,根据新的容量长度查找在新的数组的位置，之后采用头插法插入到该位置的单向链表的头部。
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] 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<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
- HashTable添加元素
首先它会判断该数组中是否含有该key值，如果有则进行值替换。
如果没有，则利用头插法插入到该数组位置的头结点。
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null; }
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++; }
- HashTable删除元素
如果删除的位置是某一单向链表的非头结点位置，则记录它的前一结点和下一结点，然后将前一结点的next指向它的下一结点。
如果是该链表的头结点的话，就将待删除结点的下一结点赋值给头结点。最后，设置待删除结点的值为null.
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null;
return oldValue;
}
}
return null; }
HashTable与HashMap的不同
- 基类不同：HashTable基于Dictionary类，而HashMap是基于AbstractMap。
- null不同：HashMap可以允许存在一个为null和任意个为null的value,但是HashTable中的key和value都不允许为null。
- 线程安全：HashMap是单线程安全的，多线程不安全，而Hashtable是多线程安全的。
- 遍历不同：HashMap仅支持Iterator的遍历方式，而Hashtable支持Iterrator和Enumeration两种遍历放式。
- 存储结构： HashMap是数组+单向链表+红黑树，而HashTable是数组+单向链表
