一、继承关系
public class Hashtable extends Dictionary implements Map, Cloneable, java.io.Serializable
（1）继承自Dictionary抽象类，实现了Map接口，Cloneable接口和Serializable可序列化接口
（2）cloneable:可以重写Object的clone方法，并调用super.clone()获取复制的对象。
（3）所有public方法都是同步的，是一个线程安全的集合类
二、成员变量
private transient Entry[] table
private transient int count;//table中所有entry的个数
private int threshold;//扩容的临界值count >= threshold,threshold=loadFactor*capacity,
private float loadFactor;//加载因子threshold=loadFactor*capacity,加载因子越大，table的利用率越高
private transient int modCount = 0;//单线程，多线程操作可能会引起Hashtable fail-fast，抛出ConcurrentModificationException异常
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//table的最大size
//三种遍历方式
private transient volatile Set keySet;
private transient volatile Set> entrySet;
private transient volatile Collection values;
三、主要方法
1、构造方法
//传递一个table的初始容量和加载因子，table的初始化在构造函数中进行(与HashMap不同，hashmap在put第一个node中进行)。
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;
//设置loadFactor，threshold的值，为table申请空间
this.loadFactor = loadFactor;
//与HashMap不同，table的size可以随意指定，不用为2的整数次幂，甚至都不用超过11（默认的初始容量）
table = new Entry[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
//默认的loadFactor=0.75
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
//默认的capacity=11
public Hashtable() {
this(11, 0.75f);
}
//2*t.size()保证不用插进去就需要扩容
public Hashtable(Map t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
2、同步方法
(1)size
public synchronized int size() {
return count;
}
(2)isEmpty
public synchronized boolean isEmpty() {
return count == 0;
}
(3)keys:依次遍历table中所有的entry的key，调用getEnumeration实现
public synchronized Enumeration keys() {
return this.getEnumeration(KEYS);
}
(4)elements:依次遍历table中所有的entry的value，调用getEnumeration实现
public synchronized Enumeration elements() {
return this.getEnumeration(VALUES);
}
(5)containsValue
public boolean containsValue(Object value) {
return contains(value);
}
//从table[len-1]开始，依次遍历每个bin中的entry查找value
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;
}
(6)containsKey
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;
}
(7)get:查找key对应的value
@SuppressWarnings("unchecked")
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;
}
(8)put
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 entry = (Entry)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;
//当前节点数大于threshold进行rehash
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 e = (Entry) tab[index];
//首部插入新节点
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
(9)remove
public synchronized V remove(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry e = (Entry)tab[index];
for(Entry 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;
}
(10)putAll
public synchronized void putAll(Map t) {
for (Map.Entry e : t.entrySet())
put(e.getKey(), e.getValue());
}
(11)clear
public synchronized void clear() {
Entry tab[] = table;
modCount++;
for (int index = tab.length; --index >= 0; )
tab[index] = null;
count = 0;
}
(12)clone
public synchronized Object clone() {
try {
Hashtable t = (Hashtable)super.clone();
t.table = new Entry[table.length];
for (int i = table.length ; i-- > 0 ; ) {
t.table[i] = (table[i] != null)
? (Entry) table[i].clone() : null;
}
t.keySet = null;
t.entrySet = null;
t.values = null;
t.modCount = 0;
return t;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
3、重要的方法
(1)rehash:扩容，不是同步的
思路：
将capatity*2,根据loadfactor重新设置threshold
依次逆序遍历oldMap中所有Bin中的节点，重新映射到newMap的bin中。这里是从链表头插入，所以顺序与OldMap中的相反。hashMap是插入链表尾部，顺序相同。
与hashMap的resize不同点：
（1）hashMap的resize中可能对table进行初始化，这里初始化在构造函数中进行
（2）扩容方式：hashmap中 newCap=oldCap*2,这样保证新容量依然是2的整数次幂；hashTable中，newCap=oldCap*2+1
（3）映射方式：hashMap中oldMap中同一个bin中node只可能映射到i和i+oldCap两个桶中；hashTable中由于不要求cap是2的整数次幂，所以oldCap中同一个bin中可能映射到newMap的各个Bin中
（4）转移数据方式：hashMap中oldMap和newMap中node在链表中相对顺序不变，是在链表尾部插入的；hashTable中顺序逆向了，在链表首部插入的。
（5）效率：hashMap效率更高，采用&操作映射；HashTable效率低，采用%
（6）桶的结构：hashMap中当节点数大于8时，单链表会转化成红黑树；HashTable始终以单链表存储
@SuppressWarnings("unchecked")
protected void rehash() {
int oldCapacity = table.length;
Entry[] oldMap = table;
// 扩容方法：新容量=就容量*2+1
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
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
//逆序遍历oldMap的桶中的所有节点，并依次映射到newMap中的桶
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry old = (Entry)oldMap[i] ; old != null ; ) {
Entry e = old;
old = old.next;
//oldMap映射到newMap的bin的方法：直接取余
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
//每次都从newMap的链表的头部插入
e.next = (Entry)newMap[index];
newMap[index] = e;
}
}
}
(2)getEnumeration：创建了一个Enumerator对象，该对象实现了Iterator接口和Enumeration接口
private Enumeration getEnumeration(int type) {
if (count == 0) {
return Collections.emptyEnumeration();
} else {
return new Enumerator<>(type, false);
}
}
(3)getIterator:创建了一个Enumerator对象，该对象实现了Iterator接口和Enumeration接口
private Iterator getIterator(int type) {
if (count == 0) {
return Collections.emptyIterator();
} else {
return new Enumerator<>(type, true);
}
}
四、内部类
(1) Entry
实现了Map.Entry接口，带一个指针的节点。
private static class Entry implements Map.Entry {
final int hash;
final K key;
V value;
Entry next;
protected Entry(int hash, K key, V value, Entry next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
@SuppressWarnings("unchecked")
protected Object clone() {
return new Entry<>(hash, key, value,
(next==null ? null : (Entry) next.clone()));
}
// Map.Entry Ops
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
if (value == null)
throw new NullPointerException();
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
(value==null ? e.getValue()==null : value.equals(e.getValue()));
}
public int hashCode() {
return hash ^ Objects.hashCode(value);
}
public String toString() {
return key.toString()+"="+value.toString();
}
}
(2)Enumerator:同时继承了Enumeration和Iterator接口
private class Enumerator implements Enumeration, Iterator {
Entry[] table = Hashtable.this.table;
int index = table.length;
Entry entry;
Entry lastReturned;
int type;//三种类型，KEYS,VALUES,ENTRIYS
/**
* Indicates whether this Enumerator is serving as an Iterator
* or an Enumeration. (true -> Iterator).
*/
boolean iterator;
/**
* The modCount value that the iterator believes that the backing
* Hashtable should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
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();
}
public void remove() {
if (!iterator)
throw new UnsupportedOperationException();
if (lastReturned == null)
throw new IllegalStateException("Hashtable Enumerator");
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//同步加锁
synchronized(Hashtable.this) {
Entry[] tab = Hashtable.this.table;
int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry e = (Entry)tab[index];
for(Entry prev = null; e != null; prev = e, e = e.next) {
if (e == lastReturned) {
modCount++;
expectedModCount++;
if (prev == null)
tab[index] = e.next;
else
prev.next = e.next;
count--;
lastReturned = null;
return;
}
}
throw new ConcurrentModificationException();
}
}
}
五、遍历方式分析
(1)keySet方法
public Set keySet() {
if (keySet == null)
//同步的
keySet = Collections.synchronizedSet(new KeySet(), this);
return keySet;
}
private class KeySet extends AbstractSet {
public Iterator iterator() {
//关键点，调用getIterator(KEYS)实现
return getIterator(KEYS);
}
public int size() {
return count;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return Hashtable.this.remove(o) != null;
}
public void clear() {
Hashtable.this.clear();
}
}
(2)entrySet
public Set> entrySet() {
if (entrySet==null)
//同步的
entrySet = Collections.synchronizedSet(new EntrySet(), this);
return entrySet;
}
private class EntrySet extends AbstractSet> {
public Iterator> iterator() {
//关键点，调用getIterator(ENTRIES)实现
return getIterator(ENTRIES);
}
public boolean add(Map.Entry o) {
return super.add(o);
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry entry = (Map.Entry)o;
Object key = entry.getKey();
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.equals(entry))
return true;
return false;
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry entry = (Map.Entry) o;
Object key = entry.getKey();
Entry[] tab = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry e = (Entry)tab[index];
for(Entry prev = null; e != null; prev = e, e = e.next) {
if (e.hash==hash && e.equals(entry)) {
modCount++;
if (prev != null)
prev.next = e.next;
else
tab[index] = e.next;
count--;
e.value = null;
return true;
}
}
return false;
}
public int size() {
return count;
}
public void clear() {
Hashtable.this.clear();
}
}
(3)values
public Collection values() {
if (values==null)
//同步的
values = Collections.synchronizedCollection(new ValueCollection(),
this);
return values;
}
private class ValueCollection extends AbstractCollection {
public Iterator iterator() {
//关键点，调用getIterator(VALUES)实现
return getIterator(VALUES);
}
public int size() {
return count;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
Hashtable.this.clear();
}
}
京公网安备 11010802041100号