前面介绍了HashMap,ConcurrentHashMap,我们再来介绍Hashtable的实现原理,也可以先看笔者写的如下文章学习学习。
1、Java集合-类的继承组合关系
2、Java集合-HashMap源码实现深入解析
3、Java集合-LinkedHashMap工作原理
4、Java集合-ConcurrentHashMap工作原理和实现JDK7
5、Java集合-ConcurrentHashMap工作原理和实现JDK8
6、ConcurrentHashMap与红黑树实现分析Java8
Hashtable与HashMap的区别
Hashtable与HashMap都是用来存储key-value类型数据的,两者有如下区别:
1、Hashtable不允许null key和null value,HashMap允许。
2、Hashtable是线程安全的,HashMap不是线程安全的。
3、HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。
4、Hashtable继承自Dictionary,HashMap继承自AbstractMap。
5、两者都实现了Map接口。
Hashtable的继承关系
从继承图来看,Hashtable继承自Dictionary,这点与HashMap不同。同时从所拥有的属性也能看出Hashtable的数据结构。
Hashtable的继承关系UML类图public class Hashtable<K,V> extends Dictionary<K,V> implements
Map<K,V>, Cloneable, java.io.Serializable {
// 省略
}
Hashtable的数据结构
在Java6中HashMap中采用table数组+链表的方式来实现(Java8中采用数组+链表+红黑树)。Hashtable的数据结构也采用这种结构。
我们先看一段Java代码:
Hashtable<String, String> hashtable = new Hashtable<String, String>();
hashtable.put("语文", "1");
hashtable.put("数学", "2");
hashtable.put("英语", "3");
hashtable.put("物理", "4");
hashtable.put("化学", "5");
hashtable.put("生物", "6");
hashtable.put("政治", "7");
hashtable.put("地理", "8");
hashtable.put("历史", "9");
for (Map.Entry<String, String> entry : hashtable.entrySet()) {
System.out.println(entry.getKey() + " --> " + entry.getValue());
}
想想输出结果会是什么?输出结果如下:
英语 --> 3
地理 --> 8
物理 --> 4
数学 --> 2
历史 --> 9
化学 --> 5
语文 --> 1
政治 --> 7
生物 --> 6
从输出结果来看,Hashtable put的顺序与读取的顺序和HashMap一样不保证一致。
Hashtable的数据结构如下图所示,和HashMap一样,采用Entry数组+链表的方式实现。
Hashtable数据结构图根据数据结构图看下源码中支持此数据结构的重要属性:
public class Hashtable<K,V> extends Dictionary<K,V> implements
Map<K,V>, Cloneable, java.io.Serializable {
// 存储元素的table,Entry节点采用内部类实现
private transient Entry[] table;
// 已存放元素的计数器
private transient int count;
// 扩容阈值=table长度 * loadFactor
// table表的元素(不包含链表中的元素)超过这个阈值将扩容
private int threshold;
// 负载因子
private float loadFactor;
// 其他省略
}
其中table中存储的是Entry节点,Entry节点直接采用内部类的方式实现,实现了Map.Entry类,其数据结构源码如下:
private static class Entry<K,V> implements Map.Entry<K,V> {
int hash;
K key;
V value;
Entry<K,V> next;// 链接的下一个节点,构成链表
}
Entry节点中存储了元素的hash值,key, value,next引用。至此Hashtable的数据结构从源码就能看出来是数组+链表的方式实现了。
Hashtable的初始化
来看下Hashtable的默认构造方法是怎么初始化Hashtable的。
public Hashtable() {
this(11, 0.75f);
}
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);
}
在默认构造方法中,调用了Hashtable(int initialCapacity, float loadFactor)方法,初始Hashtable的容量为11,负载因子为0.75,那么初始阈值就是8。这点和HashMap很不同,HashMap在初始化时,table的大小总是2的幂次方,即使给定一个不是2的幂次方容量的值,也会自动初始化为最接近其2的幂次方的容量。
Hashtable的put方法的实现
源码实现步骤和HashMap没有任何区别,知识put方法上增加了synchronized关键字,保证线程安全。
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;
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++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<K,V>(hash, key, value, e);
count++;
return null;
}
实现步骤和思路:
1、禁止null value插入。
2、根据key的hashCode值 与 0x7FFFFFFF求与后得到新的hash值,然后计算其在table中的索引下标。
3、在索引下标下遍历链表,查找key是否已存在,存在则更新value值。
4、如果不存在,判断table.count是否超过阈值,超过则重新rehash,将原元素全部拷贝到新的table中,并重新计算索引下标。rehash后,容量是以前的2倍+1的大小,这点也和HashMap不同,HashMap是2倍。
5、插入元素时直接插入在链表头部。
6、更新元素计数器。
至于rehash方法的实现还请读者自行阅读源码,比较简单。get等其他方法也不做过多介绍,都比较简单。
Hashtable如何保证线程安全
前面提到的put方法中是通过synchronized来保证线程安全的。查看源码,发现对外提供的public方法,几乎全部加上了synchronized关键字。如下:
public synchronized int size(){}
public synchronized boolean isEmpty() {}
public synchronized Enumeration<K> keys() {}
public synchronized Enumeration<V> elements() {}
public synchronized boolean contains(Object value) {}
public synchronized boolean containsKey(Object key) {}
public synchronized V get(Object key) {}
public synchronized V put(K key, V value) {}
public synchronized V remove(Object key) {}
public synchronized void putAll(Map<? extends K, ? extends V> t) {}
public synchronized void clear() {}
public synchronized Object clone() {}
public synchronized String toString() {}
public synchronized boolean equals(Object o) {}
public synchronized int hashCode() {}
所以从这个特性上看,Hashtable是通过简单粗暴的方式来保证线程安全的额。所以Hashtable的性能在多线程环境下会非常低效。前面介绍的ConcurrentHashMap其实就是Java开发团队为了替换他而开发的,性能提高了不少。笔者也建议大家在多线程环境下抛弃Hashtable,改用ConcurrentHashMap,或者用HashMap配合外部锁,例如ReentrantLock来提高效率。
大概是Java团队已经开发出替代者ConcurrentHashMap,所以Hashtable从源码的实现来看,和JDK5相比,没有什么提升,大概是Java团队放弃了这个类的维护了。
网友评论