上几篇笔记研究了HashMap和LinkedHashMap，此笔记研究Hashtable。
一：概述
先来看下Hashtable的类信息
//跟HashMap相比，继承的类不一样，实现具
//的接口倒是一样的，说明他们具有类似的功能
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
/**
* The hash table data.
* hash数组，跟HashMap一样
*/
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;
/**
* 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);
//如果初始容量是0的话，那么置成1
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
//创建指定长度的Entry数组
table = new Entry<?,?>[initialCapacity];
//计算阈值
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
/**
* 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.
*
* 带有容量的构造函数
*/
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;HashMap的容量是16，加载因子也是0.75
*/
public Hashtable() {
this(11, 0.75f);
}
/**
* 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创建一个Hashtable，容量是原来容量的两倍和11的最大值
*/
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
}
Hashtable的类信息还是比较简单的，下面看下他存入元素的方法put(K key, V value):
/**
* 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)
*/
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.
//拿到Hashtable的数组
Entry<?,?> tab[] = table;
//计算key的hash值
int hash = key.hashCode();
//桶的索引是用key的hash值和0x7FFFFFFF做与运算，最后对数组长度取余
int index = (hash & 0x7FFFFFFF) % tab.length;
//拿到指定桶上的Entry对象
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
//Hashtable上只有链表，没有红黑树，所以遍历链表
for(; entry != null ; entry = entry.next) {
//如果遍历到的Entry的hash和目标hash一样，而且两个的key
//也相等，那么只需要更新value即可，同时将老的value返回回去
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
//若干Hashtable里面没有key与目标key一样的Entry，那么新插入一个
addEntry(hash, key, value, index);
//如果是插入全新的Entry的话，就返回空
return null;
}
put方法就是先查找，找到了就更新；没找到就插入一个全新的Entry，首先可以看到，put这个方法加了synchronized，说明这个方法是线程安全的，实际上Hashtable的大部分方法都是线程安全的，这是跟HashMap的一个重要区别；然后在put里面对value进行了空判断，也就是说，HashTable是不允许存入空的键值对的，这也是和HashMap的一个在重要区别；下面分析插入的方法addEntry：
private void addEntry(int hash, K key, V value, int index) {
//modCount自增，注意到没，更新操作是不自增的
modCount++;
Entry<?,?> tab[] = table;
//如果当前元素数量超出阈值
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
//重新hash，也就是扩容
rehash();
tab = table;
//计算key的hash值
hash = key.hashCode();
//计算key的索引
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
//将桶上原来的Entry赋值给e
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
//根据原来的Entry、hash、key和value
//创建一个新的Entry放到指定的桶上
tab[index] = new Entry<>(hash, key, value, e);
//数量自增
count++;
}
addEntry方法的核心是rehash()，这个方法看起来是重新计算hash，事实上他确实也计算了，这个方法的核心作用还是扩容：
/**
* 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;
//将老数组赋值给oldMap
Entry<?,?>[] oldMap = table;
// overflow-conscious code
//新数组的长度是老数组长度的2n + 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++;
//计算新的阈值，在新容量*加载因子和最大值 + 1之间取最小值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
//将新数组赋值给table
table = newMap;
//双重遍历老数组，第一重遍历是遍历桶上的各个Entry，将老数组的节点移到新数组
for (int i = oldCapacity ; i-- > 0 ;) {
//第二重遍历是遍历桶上Entry后面接的链表
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
//将old赋值给e，e代表遍历到的节点
Entry<K,V> e = old;
//old指向他的后继节点，下次遍历就遍历到后继节点了
old = old.next;
//重新计算Entery的索引，因为newCapacity变了，所以index也会变
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
//把新桶上已存在链表节点作为当前节点的后继节点
e.next = (Entry<K,V>)newMap[index];
//遍历到的节点放到新数组的桶上，发现没？这是链表的头结点
newMap[index] = e;
}
}
}
理解了HashMap的扩容后，再理解Hashtable的扩容就简单多了；需要注意的是，老数组上的链表，经过扩容后可能会被拆散；那些没被拆散的节点，也就是重新落入同一个桶的节点，他们的前驱和后继的关系反过来了，原来是前驱节点的，在新数组里面就是后继节点了，反之亦然。既然有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;
//计算key的hash
int hash = key.hashCode();
//根据hash值计算桶的索引
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;
}
get方法超简单，不多说。增、改、查都分析了，下面分析删的动作：
/**
* Removes the key (and its corresponding value) from this
* hashtable. This method does nothing if the key is not in the hashtable.
*
* @param key the key that needs to be removed
* @return the value to which the key had been mapped in this hashtable,
* or <code>null</code> if the key did not have a mapping
* @throws NullPointerException if the key is <code>null</code>
*/
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table;
//计算key的hash
int hash = key.hashCode();
//根据hash计算桶的索引index
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) {
//如果key的hash相等，而且key本身也相等，说明就是要删掉这个节点
if ((e.hash == hash) && e.key.equals(key)) {
//自增
modCount++;
//如果prev不为空，说明要删除的不是头结点
if (prev != null) {
//那么将目标节点的头结点指向目标节点的后继节点
prev.next = e.next;
} else {
//如果删除的就是头结点，那么将原来头结点的后继节点指定为头结点
tab[index] = e.next;
}
//元素总数 - 1
count--;
//取出要删除的节点的value
V oldValue = e.value;
//将e的value置空(需要吗？)
e.value = null;
//返回删除节点的value
return oldValue;
}
}
return null;
}
可以看到，remove方法也是非常简单的。
Hashtable就讲这么多吧，其他的方法都差不多，基本上能都是通过hash计算桶的索引，然后操作链表，非常简单；我个人觉得Hashtable是HashMap的简化版，就是把HashMap中的红黑树去掉，同时在公开的方法增加了同步操作；只要理解了HashMap，理解Hashtable就水到渠成了，不管是理解哪个，都要理解链表和树。
网友评论