HashTable

Hashtable

一、对比HashMap

1.

项目	HashMap	Hashtable
默认容量	16	11
负载因子	0.75	0.75
null值	允许key/value为空	不允许key/value为空（put操作时报空指针异常）
扩容	length*2	length*2+1
安全	线程不安全	线程安全
extends	AbstractMap	Dictionary
容量	>=1	2^n

2.负载因子
过低，空间利用率低，频繁的扩容
过高，寻址时间增加，key value 的多了；

3.快速失败
modCount

在遍历过程中，如果 modCount > expectedCount
throw new ConcurrentModificationException

二、类定义

1.源码

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

三、属性

1.源码

    /**
     * The hash table data.
     */
    // Entry 的数组，Entry 
    private transient Entry[] table;

    /**
     * The total number of entries in the hash table.
     */
    // 容量
    private transient int count;

    /**
     * The table is rehashed when its size exceeds this threshold.  (The
     * value of this field is (int)(capacity * loadFactor).)
     *
     * @serial
     */
    // 临界值
    private int threshold;

    /**
     * The load factor for the hashtable.
     *
     * @serial
     */
    // 负载因子
    private float loadFactor;

    /**
     * The number of times this Hashtable has been structurally modified
     * Structural modifications are those that change the number of entries in
     * the Hashtable or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the Hashtable fail-fast.  (See ConcurrentModificationException).
     */
    // 修改次数
    private transient int modCount = 0;

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1421746759512286392L;

四、构造方法

1.

    // 初始化容量，负载因子
    public Hashtable(int initialCapacity, float loadFactor) {
        // 初始化容量不能小于0
	if (initialCapacity < 0)
	    throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        // 负载因子不能小于0且其是 float类型的数据
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
        // 初始化容量 为任意数字 ,HashMap 要求必须为 2 的 N 次幂
            initialCapacity = 1;
	this.loadFactor = loadFactor;
	table = new Entry[initialCapacity];
	threshold = (int)(initialCapacity * loadFactor);
    }

2.

    // 默认负载因子 0.75
    public Hashtable(int initialCapacity) {
	this(initialCapacity, 0.75f);
    }

    /**
     * Constructs a new, empty hashtable with a default initial capacity (11)
     * and load factor (0.75).
     */
    // 默认初始化容量 11 
    public Hashtable() {
	this(11, 0.75f);
    }

3.以存在的集合作为参数

    /**
     * Constructs a new hashtable with the same mappings as the given
     * Map.  The hashtable is created with an initial capacity sufficient to
     * hold the mappings in the given Map and a default load factor (0.75).
     *
     * @param t the map whose mappings are to be placed in this map.
     * @throws NullPointerException if the specified map is null.
     * @since   1.2
     */
    public Hashtable(Map<? extends K, ? extends V> t) {
        // 调用构造方法，初始化容量为  已有集合中的key-value 对数量的 2 倍
	this(Math.max(2*t.size(), 11), 0.75f);
	putAll(t);
    }

    // 遍历已有集合，调用put方法，synchronized 关键字，线程安全
    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());
    }

五、put()

1.源码

    
    public synchronized V put(K key, V value) {
	// Make sure the value is not null

        // value 不允许为空，空指针异常
	if (value == null) {
	    throw new NullPointerException();
	}

	// Makes sure the key is not already in the hashtable.
        // 赋值
	Entry tab[] = table;

        // key 不能为空，否则获取 hashcode 时报空指针异常
        // 一次hash，key本身的hash值
	int hash = key.hashCode();
        // 二次计算hash值，再与length 取余，确定存放在数组中的位置
	int index = (hash & 0x7FFFFFFF) % tab.length;
        // 取出index 位置的数据，遍历数组下的链表，判断此 key 是否已存在
        // 若已存在，则替换已存在的value值，并返回旧的value值
	for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
	    if ((e.hash == hash) && e.key.equals(key)) {
		V old = e.value;
		e.value = value;
		return old;
	    }
	}
        // 操作次数加 1 
	modCount++;
        // Hashtable 中 Entry 的数量 count 是否大于临界值
	if (count >= threshold) {
	    // Rehash the table if the threshold is exceeded
            // 扩容
	    rehash();

            tab = table;
            index = (hash & 0x7FFFFFFF) % tab.length;
	}

	// Creates the new entry.
        // 将 tab[index] 位置的链表赋值给 e
	Entry<K,V> e = tab[index];
        // 新增Entry ，将原有的链表放在新加入的Entry 的next 中
        // 即 新增的Entry 是放在链表的首位的
	tab[index] = new Entry<K,V>(hash, key, value, e);
	count++;
	return null;
    }

    // Entry 的构造方法
	protected Entry(int hash, K key, V value, Entry<K,V> next) {
	    this.hash = hash;
	    this.key = key;
	    this.value = value;
	    this.next = next;
	}
     
    // 扩容
    protected void rehash() {
        // 扩容前的容量
	int oldCapacity = table.length;
	Entry[] oldMap = table;
        // 扩容后的容量 length*2 + 1 
	int newCapacity = oldCapacity * 2 + 1;
	Entry[] newMap = new Entry[newCapacity];
        // 操作次数加1 
	modCount++;
	threshold = (int)(newCapacity * loadFactor);
	table = newMap;

        // 两层循环，外层遍历原数组的总长度，将旧数组依次放入新的数组中
	for (int i = oldCapacity ; i-- > 0 ;) {
            // 获取旧数据中下标 i 处的链表
	    for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
                // 获取链表当前位置的元素值
		Entry<K,V> e = old;
                // 指针下移
		old = old.next;
                // 计算存储位置
		int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                // 当前元素指向新的数组中 index 下标位置
		e.next = newMap[index];
                // 新数组的index 位置指向 e 
		newMap[index] = e;
	    }
            // 遍历的结果是将链表中的元素倒置放入新的数组中
	}
    }
    

六、remove()
1.源码

    public synchronized V remove(Object key) {
	Entry tab[] = table;
	int hash = key.hashCode();
        // 定位存储位置
	int index = (hash & 0x7FFFFFFF) % tab.length;
	for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
	    if ((e.hash == hash) && e.key.equals(key)) {
		modCount++;
              // 若链表中的元素数量 > 1 ，则将前一个Entry.next 指向 当前元素的next
		if (prev != null) {
		    prev.next = e.next;
		} else {
                    // 遍历条件
                    // Entry<K,V> e = tab[index], prev = null
                    // 下一次循环时，进行赋值 prev = e ；若 prev == null 
                    // 说明链表中的第一个Entry 即为目标
		    tab[index] = e.next;
		}
		count--; // count表示存放的 Entry的数量
		V oldValue = e.value;
		e.value = null;
		return oldValue;
	    }
	}

七、get()

1.源码

    public synchronized V get(Object key) {
	Entry tab[] = table;
        // key 不能为 null，此处报空指针
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % tab.length;
	for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
	    if ((e.hash == hash) && e.key.equals(key)) {
		return e.value;
	    }
	}
	return null;
    }