祝大家新年快乐，虎年大吉；

• HashTable的继承体系
  
  Dictionary 是JDK1.0出的一个接口，Dictionary 类是任何类的抽象父类，例如 Hashtable，它将键映射到值。每个键和每个值都是一个对象。在任何一个 Dictionary 对象中，每个键最多与一个值相关联。给定一个字典和一个键，可以查找相关的元素。任何非空对象都可以用作键和值。通常，此类的实现应使用 equals 方法来确定两个键是否相同。感觉是Map(JDK 1.2)接口的前世，定义了一些简单的集合操作方法：

public abstract class Dictionary<K,V> {// 构造器public Dictionary() {}// 返回此字典中的条目数（不同的键）abstract public int size();// 测试此字典是否没有将键映射到值。isEmpty 方法的一般约定是，// 当且仅当此字典不包含条目   时，结果才为真。abstract public boolean isEmpty();// 返回此字典中键的枚举。 keys 方法的一般约定是返回一个 // Enumeration 对象，该对象将生成该字典包含条目的所有键。abstract public Enumeration<K> keys();// 返回此字典中值的枚举。 elements 方法的一般约定是返回一个 // Enumeration ，它将生成该字典中条目中包含的所有元素abstract public Enumeration<V> elements();// 返回此字典中键映射到的值。 isEmpty 方法的一般约定是，// 如果此字典包含指定键的条目，则返回关联的值；否则，返回 null。abstract public V get(Object key);// 将指定的键映射到此字典中的指定值。键和值都不能为空。如果// 此字典已包含指定键的条目，则在修改条目以包含新元素后，返// 回此字典中已存在的该键的值。如果此字典还没有指定键的条目，// 则为指定的键和值创建一个条目，并返回 null。可以通过使用与// 原始键相同的键调用 get 方法来检索该值。abstract public V put(K key, V value);// 从此字典中删除键（及其对应的值）。如果键不在此字典中，则此方法不执行任何操作。abstract public V remove(Object key);
}

• 成员变量

// 哈希表
private transient Entry<?,?>[] table;
// 哈希表 Entry结点数量
private transient int count;
// 哈希表扩容的阙值(容量 * 负载因子)
private int threshold;
// 负载因子，默认为0.75
private float loadFactor;
// 记录哈希表结构变化的次数
private transient int modCount = 0;
// 哈希表最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

• 构造器

 // 指定容量和负载因子// 初始化哈希表和下次扩容的阙值
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);}// 指定容量，使用默认的负载因子 0.75public Hashtable(int initialCapacity) {this(initialCapacity, 0.75f);}// 使用默认容量11和负载因子0.75public Hashtable() {this(11, 0.75f);}// jdk 1.2// 使用Map的信息初始化hashTable// 将Map中的结点添加到hashTablepublic Hashtable(Map<? extends K, ? extends V> t) {this(Math.max(2*t.size(), 11), 0.75f);putAll(t);}

• 重要方法

// 哈希表扩容，重新计算哈希值，分配哈希散列
protected void rehash() {int oldCapacity = table.length;Entry<?,?>[] oldMap = table;// overflow-conscious codeint newCapacity = (oldCapacity << 1) + 1;if (newCapacity - MAX_ARRAY_SIZE > 0) {if (oldCapacity == MAX_ARRAY_SIZE)// Keep running with MAX_ARRAY_SIZE bucketsreturn;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;}}}

• 常用方法（方法都是同步的，使用synchronized修饰）

  // 获取当前哈希表结点数量public synchronized int size() {return count;}// 判断当前哈希表是否为空public synchronized boolean isEmpty() {return count == 0;}  // 判断哈希表中是否包含指定valuepublic 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;}// 判断哈希表中是否包含指定valuepublic boolean containsValue(Object value) {return contains(value);}// 判断哈希表中是否包含指定keypublic 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获取valuepublic 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;}// 向哈希表中添加public synchronized V put(K key, V value) {// value不能为空if (value == null) {throw new NullPointerException();}// 哈希表Entry<?,?> tab[] = table;// 计算key的内存地址hashCodeint hash = key.hashCode();// 使用哈希算法计算哈希值(除留余数法)int index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")// 获取当前哈希值对应位置的EntryEntry<K,V> entry = (Entry<K,V>)tab[index];// 不为空则进行value的替换并返回旧的valuefor(; entry != null ; entry = entry.next) {if ((entry.hash == hash) && entry.key.equals(key)) {V old = entry.value;entry.value = value;return old;}}// entry为空添加新的entryaddEntry(hash, key, value, index);return null;}// 添加新的entry结点private void addEntry(int hash, K key, V value, int index) {// 操作数加1modCount++;Entry<?,?> tab[] = table;// 判断当前哈希表中的entry结点数是否大于哈希表扩容阙值if (count >= threshold) {// 扩容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++;}// 移除哈希表中key对应的结点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;}// 添加Map到HashTable中public synchronized void putAll(Map<? extends K, ? extends V> t) {for (Map.Entry<? extends K, ? extends V> e : t.entrySet())put(e.getKey(), e.getValue());}// 清除哈希表中所有的结点public synchronized void clear() {Entry<?,?> tab[] = table;modCount++;for (int index = tab.length; --index >= 0; )tab[index] = null;count = 0;}// 获取哈希表中所有的keypublic synchronized Enumeration<K> keys() {return this.<K>getEnumeration(KEYS);}  // 获取哈希表中所有的valuepublic synchronized Enumeration<V> elements() {return this.<V>getEnumeration(VALUES);}  // 根据type获取相应的枚举器private <T> Enumeration<T> getEnumeration(int type) {if (count == 0) {return Collections.emptyEnumeration();} else {return new Enumerator<>(type, false);}}

• 静态内部类Entry

 private static class Entry<K,V> implements Map.Entry<K,V> {// 哈希值final int hash;// keyfinal K key;// valueV 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;}@SuppressWarnings("unchecked")protected Object clone() {return new Entry<>(hash, key, value,(next==null ? null : (Entry<K,V>) next.clone()));}// 返回keypublic K getKey() {return key;}// 返回valuepublic V getValue() {return value;}// 设置valuepublic 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();}}

• 枚举器(个人感觉有点类似于Iterator(jdk1.2))

// jdk 1.0
public interface Enumeration<E> {// 测试此枚举是否包含更多元素。返回： 当且仅当此枚举// 对象包含至少一个要提供的元素时，才返回 true；否则为假boolean hasMoreElements();// 如果此枚举对象至少还有一个要提供的元素，则返回此枚举的下一个元素E nextElement();
}// 在hashtable中实现的内部类Enumerator// 用于获取哈希表中的key或者value时指定一个类型// 返回相应的枚举器private static final int KEYS = 0;private static final int VALUES = 1;private static final int ENTRIES = 2;private class Enumerator<T> implements Enumeration<T>, Iterator<T> {Entry<?,?>[] table = Hashtable.this.table;int index = table.length;Entry<?,?> entry;Entry<?,?> lastReturned;int type;/*** 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 methodspublic 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<K,V> e = (Entry<K,V>)tab[index];for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {if (e == lastReturned) {modCount++;expectedModCount++;if (prev == null)tab[index] = e.next;elseprev.next = e.next;count--;lastReturned = null;return;}}throw new ConcurrentModificationException();}}}