开篇
Hashtable作为jdk提供的最原始的key/value存储结构，属于线程安全系列的，所以这边顺便把这个类分析一下，基本上如果你看过了HashMap相关的数据结构，这个看起来就是小菜一碟了。
Hashtable类关系图
Hashtable类关系图
Hashtable源码分析
Hashtable类成员变量
Hashtable中核心的存储结构是table，table中存储的数据结构是Entry对象
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
// 实际key/value存储的table数组
private transient Entry<?,?>[] table;
private transient int count;
private int threshold;
private float loadFactor;
// modCount
private transient int modCount = 0;
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next;
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
Hashtable的构造函数
Hashtable构造函数的核心内容就是初始化loadFactor、threshold等变量，以及根据initialCapacity初始化table对象。
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);
}
Hashtable的put操作
Hashtable的put()方法 采用synchronized方法修饰保证线程安全，put的执行过程就是根据key计算hash值，根据hash值找到table中对应的hash桶后采用倒链法保存节点。
在put过程中如果找到key对应的value，那么就覆盖value值并返回旧value值。
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的get操作
Hashtable的get()方法 用synchronized关键进行修饰保证线程安全，get的过程通过计算key的hash值找table中对应的hash桶，然后遍历hash桶下面的所有的对象链表，通过比较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的迭代器其实核心在于getIterator()方法，该方法内部创建了Enumerator类对象，其中Enumerator类是核心的对象。
Enumerator的hasMoreElements()方法用于判断是否还有下一个变量，nextElement()方法用于返回当前变量的值并将entry指向下一个变量。
Hashtable的遍历是从数组的最后一个非空的元素开始遍历的，遍历完hash桶下的所有链表对象后再往前推进下一个hash桶。
// Types of Enumerations/Iterations
private static final int KEYS = 0;
private static final int VALUES = 1;
private static final int ENTRIES = 2;
public Set<K> keySet() {
if (keySet == null)
keySet = Collections.synchronizedSet(new KeySet(), this);
return keySet;
}
private class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return getIterator(KEYS);
}
}
public Set<Map.Entry<K,V>> entrySet() {
if (entrySet==null)
entrySet = Collections.synchronizedSet(new EntrySet(), this);
return entrySet;
}
private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return getIterator(ENTRIES);
}
}
public Collection<V> values() {
if (values==null)
values = Collections.synchronizedCollection(new ValueCollection(),
this);
return values;
}
private class ValueCollection extends AbstractCollection<V> {
public Iterator<V> iterator() {
return getIterator(VALUES);
}
}
private <T> Iterator<T> getIterator(int type) {
if (count == 0) {
return Collections.emptyIterator();
} else {
return new Enumerator<>(type, true);
}
}
private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
Entry<?,?>[] table = Hashtable.this.table;
// index默认是table.length的长度
int index = table.length;
Entry<?,?> entry;
Entry<?,?> lastReturned;
int type;
boolean iterator;
protected int expectedModCount = modCount;
Enumerator(int type, boolean iterator) {
this.type = type;
this.iterator = iterator;
}
public boolean hasMoreElements() {
Entry<?,?> e = entry;
int i = index;
Entry<?,?>[] t = table;
/* Use locals for faster loop iteration */
while (e == null && i > 0) {
e = t[--i];
}
entry = e;
index = i;
return e != null;
}
@SuppressWarnings("unchecked")
public T nextElement() {
Entry<?,?> 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<?,?> e = lastReturned = entry;
entry = e.next;
return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
}
throw new NoSuchElementException("Hashtable Enumerator");
}
// Iterator methods
public boolean hasNext() {
return hasMoreElements();
}
public T next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
return nextElement();
}
}
网友评论