【JDK源码】HashTable

先去了解HashMap效果更佳【JDK源码】HashMap（一）

继承体系

Hashtable 的函数都是同步的，这意味着它是线程安全的，能用于多线程环境中。它的key、value都不可以为null。

Hashtable中的映射不是有序的。

Hashtable采用"拉链法"实现哈希表。

基本属性

/*** 哈希表数据*/
private transient Entry<?,?>[] table;/*** 哈希表中元素的总数*/
private transient int count;/*** Hashtable的阈值，用于判断是否需要调整Hashtable的容量。threshold的值="容量*加载因子"*/
private int threshold;/*** 加载因子*/
private float loadFactor;/*** Hashtable被改变的次数，用于fail-fast机制的实现* 所谓快速失败就是在并发集合中，其进行迭代操作时，若有其他线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出ConcurrentModificationException异常，而不是等到迭代完成之后才告诉你（你已经出错了）*/
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);//如果初始容量为0则让其等于1if (initialCapacity==0)initialCapacity = 1;//初始化加载因子this.loadFactor = loadFactor;//创建一个Entry类型的数组长度为参数initialCapacity的值。table = new Entry<?,?>[initialCapacity];//计算阀值在初始容量乘以加载因子的值和后者（整数最大32位）之间取最小值。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);
}/*** 根据传入的Map集合直接初始化HashTable,容量为传入Map集合容量大小*2与11进行比较，取值较大者*/
public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75f);putAll(t);
}

在初始化阶段，Hashtable就已经为table属性开辟了内存空间，这和HashMap中不同，HashMap是在第一次调用put方法时才为table开辟内存的。还有就是默认初始容量不同，一个16一个11。

put()

public synchronized V put(K key, V value) {
    // Make sure the value is not null// 发现值不能等于null 与hashmap不同if (value == null) {
    throw new NullPointerException();}// Makes sure the key is not already in the hashtable.//确保该键不在哈希表中//迭代table，将其赋值给局部变量tabEntry<?,?> tab[] = table;//计算key的hash值，确认在table[]中的索引位置//这里如果key为null调用Object的hashCode方法就会报空指针异常，所以key也不能为nullint hash = key.hashCode();// 计算索引位置，这里与hashmap不同/*** 0x7FFFFFFF: 16进制表示的整型,是整型里面的最大值* 0x7FFFFFFF: 0111 1111 1111 1111 1111 1111 1111 1111：除符号位外的所有1* (hash & 0x7FFFFFFF) 将产生正整数* (hash & 0x7FFFFFFF) % tab.length 将在标签长度的范围内* 所以hashtable采用奇数导致的hash冲突会比较少，采用偶数会导致的冲突会增多* 4%2 = 6%2 = 8%2 ……*/int index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")Entry<K,V> entry = (Entry<K,V>)tab[index];//遍历对应index位置的链表for(; entry != null ; entry = entry.next) {
    //如果已经有了相同key的元素 ，则更新数据，返回原来的元素if ((entry.hash == hash) && entry.key.equals(key)) {
    V old = entry.value;entry.value = value;return old;}}// 增加新Entry元素addEntry(hash, key, value, index);return null;
}

• 我们可以看到put方法加了synchronized维护，所以这个方法是线程安全的
• 从计算hash就可以看出为什么采用11奇数作为初始容量
• put方法不允许key和value为null值，如果发现是null，则直接抛出异常
• addEntry方法

addEntry()

private void addEntry(int hash, K key, V value, int index) {
    modCount++;Entry<?,?> tab[] = table;//元素个数大于阈值则将扩容if (count >= threshold) {
    // Rehash the table if the threshold is exceededrehash();//扩容后也找到index，也就是链表对应的索引tab = table;hash = key.hashCode();index = (hash & 0x7FFFFFFF) % tab.length;}// Creates the new entry.@SuppressWarnings("unchecked")//拿到该index下的链表的头结点Entry<K,V> e = (Entry<K,V>) tab[index];//然后采用头插法将元素插入,这里和hashmap 1.8不同tab[index] = new Entry<>(hash, key, value, e);count++;
}

• 是否扩容
• 插入头部，和hashmap1.8不同

rehash()

protected void rehash() {
    //原来的容量(旧的数组的长度)int oldCapacity = table.length;//将原来的table保存起来Entry<?,?>[] oldMap = table;// overflow-conscious code//新容量 原来两倍加一 保证奇数int 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;// 把旧哈希表的键值对重新哈希到新哈希表中去（双重循环，耗时！）// 这个方法类似于HashMap扩容后，将旧数组数据赋给新数组，// 在HashMap中会将其旧数组每个桶位进一步‘打散'，放置到新数组对应的桶位上（有一个重新计算桶位的过程）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;//将每条链表的每个结点打乱重新hash 重新组建找到自己的位置，还是头结点插入int index = (e.hash & 0x7FFFFFFF) % newCapacity;e.next = (Entry<K,V>)newMap[index];newMap[index] = e;}}
}

• 扩容2倍加1
• 更新阈值，更新table
• 遍历旧表中的节点，计算在新表中的index，插入到对应位置链表的头部

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

• synchronized,保证线程安全

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];//找到删除结点的前结点prevfor(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
    if ((e.hash == hash) && e.key.equals(key)) {
    modCount++;//e的前结点不为空if (prev != null) {
    //把e删除了 prev.next = e.next;//e是头结点} else {
    //把e的下一个节点左头结点tab[index] = e.next;}count--;V oldValue = e.value;//交给gc处理ee.value = null;//返回旧的值return oldValue;}}return null;
}

• synchronized,保证线程安全

• 存在就删除并返回删除的值，不存在返回null

Hashtable 和 HashMap的区别

1. HashMap可以允许存在一个为null的key和任意个为null的value，但是HashTable中的key和value都不允许为null

	// HashTable
if (value == null) {
    throw new NullPointerException();
}int hash = key.hashCode();
============================// HashMap
static final int hash(Object key) {
    int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

2. Hashtable的方法是同步的，而HashMap的方法不是。所以有人一般都建议如果是涉及到多线程同步时采用HashTable，没有涉及就采用HashMap。
3. 哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值

	// HashTable
int hash = key.hashCode();
========================// HashMap
int  hash =  hash(key)
static final int hash(Object key) {
    int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

4. Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。这与hash冲突有关