1、本文主要内容
- Hashtable简介
- Hashtable源码剖析
- 总结
今天来总结下 Hashtable，Hashtable是一个线程安全的容器，它实现了Map接口，使用键值对形式来保存元素。
2、Hashtable简介
Hashtable与HashMap类似，都是以键值对形式存储元素，但它与HashMap最大的差别即是，Hashtable线程安全，而HashMap非线程安全。而且它们各自的父类也不一样，但都实现了Map接口
另外Hashtable求元素索引的方式与HashMap稍有不同，或者可以说方法较为粗糙。
3、Hashtable源码剖析
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
/**
* The hash table data.
*/
//存储数据所用的数组，存储的是entry对象，键值对
private transient Entry[] table;
/**
* The total number of entries in the hash table.
*/
//存储数据的个数，size方法的返回值
private transient int count;
/**
* The table is rehashed when its size exceeds this threshold. (The
* value of this field is (int)(capacity * loadFactor).)
*
* @serial
*/
//超过这个数就重新hash，要扩容
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).
*/
//Hashtable结构性改变的次数
private transient int modCount = 0;
/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1421746759512286392L;
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)(initialCapacity * loadFactor);
}
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
//注意Hashtable默认的数组长度是11
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);
}
//返回当前已存储元素的个数，注意加的同步锁，同步锁为当前的Hashtable对象
public synchronized int size() {
return count;
}
//查看当前Hashtable是否为空，有没有存储元素
public synchronized boolean isEmpty() {
return count == 0;
}
//查看是否包含某个值，同样是同步
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
Entry tab[] = table;
//因为Hashtable和HashMap一样，都是使用数组链表的形式来存储数据，如果某个key的hash值一样
//则数组的索引处将有一个链表，所以需要进行两重循环
for (int i = tab.length ; i-- > 0 ;) {
for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
public boolean containsValue(Object value) {
return contains(value);
}
//查看是否包含某个key，线程安全
public synchronized boolean containsKey(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
//注意它和Hashmap不一样的地方，直接拿hash值与 0x7FFFFFFF 相与，
//意味着hash值只丢弃第1位，其它位全部保留，再将值对tab.length求余，得到索引位置
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 true;
}
}
return false;
}
//获取某个key下的值
public synchronized V get(Object key) {
Entry tab[] = table;
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;
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//重新hash
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];
//改变次数加1，同时重新计算threshold值，并为table赋新值
modCount++;
threshold = (int)(newCapacity * loadFactor);
table = newMap;
//两重循环遍历旧数组中的所有元素，重新计算索引值，因为数组的长度变化了，索引值也会不一样
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
//重新计算的索引值
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
//构成链表，新的元素总是在链表的表头，它的next指向旧的链表头
e.next = newMap[index];
newMap[index] = e;
}
}
}
//线程安全地保存新元素
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = key.hashCode();
//计算新元素的索引值
int index = (hash & 0x7FFFFFFF) % tab.length;
//根据已经得到的index值，查看此处可能存在的链表，如果有hash值和key完全一样的元素，则直接替换成新元素
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;
}
}
modCount++;
//如果count值大于threshold，则数组扩容重新hash
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
//如果不是对已经元素的更新值，则将新元素放在链表头位置，并且将它的next指向之前的老的链表头节点
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}
//线程安全删除对象
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)) {
//如果hash值相等并且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;
}
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());
}
//清空所有数组
public synchronized void clear() {
Entry tab[] = table;
modCount++;
for (int index = tab.length; --index >= 0; )
tab[index] = null;
count = 0;
}
}
4、总结
其实源码非常简单，目前为止已经分析了多个java容器，只要一查源码，发现其并不神秘，只需要我们都看源码，则它背后的原理就都清楚了。
后续本博还会继续总结set接口，以及各种阻塞队列，分析阻塞的原理等等
