1. Hashtable概述 Hashtable和HashMap解决Hash Collision的方法相同, 都使用Separate Chaining. 但Hashtable使用synchronized保证线程安全, 使得效率上插入删除效率上略低于HashMap
2. 重要参数 private transient Entry<?,?>[] table;private transient int count;private int threshold;private float loadFactor;private transient int modCount = 0 ;private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 ;
3. 初始化函数 3.1 无参数初始化函数 Hashtable的默认大小为11, 而HashMap的默认大小为16. 因为HashMap获得table的index操作为 hash_value & table.length - 1 . 这时就需要HashMap的长度始终保持在2n , 而Hashtable的长度则需要一个质数, 因为Hashtable获得table的index操作为 hash_value % table.length, 这就需要 hash_value 和 table.length 的GCD(Greatest Common Divisor, 最大公约数)为1, 这样才能保证index的分布平均, 证明如下:
index的求解公式: index = N % M (N为hash_value, M为table的长度, index为余数) 假设N = kn, M = km. k为N和M的GCD 所以index求解公式可转换为: kn = km × q + r 这么看来, r的取值范围为[0, M - 1] 但当公式两边除k后: n = m × q + r / k r的取值范围变为[0, k, 2k, 3k ... m*k], 缩小了k倍, 导致分布不平均. 所以简单的方法就是将M设置为质数, 保证N和M的GCD为1
public Hashtable () { this (11 , 0.75f ); }
3.2 带参数初始化函数 public Hashtable (int initialCapacity) { this (initialCapacity, 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 ); }
4. table的组成单元 - Entry 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; } @SuppressWarnings("unchecked") protected Object clone () { return new Entry <>(hash, key, value, (next == null ? null : (Entry<K,V>) next.clone()) ); } 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(); } }
5. table扩容函数 table长度的增长规律为 nn+1 = 2×nn + 1, 这样虽然不能保证nn 为质数, 但可保证nn 一直为odd number, 避免了nn 与hash value的公约数为2.
@SuppressWarnings("unchecked") protected void rehash () { int oldCapacity = table.length; Entry<?,?>[] oldMap = table; int newCapacity = (oldCapacity << 1 ) + 1 ; if (newCapacity - MAX_ARRAY_SIZE > 0 ) { if (oldCapacity == MAX_ARRAY_SIZE) 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; } } }
6. put() public synchronized V put (K key, V value) { if (value == null ) { throw new NullPointerException (); } 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(); tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF ) % tab.length; } @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) tab[index]; tab[index] = new Entry <>(hash, key, value, e); count++; }
7. get() 查找元素 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. remove() 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 ; }