HashTable介绍
先来看看HashMap和HashTable有哪些区别
- 关于null，HashMap运行key和value都可以为null，而HashTable不允许key或者value为null的键值对
当HashMap遇到null为key时，回调用putForNullKey方法来进行处理，当HashTable遇到null时，直接抛出异常 - 关于线程安全，Hashmap不是线程安全的，HashTable则是线程安全的，它的需要操作都是由synchronized修饰
- Hashtable与HashMap实现的接口一致，但Hashtable继承Dictionary，而HashMap继承自AbstractMap，即父类不同
- 默认初始容量不同，扩容大小不同。HashMap的hash数组file:///Users/starlin/Documents/Hexo/source/_posts/java集合框架/的默认大小是16，而且一定是2 的指数,增加方式old2；Hashtable中hash数组默认大小是11，增加的方式是old2+1
HashTable源码
HashTable定义
HashTable继承Dictionary类，实现Map接口。其中Dictionary类是任何可将键映射到相应值的类的抽象父类。每个键和每个值都是一个对象。在任何一个 Dictionary 对象中，每个键至多与一个值相关联。
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
HashTable中的属性
/**
* The hash table data.
*/
//为一个Entry[]数组类型，Entry代表了“拉链”的节点，每一个Entry代表了一个键值对，
//哈希表的"key-value键值对"都是存储在Entry数组中的
private transient Entry<?,?>[] table;
/**
* The total number of entries in the hash table.
*/
//HashTable的大小，注意这个大小并不是HashTable的容器大小，而是他所包含Entry键值对的数量。
private transient int count;
/**
* The table is rehashed when its size exceeds this threshold. (The
* value of this field is (int)(capacity * loadFactor).)
*/
//Hashtable的阈值，用于判断是否需要调整Hashtable的容量。threshold的值="容量*加载因子"。
private int threshold;
/**
* The load factor for the hashtable.
*/
//加载因子
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).
*/
//用来实现“fail-fast”机制的（也就是快速失败）。
//所谓快速失败就是在并发集合中，其进行迭代操作时，
//若有其他线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出
//ConcurrentModificationException异常，而不是等到迭代完成之后才告诉你已经出错了
private transient int modCount = 0;
HashTable中的构造函数
/**
* Constructs a new, empty hashtable with the specified initial capacity
* and default load factor (0.75).
*
* @param initialCapacity the initial capacity of the hashtable.
* @exception IllegalArgumentException if the initial capacity is less
* than zero.
*/
//用指定初始容量和默认的加载因子 (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，加载因子为0.75。
public Hashtable() {
this(11, 0.75f);
}
/**
* Constructs a new, empty hashtable with the specified initial
* capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hashtable.
* @param loadFactor the load factor of the hashtable.
* @exception IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive.
*/
//用指定初始容量和指定加载因子构造一个新的空哈希表。
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，获得大小为initialCapacity的table数组
table = new Entry<?,?>[initialCapacity];
//计算阀值
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
/**
* 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
*/
// 构造一个与给定的 Map 具有相同映射关系的新哈希表。
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
HashTable中的主要方法
put方法
/**
* Maps the specified <code>key</code> to the specified
* <code>value</code> in this hashtable. Neither the key nor the
* value can be <code>null</code>. <p>
*
* The value can be retrieved by calling the <code>get</code> method
* with a key that is equal to the original key.
*
* @param key the hashtable key
* @param value the value
* @return the previous value of the specified key in this hashtable,
* or <code>null</code> if it did not have one
* @exception NullPointerException if the key or value is
* <code>null</code>
* @see Object#equals(Object)
* @see #get(Object)
*/
//用了 synchronized修饰，线程安全
public synchronized V put(K key, V value) {
// Make sure the value is not null
//确保value不为null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
//确保key在table[]是不重复的
Entry<?,?> tab[] = table;
//计算key的hash值
int hash = key.hashCode();
//(hash & 0x7FFFFFFF)获取数组元素下标,先对hash值取正,然后取余
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;
}
接上面，看下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 exceeded
//在rehash里进行扩容处理
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++;
}
我们看下扩容方法rehash()，其源码如下：
/**
* Increases the capacity of and internally reorganizes this
* hashtable, in order to accommodate and access its entries more
* efficiently. This method is called automatically when the
* number of keys in the hashtable exceeds this hashtable's capacity
* and load factor.
*/
@SuppressWarnings("unchecked")
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
//新容量等于旧容量*2 + 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;
//将原来的元素拷贝到新的HashTable中
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;
}
}
}
get方法
和put方法相比，get方法简单的多，其源码如下：
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key.equals(k))},
* then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* @param key the key whose associated value is to be returned
* @return the value to which the specified key is mapped, or
* {@code null} if this map contains no mapping for the key
* @throws NullPointerException if the specified key is null
* @see #put(Object, Object)
*/
@SuppressWarnings("unchecked")
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;
}
总结
鉴于HashTable的历史遗留问题，现在已经很少用到的，即使我们在对线程安全有要求的场景中，也是通过使用ConcurrentHashMap来解决，而不是使用Hashtable。关于ConcurrentHashMap的使用会在并发章节中会详细介绍