java源码解读--hashtable

HashTable

HashTable类早期jdk对哈希表的实现，后续加入了HashMap等新的哈希表实现，目前HashTable已经被建议弃用。

HashTable和HashMap的区别有以下几点：

1. HashTable基于Dictionary抽象类实现了Map接口，而HashMap基于AbstractMap实现了Map接口
2. HashMap允许key和value为null，而HashTable中不允许
3. HashTable是线程安全的，HashMap不是，但Collections类中提供饿了synchronizedMap方法对HashMap进行线程安全封装

类定义

继承了Dictionary抽象类，实现了

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

成员变量

//底层存储数组
   private transient Entry<?,?>[] table;
//哈希表大小
   private transient int count;
//扩容阈值
   private int threshold;
//负载因子
   private float loadFactor;
//修改次数
   private transient int modCount = 0;

构造方法

//传入初始容量和负载因子
   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.75
   public Hashtable(int initialCapacity) {
       this(initialCapacity, 0.75f);
   }
//默认初始容量是11，负载因子是0.75
   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);
   }

put

方法被synchronized修饰，线程安全。
对value进行进行非空检查，若为空，报错

   public synchronized V put(K key, V value) {
//value为空报错
       if (value == null) {
           throw new NullPointerException();
       }

       Entry<?,?> tab[] = table;
//若key为空，这里会报空指针异常
       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;
   }

get

get方法也被synchronized修饰，线程安全

   public synchronized V get(Object key) {
       Entry<?,?> tab[] = table;
//key为null这里会报空指针异常
       int hash = key.hashCode();
//计算下标
       int index = (hash & 0x7FFFFFFF) % tab.length;
//查找key
       for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
           if ((e.hash == hash) && e.key.equals(key)) {
               return (V)e.value;
           }
       }
       return null;
   }

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;
}

扩容相关

   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;
       }

       // Creates the new entry.
       @SuppressWarnings("unchecked")
       Entry<K,V> e = (Entry<K,V>) tab[index];
       tab[index] = new Entry<>(hash, key, value, e);
       count++;
   }

   protected void rehash() {
       int oldCapacity = table.length;
       Entry<?,?>[] oldMap = table;

//扩容一倍+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 = (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;
           }
       }
   }