上一章我们学习了hashmap的源码，这一节我们来讨论一下hashtable，hashtable和hashmap在某种程度上是类似的。我们依然遵循以下步骤：先对hashtable有个整体的认识，然后学习它的源码，深入剖析hashtable。
首先看一下hashtable的继承关系
java.lang.object
↳ java.util.dictionary<k, v>
↳ java.util.hashtable<k, v>
public class hashtable<k,v> extends dictionary<k,v>
implements map<k,v>, cloneable, java.io.serializable { }
我们可以看出，hashtable不但继承了dictionary，而且实现了map、cloneable和serializable接口，所以hashtable也可以实例化。hashtable和hashmap不同，hashtable是线程安全的（等会我们在源码中就能看出）。下面我们先总览一下hashtable都有哪些api，然后我们详细分析它们。
synchronized void clear()
synchronized object clone()
boolean contains(object value)
synchronized boolean containskey(object key)
synchronized boolean containsvalue(object value)
synchronized enumeration<v> elements()
synchronized set<entry<k, v>> entryset()
synchronized boolean equals(object object)
synchronized v get(object key)
synchronized int hashcode()
synchronized boolean isempty()
synchronized set<k> keyset()
synchronized enumeration<k> keys()
synchronized v put(k key, v value)
synchronized void putall(map<? extends k, ? extends v> map)
synchronized v remove(object key)
synchronized int size()
synchronized string tostring()
synchronized collection<v> values()
从hashtable的api中可以看出，hashtable之所以是线程安全的，是因为方法上都加了synchronized关键字。
和hashmap一样，hashtable内部也维护了一个数组，数组中存放的是entry<k,v>实体，数组定义如下：
private transient entry<k,v>[] table;
然后我们看看entry实体的定义：
/**
* entry实体类的定义
*/
private static class entry<k,v> implements map.entry<k,v> {
int hash; //哈希值
final k key;
v value;
entry<k,v> next; //指向的下一个entry，即链表的下一个节点
//构造方法
protected entry(int hash, k key, v value, entry<k,v> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
//由于hashtable实现了cloneable接口，所以支持克隆操作
protected object clone() {
return new entry<>(hash, key, value, (next==null ? null : (entry<k,v>) next.clone()));
//下面对map.entry的具体操作了
public k getkey() { //拿到key
return key;
public v getvalue() { //拿到value
return value;
public v setvalue(v value) { //设置value
if (value == null) //从这里可以看出，hashtable中的value是不允许为空的！
throw new nullpointerexception();
v oldvalue = this.value;
return oldvalue;
//判断两个entry是否相等
public boolean equals(object o) {
if (!(o instanceof map.entry))
return false;
map.entry<?,?> e = (map.entry)o;
//必须两个entry的key和value均相等才行
return key.equals(e.getkey()) && value.equals(e.getvalue());
public int hashcode() { //计算hashcode
return (objects.hashcode(key) ^ objects.hashcode(value));
public string tostring() { //重写tostring方法
return key.tostring()+"="+value.tostring();
}
从entry实体的源码中可以看出，hashtable其实就是个存储entry的数组，entry中包含了键值对以及下一个entry（用来处理冲突的），形成链表。而且entry中的value是不允许为nul的。好了，我们对hashtable整体上了解了后，下面开始详细分析hashtable中的源码。
首先我们看看hashtable都有哪些关键属性：
private transient int count;//记录hashtable中有多少entry实体
//阈值，用于判断是否需要调整hashtable的容量（threshold = 容量*加载因子）
private int threshold;
private float loadfactor; // 加载因子
private transient int modcount = 0; // hashtable被改变的次数，用于fail-fast
// 序列版本号
private static final long serialversionuid = 1421746759512286392l;
//最大的门限阈值，不能超过这个
static final int alternative_hashing_threshold_default = integer.max_value;
//参数为数组容量和加载因子的构造方法
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);
inithashseedasneeded(initialcapacity);
//参数为初始容量的构造方法
public hashtable(int initialcapacity) {
this(initialcapacity, 0.75f); //我们可以看出，默认加载因子为0.75
}
//默认构造方法
public hashtable() { //可以看出，默认容量为11，加载因子为0.75
this(11, 0.75f);
//包含“子map”的构造函数
public hashtable(map<? extends k, ? extends v> t) {
this(math.max(2*t.size(), 11), 0.75f);//先比较容量，如果map的2倍容量大于11，则使用新的容量
putall(t);
我们可以看到，如果我们不指定数组容量和加载因子，hashtable会自动初始化容量为11，加载因子为0.75。加载因子和hashmap是相同的。
和hashmap的分析一样，hashtable的存取部分重点分析put和get方法，其他的方法我放到代码中分析。首先看看hashtable是如何存储数据的：
public synchronized v put(k key, v value) {
//确保value不为空
if (value == null) {
throw new nullpointerexception();
entry tab[] = table;
int hash = hash(key); //计算哈希值
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)) { //如果对应的key已经存在
v old = e.value;
e.value = value; //替换掉原来的value
return old;
}
//否则新添加一个entry
modcount++;
if (count >= threshold) { //判断数组中的entry数量是否已经达到阈值
rehash(); //如果达到了，扩容
tab = table;
hash = hash(key); //重新计算哈希值
index = (hash & 0x7fffffff) % tab.length; //重新计算在新的数组中的索引
//创建一个新的entry
entry<k,v> e = tab[index];
//存到对应的位置，并将其next置为原来该位置的entry，这样就与原来的连上了
tab[index] = new entry<>(hash, key, value, e);
count++;
return null;
然后便开始往数组中存数据了，如果当前的key已经在里面了，那么直接替换原来旧的value，如果不存在，先判断数组中的entry数量有没有达到门限值，达到了就要调用rehash方法进行扩容，然后重新计算当前key在新的数组中的索引值，然后在该位置添加进去即可。下面我们看一下rehash方法：
private static final int max_array_size = integer.max_value - 8;
protected void rehash() {
int oldcapacity = table.length;
entry<k,v>[] oldmap = table; //保存旧数组
int newcapacity = (oldcapacity << 1) + 1; //新数组容量 = 2 * 旧容量 + 1
if (newcapacity - max_array_size > 0) {
if (oldcapacity == max_array_size)
return;
newcapacity = max_array_size; //不能超出最大值
entry<k,v>[] newmap = new entry[newcapacity];
threshold = (int)math.min(newcapacity * loadfactor, max_array_size + 1);
boolean rehash = inithashseedasneeded(newcapacity);
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;
if (rehash) {
e.hash = hash(e.key);
}
int index = (e.hash & 0x7fffffff) % newcapacity;//重新计算在新的数组中的索引
//第一次newmap[index]为空，后面每次的nex都是当前的entry，这样才能连上
e.next = newmap[index];
newmap[index] = e;//然后将该entry放到当前位置
到这里put方法就分析完了，还有个putall方法，是将整个map加到当前hashtable中，内部也是遍历每个entry，然后调用上面的put方法而已，简单看一下吧：
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());
到这里，是不是感觉hashtable其实很简单，比hashmap简单多了。下面来看看get方法，也很简单，我觉得已经不用再分析了……
public synchronized v get(object key) {
int hash = hash(key); //哈希值
int index = (hash & 0x7fffffff) % tab.length; //索引值
if ((e.hash == hash) && e.key.equals(key)) {
return e.value; //拿到value
上面分析完了存取方法，剩下来的其他方法我放到代码里分析了，也很简单：
//返回数组中entry数
public synchronized int size() {
return count;
//判断是否为空
public synchronized boolean isempty() {
return count == 0;
//返回所有key的枚举对象
public synchronized enumeration<k> keys() {
return this.<k>getenumeration(keys);
//返回所有value的枚举对象
public synchronized enumeration<v> elements() {
return this.<v>getenumeration(values);
//内部私有方法，返回枚举对象
private <t> enumeration<t> getenumeration(int type) {
if (count == 0) {
return collections.emptyenumeration();
} else {
return new enumerator<>(type, false); //new一个enumeration对象，见下面：
// types of enumerations/iterations
private static final int keys = 0;
private static final int values = 1;
private static final int entries = 2;
//私有内部类，实现了enumeration接口和iterator接口
private class enumerator<t> implements enumeration<t>, iterator<t> {
entry[] table = hashtable.this.table;
int index = table.length;
entry<k,v> entry = null;
entry<k,v> lastreturned = null;
int type;
//该字段用来决定是使用iterator还是enumeration
boolean iterator; //false表示使用enumeration
//fail-fast
protected int expectedmodcount = modcount;
enumerator(int type, boolean iterator) {
this.type = type;
this.iterator = iterator;
public boolean hasmoreelements() { //判断是否含有下一个元素
entry<k,v> e = entry;
int i = index;
entry[] t = table;
/* use locals for faster loop iteration */
while (e == null && i > 0) {
e = t[--i];
entry = e;
index = i;
return e != null;
public t nextelement() { //获得下一个元素
entry<k,v> et = entry;
while (et == null && i > 0) {
et = t[--i];
entry = et;
if (et != null) {
entry<k,v> e = lastreturned = entry;
entry = e.next;
//根据传进来的关键字决定返回什么
return type == keys ? (t)e.key : (type == values ? (t)e.value : (t)e);
throw new nosuchelementexception("hashtable enumerator");
// iterator methods
public boolean hasnext() {
return hasmoreelements();
public t next() {
if (modcount != expectedmodcount)
throw new concurrentmodificationexception();
return nextelement();
public void remove() {
if (!iterator)
throw new unsupportedoperationexception();
if (lastreturned == null)
throw new illegalstateexception("hashtable enumerator");
synchronized(hashtable.this) { //保证了线程安全
entry[] tab = hashtable.this.table;
int index = (lastreturned.hash & 0x7fffffff) % tab.length;
for (entry<k,v> e = tab[index], prev = null; e != null;
prev = e, e = e.next) {
if (e == lastreturned) {
modcount++;
expectedmodcount++;
if (prev == null)
tab[index] = e.next;
else
prev.next = e.next;
count--;
lastreturned = null;
return;
}
//判断hashtable中是否包含value值
public synchronized boolean contains(object value) {
if (value == null) { //value不能为空
//从后向前遍历table数组中的元素（entry）
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);
//判断hashtable中是否包含key
public synchronized boolean containskey(object key) {
int hash = hash(key);
int index = (hash & 0x7fffffff) % tab.length;
return true;
//删除hashtable中键为key的entry，并返回value
public synchronized v remove(object key) {
//找到key对应的entry，然后在链表中找到要删除的节点，删除之。
for (entry<k,v> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
modcount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
count--;
v oldvalue = e.value;
e.value = null;
return oldvalue;
//清空hashtable
public synchronized void clear() {
for (int index = tab.length; --index >= 0; )
tab[index] = null; //将hashtable中数组值全部设置为null
count = 0;
//克隆一个hashtable，并以object的形式返回
public synchronized object clone() {
try {
hashtable<k,v> t = (hashtable<k,v>) super.clone();
t.table = new entry[table.length];
for (int i = table.length ; i-- > 0 ; ) {
t.table[i] = (table[i] != null)
? (entry<k,v>) 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();
//重写tostring方法：{, ,}
public synchronized string tostring() {
int max = size() - 1;
if (max == -1)
return "{}";
stringbuilder sb = new stringbuilder();
iterator<map.entry<k,v>> it = entryset().iterator();
sb.append('{');
for (int i = 0; ; i++) {
map.entry<k,v> e = it.next();
k key = e.getkey();
v value = e.getvalue();
sb.append(key == this ? "(this map)" : key.tostring());
sb.append('=');
sb.append(value == this ? "(this map)" : value.tostring());
if (i == max)
return sb.append('}').tostring();
sb.append(", ");
}
// hashtable的“key的集合”。它是一个set，意味着没有重复元素
private transient volatile set<k> keyset = null;
// hashtable的“key-value的集合”。它是一个set，意味着没有重复元素
private transient volatile set<map.entry<k,v>> entryset = null;
// hashtable的“value的集合”。它是一个collection，意味着可以有重复元素
private transient volatile collection<v> values = null;
//返回一个被synchronizedset封装后的keyset对象
//synchronizedset封装的目的是对keyset的所有方法都添加synchronized，实现多线程同步
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); //返回一个迭代器，装有hashtable的信息
//从这里也可以看出，获取到了key的set集合后，要想取数据，只能通过迭代器
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();
// 获取hashtable的迭代器
// 若hashtable的实际大小为0,则返回“空迭代器”对象；
// 否则，返回正常的enumerator的对象。(由上面代码可知，enumerator实现了迭代器和枚举两个接口)
private <t> iterator<t> getiterator(int type) {
return collections.emptyiterator();
return new enumerator<>(type, true);
//返回一个被synchronizedset封装后的entryset对象
public set<map.entry<k,v>> entryset() {
if (entryset==null)
entryset = collections.synchronizedset(new entryset(), this);
return entryset;
//跟keyset类似
private class entryset extends abstractset<map.entry<k,v>> {
public iterator<map.entry<k,v>> iterator() {
return getiterator(entries);
public boolean add(map.entry<k,v> o) {
return super.add(o);
// 查找entryset中是否包含object(o)
// 首先，在table中找到o对应的entry(entry是一个单向链表)
// 然后，查找entry链表中是否存在object
map.entry entry = (map.entry)o;
object key = entry.getkey();
entry[] tab = table;
int hash = hash(key);
int index = (hash & 0x7fffffff) % tab.length;
for (entry e = tab[index]; e != null; e = e.next)
if (e.hash==hash && e.equals(entry))
return false;
// 删除元素object(o)
// 然后，删除链表中的元素object
map.entry<k,v> entry = (map.entry<k,v>) o;
k key = entry.getkey();
for (entry<k,v> e = tab[index], prev = null; e != null;
prev = e, e = e.next) {
if (e.hash==hash && e.equals(entry)) {
modcount++;
if (prev != null)
prev.next = e.next;
else
tab[index] = e.next;
count--;
e.value = null;
// 返回一个被synchronizedcollection封装后的valuecollection对象
// synchronizedcollection封装的目的是对valuecollection的所有方法都添加synchronized，实现多线程同步
public collection<v> values() {
if (values==null)
values = collections.synchronizedcollection(new valuecollection(),
this);
return values;
private class valuecollection extends abstractcollection<v> {
public iterator<v> iterator() {
return getiterator(values); //同上
return containsvalue(o);
//重写equals()方法
// 若两个hashtable的所有key-value键值对都相等，则判断它们两个相等
public synchronized boolean equals(object o) {
if (o == this)
return true;
if (!(o instanceof map))
map<k,v> t = (map<k,v>) o;
if (t.size() != size())
iterator<map.entry<k,v>> i = entryset().iterator();
while (i.hasnext()) {
map.entry<k,v> e = i.next();
k key = e.getkey();
v value = e.getvalue();
if (value == null) {
if (!(t.get(key)==null && t.containskey(key)))
return false;
if (!value.equals(t.get(key)))
} catch (classcastexception unused) {
} catch (nullpointerexception unused) {
return true;
//计算哈希值
//若hashtable的实际大小为0或者加载因子<0，则返回0
//否则返回“hashtable中的每个entry的key和value的异或值的总和”
public synchronized int hashcode() {
int h = 0;
if (count == 0 || loadfactor < 0)
return h; // returns zero
loadfactor = -loadfactor; // mark hashcode computation in progress
entry[] tab = table;
for (entry<k,v> entry : tab)
while (entry != null) {
h += entry.hashcode();
entry = entry.next;
loadfactor = -loadfactor; // mark hashcode computation complete
return h;
// java.io.serializable的写入函数
// 将hashtable的“总的容量，实际容量，所有的entry”都写入到输出流中
private void writeobject(java.io.objectoutputstream s)
throws ioexception {
entry<k, v> entrystack = null;
synchronized (this) {
// write out the length, threshold, loadfactor
s.defaultwriteobject();
// write out length, count of elements
s.writeint(table.length);
s.writeint(count);
// stack copies of the entries in the table
for (int index = 0; index < table.length; index++) {
entry<k,v> entry = table[index];
while (entry != null) {
entrystack =
new entry<>(0, entry.key, entry.value, entrystack);
entry = entry.next;
// write out the key/value objects from the stacked entries
while (entrystack != null) {
s.writeobject(entrystack.key);
s.writeobject(entrystack.value);
entrystack = entrystack.next;
// java.io.serializable的读取函数：根据写入方式读出
// 将hashtable的“总的容量，实际容量，所有的entry”依次读出
private void readobject(java.io.objectinputstream s)
throws ioexception, classnotfoundexception
{
// read in the length, threshold, and loadfactor
s.defaultreadobject();
// read the original length of the array and number of elements
int origlength = s.readint();
int elements = s.readint();
// compute new size with a bit of room 5% to grow but
// no larger than the original size. make the length
// odd if it's large enough, this helps distribute the entries.
// guard against the length ending up zero, that's not valid.
int length = (int)(elements * loadfactor) + (elements / 20) + 3;
if (length > elements && (length & 1) == 0)
length--;
if (origlength > 0 && length > origlength)
length = origlength;
entry<k,v>[] newtable = new entry[length];
threshold = (int) math.min(length * loadfactor, max_array_size + 1);
inithashseedasneeded(length);
// read the number of elements and then all the key/value objects
for (; elements > 0; elements--) {
k key = (k)s.readobject();
v value = (v)s.readobject();
// synch could be eliminated for performance
reconstitutionput(newtable, key, value);
this.table = newtable;
private void reconstitutionput(entry<k,v>[] tab, k key, v value)
throws streamcorruptedexception
throw new java.io.streamcorruptedexception();
// makes sure the key is not already in the hashtable.
// this should not happen in deserialized version.
throw new java.io.streamcorruptedexception();
// creates the new entry.
hashtable的遍历方式比较简单，一般分两步：
1. 获得entry或key或value的集合；
2. 通过iterator迭代器或者enumeration遍历此集合。
// 假设table是hashtable对象
// table中的key是string类型，value是integer类型
integer value = null;
iterator iter = table.entryset().iterator();
while(iter.hasnext()) {
map.entry entry = (map.entry)iter.next();
// 获取key
key = (string)entry.getkey();
// 获取value
value = (integer)entry.getvalue();
string key = null;
iterator iter = table.keyset().iterator();
while (iter.hasnext()) {
key = (string)iter.next();
// 根据key，获取value
value = (integer)table.get(key);
collection c = table.values();
iterator iter= c.iterator();
value = (integer)iter.next();
enumeration enu = table.keys();
while(enu.hasmoreelements()) {
system.out.println(enu.nextelement());
enumeration enu = table.elements();
hashtable的遍历就介绍到这吧，至此，hashtable的源码就讨论完了，如有错误之处，欢迎留言指正~
转载：http://blog.csdn.net/eson_15/article/details/51208166