既然聊到了HashMap,那么HashTable、ConcurrentHashMap等这都是绕不开的话题。做为ConcurrentHashMap在并发场景下高效性能的一个反例,HashTable究竟是怎么实现的呢,本章将对HashTable的源码进行分析。
HashTable与HashMap不太一样,由于HashTable产生得比较早,而在java升级的过程中,其功能逐渐被ConcurrentHashMap取代,因此HashTable逐渐显得有些过时。其继承了一个过时的抽象类Dictionary。在java后续发展的过程中,Dictionary的作用逐渐被Map取代了。虽然HashTable在jdk1.2之后也实现了map接口,但是可以看到在1.7、1.8中除了保持原状之外逐渐没有更新。 其类结构如下:
我们可以看到,继承了Dictionary抽象类,另外实现了Map、Cloneable、Serializable接口。
/**
* This class implements a hash table, which maps keys to values. Any
* non-<code>null</code> object can be used as a key or as a value. <p>
*
* To successfully store and retrieve objects from a hashtable, the
* objects used as keys must implement the <code>hashCode</code>
* method and the <code>equals</code> method. <p>
*
* An instance of <code>Hashtable</code> has two parameters that affect its
* performance: <i>initial capacity</i> and <i>load factor</i>. The
* <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
* <i>initial capacity</i> is simply the capacity at the time the hash table
* is created. Note that the hash table is <i>open</i>: in the case of a "hash
* collision", a single bucket stores multiple entries, which must be searched
* sequentially. The <i>load factor</i> is a measure of how full the hash
* table is allowed to get before its capacity is automatically increased.
* The initial capacity and load factor parameters are merely hints to
* the implementation. The exact details as to when and whether the rehash
* method is invoked are implementation-dependent.<p>
*
* Generally, the default load factor (.75) offers a good tradeoff between
* time and space costs. Higher values decrease the space overhead but
* increase the time cost to look up an entry (which is reflected in most
* <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p>
*
* The initial capacity controls a tradeoff between wasted space and the
* need for <code>rehash</code> operations, which are time-consuming.
* No <code>rehash</code> operations will <i>ever</i> occur if the initial
* capacity is greater than the maximum number of entries the
* <tt>Hashtable</tt> will contain divided by its load factor. However,
* setting the initial capacity too high can waste space.<p>
*
* If many entries are to be made into a <code>Hashtable</code>,
* creating it with a sufficiently large capacity may allow the
* entries to be inserted more efficiently than letting it perform
* automatic rehashing as needed to grow the table. <p>
*
* This example creates a hashtable of numbers. It uses the names of
* the numbers as keys:
* <pre> {@code
* Hashtable<String, Integer> numbers
* = new Hashtable<String, Integer>();
* numbers.put("one", 1);
* numbers.put("two", 2);
* numbers.put("three", 3);}</pre>
*
* <p>To retrieve a number, use the following code:
* <pre> {@code
* Integer n = numbers.get("two");
* if (n != null) {
* System.out.println("two = " + n);
* }}</pre>
*
* <p>The iterators returned by the <tt>iterator</tt> method of the collections
* returned by all of this class's "collection view methods" are
* <em>fail-fast</em>: if the Hashtable is structurally modified at any time
* after the iterator is created, in any way except through the iterator's own
* <tt>remove</tt> method, the iterator will throw a {@link
* ConcurrentModificationException}. Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than risking
* arbitrary, non-deterministic behavior at an undetermined time in the future.
* The Enumerations returned by Hashtable's keys and elements methods are
* <em>not</em> fail-fast.
*
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <i>the fail-fast behavior of iterators
* should be used only to detect bugs.</i>
*
* <p>As of the Java 2 platform v1.2, this class was retrofitted to
* implement the {@link Map} interface, making it a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
*
* Java Collections Framework</a>. Unlike the new collection
* implementations, {@code Hashtable} is synchronized. If a
* thread-safe implementation is not needed, it is recommended to use
* {@link HashMap} in place of {@code Hashtable}. If a thread-safe
* highly-concurrent implementation is desired, then it is recommended
* to use {@link java.util.concurrent.ConcurrentHashMap} in place of
* {@code Hashtable}.
*
* @author Arthur van Hoff
* @author Josh Bloch
* @author Neal Gafter
* @see Object#equals(java.lang.Object)
* @see Object#hashCode()
* @see Hashtable#rehash()
* @see Collection
* @see Map
* @see HashMap
* @see TreeMap
* @since JDK1.0
*/
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
}
在开头有大段的注释,在java中,尤其是源码中有大段注释的地方是特别需要我们注意的。上述部分其大意为: 这个类实现了一个hash表,它将key映射到值。任何非空的对象都可以做为key或者value使用。 要成功地从hash表中存储和检索对象,则做为key的对象必须实现hashCode方法和equals方法。 HashTable的一个示例有两个参数影响它的性能,初始容量,负载因子。容量capacity是哈希表中bucket的数量,而初始的容量则是在创建hash表的时候同时创建。需要注意的是,哈希表是开放状态的,在hash冲突的情况下,一个bucket存储了多个条目,那么必须按顺序对这些条目进行搜索。负载因子load factor 是一个度量哈希表在其容量自动增加之前可以达到的完整程度。初始容量和负载因子只是对实现的提示,有关何时及是否调用rehash方法确切的细节取决于实现。 通常情况下,负载因子默认为0.75,这是在时间和空间成本上的一个平衡。如果这个值太高固然会降低空间的开销,但是检索的时候会增加时间成本。这在大多数哈希表的操作中,表现在get和put方法上。 初始容量是空间浪费和rehash操作的折衷。rehash操作非常耗时。如果初始容量大于hashtable将包含的最大条目和负载因子之商,那么将不会有任何rehash操作。然而,这将造成空间浪费。 如果许多条目被创建到hashtable中,创建一个足够大的容量允许这些条目插入,比让这些条目插入之后触发rehash操作更有效率。 如下这个例子创建了一个数字的hash表,它使用名称做为数字的key。
Hashtable<String, Integer> numbers
= new Hashtable<String, Integer>();
numbers.put("one", 1);
numbers.put("two", 2);
numbers.put("three", 3);
检索一个号码,用如下代码:
Integer n = numbers.get("two");
if (n != null) {
System.out.println("two = " + n);
}
类的所有集合视图方法返回的集合的iterator方法返回的集合是符合fail-fast机制的。在hashTable被创建后的任何时候,以任何方式(除迭代器自己的remove方法之外)修改hashtable,迭代器将抛出ConcurrentModificationException异常。因此,在并发修改的情况下,迭代器会迅速的返回失败,而不是在将来某个不确定的时间,冒着任意的、不确定的行为风险。HashTable的keys和elements方法返回Enumerations类型不是fail-fast。 需要注意的是,迭代器的fail-fast行为不能得到保证,因为一般来说,在存在不同步的并发修改的时候,不可能做出任何硬件担保。Fail-fast迭代器尽最大努力抛出ConcurrentModificationException,因此,编写任何一个依赖于这个异常来确保正确性的程序是错误的,迭代器的fail-fast机制只用于检测错误。 在java1.2中,这个类实现了map接口,确保其是java集合框架的成员之一。 在java集合框架中,与其他集合不同的是HashTable是同步的,如果线程安全不是必须的,请使用HashMap来替换HashTable。如果需要一个线程安全的实现,推荐使用ConcurrentHashMap。 通过上述注释可以看除,实际上HashTable在java集合框架中,越来越尴尬,不需要并发的情况下直接使用HashMap效率会高很多。在并发场景下则推荐使用ConcurrentHashMap。
H与HashMap类似,HashTable内部也采用内部类来实现这些复杂的结构。
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next;
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
@SuppressWarnings("unchecked")
protected Object clone() {
return new Entry<>(hash, key, value,
(next==null ? null : (Entry<K,V>) next.clone()));
}
// Map.Entry Ops
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
if (value == null)
throw new NullPointerException();
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
(value==null ? e.getValue()==null : value.equals(e.getValue()));
}
public int hashCode() {
return hash ^ Objects.hashCode(value);
}
public String toString() {
return key.toString()+"="+value.toString();
}
}
这个内部类实现了Map.Entry接口。 内部核心的字段有,hash、key、value,另外还有一个next的指针指向下一个元素。也就是说,实际上hashtable在hash碰撞之后由单向链表组成。这实际上与HashMap中的Node节点一致。 需要注意的是 hashCode方法与HashMap中的实现不太一样: 如下是HashMap中Node的hashCode的方法。是将key和value的hashCode进行异或运算。
Objects.hashCode(key) ^ Objects.hashCode(value);
而在此处,则是Entry中的hash和value的hashcode进行异或运算。
return hash ^ Objects.hashCode(value);
这个代码的结果实际上没有区别,Hashtable中的hash实际上是key的hashcode:
hash = key.hashCode();
但是hashMap中的hash属性已经被修改了,需要用高位部分混淆。
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
也就是说hashMap和HashTable中元素的hash属性的计算是有区别的,这也是我们在面试过程中需要注意的。hashMap为什么要重写hash方法,实际上是因为hashmap计算bucket的方法不同。这个在所有Map都分析完之后进行统一总结。
1.3 成员变量 重要的一些成员变量如下:
/**
* The hash table data.
*/
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;
成员变量有transient修饰的Entry数组 table。以及哈希表元素的数量count。另外还有threshold和loadFactor两个控制变量。这个与HashMap不同的是,loadfactor并没有在类中定义一个常量。HashTable的这些初始化参数直接在构造函数中。 需要注意的是,HashMap以及HashTable相关存储元素的数组等属性都是transient修饰,在序列化的时候不会被序列化,而是类自己实现了序列化和反序列华的缺省方法。因为EffecitveJava一书中说过,这是因为在不同的虚拟机或者不同操作系统上,hashcode的算法可能会造成相同的值经过hash之后其hashcode不一致。这样就容易造成实际上反序列化之后的HashTable与之前的HashTable不同。
另外有个常量是我们需要注意的:
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
这里对为啥MAX_ARRAY_SIZE不是Integer.MAX_VALUE进行了解释。再某些jvm中,数组是需要一些头信息的,因此如果直接将int数组分配为Integer.MAX_VALUE,则会造成OOM。所以这里的长度是Integer.MAX_VALUE - 8;
学过HashMap之后再来看HashTable就非常简单了。其内部构成就是通过拉链法实现的单向链表。
这就是HashTable的组成。 实际上相对HashMap和LinkedHashMap要简单得多。
这是一个最基本的构造方法,判断initialCapacity和loadFactor是否合法。当initialCapacity为0的时候,会改为1。
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)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
在调用构造函数的时候,会创建这个table数组,这一点与HashMap也不同,HashMap的数组为了控制其大小为2的幂,是在resize的方法中才会创建。而HashTable没有这个限制。因此可以在构造函数中创建。
实际上是调用的3.1中的构造函数:
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
在这指定了loadFactor为0.75。
也是通过this调用前面的构造函数。
public Hashtable() {
this(11, 0.75f);
}
这里可以看到,HashTable的默认大小为11,负载因子为0.75。HashTable的bucket可以为任意大小。
同理,也会存在一个根据原有的Map产生一个新Map的构造方法。
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
判断大小,通过构造函数创建的HashTable默认为11。之后调用putAll方法。
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());
}
putAll方法是一个同步方法。其没部通过遍历,之后对put方法进行调用。
在HashTable中,还有一些非常重要的方法。
这个方法是Hashtable的核心方法,扩容就是用此方法进行实现,我们来看看其源码:
/**
* 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() {
//原始的table容量及table
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
//注意其扩容的方式,左移1位+1。
int newCapacity = (oldCapacity << 1) + 1;
//如果其容量大于最大值
if (newCapacity - MAX_ARRAY_SIZE > 0) {
//如果旧的容量就为最大值,那么说明没必要扩容,直接return
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
//反之扩容到最大值
newCapacity = MAX_ARRAY_SIZE;
}
//创建新的数组
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
//增加modCount
modCount++;
//重新计算门槛阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
//遍历数组
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;
}
}
}
我们可以看到,rehash方法,其扩容的方式与HashMap中resize的方式不一样。
newCapacity = (oldCapacity << 1) + 1;
另外计算bucket槽位的时候:
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
先采用& 0x7FFFFFFF。这是因为 0x7FFFFFFF为2^32-1。这样一来,由于采用的是&运算,这样一来任何大于0x7FFFFFFF都将只保留0x7FFFFFFF覆盖的低位部分。高位部分会舍去。由于Hashtable的长度不一定满足2的幂,因此其计算槽位不能用位运算。这里直接用%。显然其效率要低于Hashmap中的位运算操作。 由于在Hashtable中,rehash并没提供给外部访问,而调用rehash的位置只有addEntry方法。因此这个方法没有加同步关键字。 另外HashTable并没提供缩容机制,也不存在HashMap中红黑树和链表互相转换的问题。因此其逻辑要简单得多。
这是HashTable中添加元素的底层方法:
private void addEntry(int hash, K key, V value, int index) {
//修改modecount
modCount++;
//tab指向table
Entry<?,?> tab[] = table;
//判断是否需要扩容
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
//扩容
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++;
}
将元素添加到Hashtable的时候,最近增加的元素会放到table指针上,而将之前的元素前移。
这是同步方法,将元素put到HashTable中
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;
int hash = key.hashCode();
//计算索引
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
//遍历 判断其key是否已经存在于链表中,如果存在直接返回
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);
添加成功返回null否则返回之前的old元素
return null;
}
删除hashTable中的元素,这个方法也是同步方法:
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
//计算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) {
//用hash和key是否都相等来判断是否存在于HashTable中
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
if (prev != null) {
//改变链表
prev.next = e.next;
} else {
//如果在链表末尾 tab中,则改变tab指针
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null;
//返回被删除的value
return oldValue;
}
}
//如果不存在则返回null
return null;
}
获取元素,此方法也是同步的。
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
//计算index
int index = (hash & 0x7FFFFFFF) % tab.length;
//遍历
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
//如果hash相同且key相等说明即为所查找的元素
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
清空HashTable,这个方法也是同步的。
public synchronized void clear() {
Entry<?,?> tab[] = table;
modCount++;
//遍历table,将其都置为null
for (int index = tab.length; --index >= 0; )
tab[index] = null;
count = 0;
}
需要注意的是,Hashtable提供的clone是一个浅拷贝。
/**
* Creates a shallow copy of this hashtable. All the structure of the
* hashtable itself is copied, but the keys and values are not cloned.
* This is a relatively expensive operation.
*
* @return a clone of the hashtable
*/
public synchronized Object clone() {
try {
//clone对象
Hashtable<?,?> t = (Hashtable<?,?>)super.clone();
//创建数组
t.table = new Entry<?,?>[table.length];
//如果某个索引不为空则clone
for (int i = table.length ; i-- > 0 ; ) {
t.table[i] = (table[i] != null)
? (Entry<?,?>) table[i].clone() : null;
}
//其他全部置空
t.keySet = null;
t.entrySet = null;
t.values = null;
t.modCount = 0;
return t;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
这个clone方法是一个浅拷贝方法,其数组会新建一个数据,但是其中的Entry都是指向之前的对象。而且Keyset和entrySet以及values都为空。这也是hashtable面试的过程中需要注意的。
HashTable提供了两个replace方法,分别是当key和Value都相等的情况下replace和只需要根据key来确定replace。
@Override
public synchronized boolean replace(K key, V oldValue, V newValue) {
Objects.requireNonNull(oldValue);
Objects.requireNonNull(newValue);
Entry<?,?> tab[] = table;
int hash = key.hashCode();
//计算index
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
//for循环遍历
for (; e != null; e = e.next) {
//判断hash和key是否相等
if ((e.hash == hash) && e.key.equals(key)) {
//判断value是否相等
if (e.value.equals(oldValue)) {
//如果都相等则替换
e.value = newValue;
return true;
} else {
return false;
}
}
}
return false;
}
另外一个replace方法:
public synchronized V replace(K key, V value) {
Objects.requireNonNull(value);
Entry<?,?> tab[] = table;
int hash = key.hashCode();
//计算index
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
//循环遍历
for (; e != null; e = e.next) {
//如果hash和key相等则替换
if ((e.hash == hash) && e.key.equals(key)) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
return null;
}
与HashMap等类似,Hashtable也提供了视图类KeySet、Values、EntrySet的支持。其实现如下:
/**
* Each of these fields are initialized to contain an instance of the
* appropriate view the first time this view is requested. The views are
* stateless, so there's no reason to create more than one of each.
*/
private transient volatile Set<K> keySet;
private transient volatile Set<Map.Entry<K,V>> entrySet;
private transient volatile Collection<V> values;
由于涉及在并发情况下使用,因此这三个变量都是volatile修饰的,具有可见性。
public Set<K> keySet() {
if (keySet == null)
keySet = Collections.synchronizedSet(new KeySet(), this);
return keySet;
}
private class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return getIterator(KEYS);
}
public int size() {
return count;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return Hashtable.this.remove(o) != null;
}
public void clear() {
Hashtable.this.clear();
}
}
Keyset实际上就是要给视图类,但是此处采用 Collections.synchronizedSet进行同步保证。 其他Values和EntrySet与此原理类似。就不一一列举。
本文对Hashtale源码进行了分析,虽然Hashtable类已经在现实情况中很少使用,但是我们仍然需要注意其与HashMap的区别。这也是面试的时候的高频面试题,HashMap与HashTable主要区别体现在:
以上是我对HashTable和HashMap源代码阅读之后的比较,如有不足,烦请补充。