java集合框架09——HashTable和源码分析
2023-09-14 09:01:03 时间
我们可以看出，HashTable不但继承了Dictionary，而且实现了Map、Cloneable和Serializable接口，所以HashTable也可以实例化。HashTable和hashMap不同，HashTable是线程安全的（等会我们在源码中就能看出）。下面我们先总览一下HashTable都有哪些API，然后我们详细分析它们。
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()
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; this.value = 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中的源码。
3.HashTable源码分析（基于JDK1.7）
//阈值，用于判断是否需要调整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;
这写成员属性的功能和HashMap基本上都一样的，这里就不再赘述了，详细信息可以看下上一篇博文HashMap对应的该部分。下面看看HashTable的几个构造方法： 3.2 构造方法
//参数为数组容量和加载因子的构造方法 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是相同的。
3.3 存取方法
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;
put方法中，首先检测value是否为null，如果为null则会抛出NullPointerException异常。然后往下走，跟HashMap的过程一样，先计算哈希值，再根据哈希值计算在数组中的索引位置，不过这里计算索引位置的方法和HashMap不同，HashMap里使用的是 hash (length-1)的方法，其实本质上跟这里用的(hash 0x7FFFFFFF) % table.length一样的效果，但是HashMap中的方法效率要高，至于它们两为啥本质一样的，可以参见我的上一博客：HashMap，那里分析的很详细。HashTable中的很好理解，直接取余就是索引值，地球人都知道~
然后便开始往数组中存数据了，如果当前的key已经在里面了，那么直接替换原来旧的value，如果不存在，先判断数组中的Entry数量有没有达到门限值，达到了就要调用rehash方法进行扩容，然后重新计算当前key在新的数组中的索引值，然后在该位置添加进去即可。下面我们看一下rehash方法：
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]; modCount++; 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方法，也很简单，我觉得已经不用再分析了……
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)) { return e.value; //拿到value } } return null;
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; int i = index; Entry[] t = table; /* Use locals for faster loop iteration */ while (et == null i 0) { et = t[--i]; } entry = et; index = i; 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"); if (modCount != expectedModCount) throw new ConcurrentModificationException(); 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; } } throw new ConcurrentModificationException(); } } //判断HashTable中是否包含value值 public synchronized boolean contains(Object value) { if (value == null) { //value不能为空 throw new NullPointerException(); } Entry tab[] = table; //从后向前遍历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) { 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)) { return true; } } return false; //删除HashTable中键为key的Entry，并返回value public synchronized V remove(Object key) { Entry tab[] = table; int hash = hash(key); int index = (hash 0x7FFFFFFF) % tab.length; //找到key对应的Entry，然后在链表中找到要删除的节点，删除之。 for (Entry K,V e = tab[index], prev = null ; e != null ; prev = e, e = e.next) { if ((e.hash == hash) e.key.equals(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; //清空HashTable public synchronized void clear() { Entry tab[] = table; modCount++; 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 shouldnt 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) { if (count == 0) { return Collections.emptyIterator(); } else { 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 public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; 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 true; return false; } // 删除元素Object(o) // 首先，在table中找到o对应的Entry(Entry是一个单向链表) // 然后，删除链表中的元素Object public boolean remove(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry K,V entry = (Map.Entry K,V K key = entry.getKey(); Entry[] tab = table; int hash = hash(key); 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.equals(entry)) { modCount++; if (prev != null) prev.next = e.next; else tab[index] = e.next; count--; e.value = null; return true; } } return false; } public int size() { return count; } public void clear() { Hashtable.this.clear(); } // 返回一个被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); //同上 } public int size() { return count; } public boolean contains(Object o) { return containsValue(o); } public void clear() { Hashtable.this.clear(); } //重写equals()方法 // 若两个Hashtable的所有key-value键值对都相等，则判断它们两个相等 public synchronized boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Map)) return false; Map K,V t = (Map K,V if (t.size() != size()) return false; try { 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; } else { if (!value.equals(t.get(key))) return false; } } } catch (ClassCastException unused) { return false; } catch (NullPointerException unused) { return false; } 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 its large enough, this helps distribute the entries. // Guard against the length ending up zero, thats 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); count = 0; 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 if (value == null) { throw new java.io.StreamCorruptedException(); } // Makes sure the key is not already in the hashtable. // This should not happen in deserialized version. 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)) { throw new java.io.StreamCorruptedException(); } } // Creates the new entry. Entry K,V e = tab[index]; tab[index] = new Entry (hash, key, value, e); count++;
java集合类史上最细讲解 - HashTable，Properties篇 1.基本介绍 HashTable的键和值都不能为空，否则会抛出一个异常 使用方法基本与HashMap一致 HashTable是线程安全的，HashMap是线程不安全的
Java实现HashTable 哈希表(Hash Table)也叫做散列表，是根据键值对(Key Value)而直接访问的数据结构。它通过将关键码值Key映射到表的一个位置来直接访问，以此加快查找的速度。这个映射函数叫做散列函数，存放记录的数值叫做散列表。
【JAVA】对比 Hashtable、HashMap、TreeMap 有什么不同？ Map 是广义 Java 集合框架中的另外一部分，它本身以及相关类型自然也是面试考察的热点。那么你知道，Hashtable、HashMap、TreeMap 有什么不同？
Java中的HashTable详解 HashTable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。
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()
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; this.value = 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中的源码。
3.HashTable源码分析（基于JDK1.7）
//阈值，用于判断是否需要调整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;
这写成员属性的功能和HashMap基本上都一样的，这里就不再赘述了，详细信息可以看下上一篇博文HashMap对应的该部分。下面看看HashTable的几个构造方法： 3.2 构造方法
//参数为数组容量和加载因子的构造方法 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是相同的。
3.3 存取方法
和HashMap的分析一样，HashTable的存取部分重点分析put和get方法，其他的方法我放到代码中分析。首先看看HashTable是如何存储数据的：
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;
put方法中，首先检测value是否为null，如果为null则会抛出NullPointerException异常。然后往下走，跟HashMap的过程一样，先计算哈希值，再根据哈希值计算在数组中的索引位置，不过这里计算索引位置的方法和HashMap不同，HashMap里使用的是 hash (length-1)的方法，其实本质上跟这里用的(hash 0x7FFFFFFF) % table.length一样的效果，但是HashMap中的方法效率要高，至于它们两为啥本质一样的，可以参见我的上一博客：HashMap，那里分析的很详细。HashTable中的很好理解，直接取余就是索引值，地球人都知道~
然后便开始往数组中存数据了，如果当前的key已经在里面了，那么直接替换原来旧的value，如果不存在，先判断数组中的Entry数量有没有达到门限值，达到了就要调用rehash方法进行扩容，然后重新计算当前key在新的数组中的索引值，然后在该位置添加进去即可。下面我们看一下rehash方法：
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]; modCount++; 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方法，也很简单，我觉得已经不用再分析了……
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)) { return e.value; //拿到value } } return null;
上面分析完了存取方法，剩下来的其他方法我放到代码里分析了，也很简单：
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; int i = index; Entry[] t = table; /* Use locals for faster loop iteration */ while (et == null i 0) { et = t[--i]; } entry = et; index = i; 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"); if (modCount != expectedModCount) throw new ConcurrentModificationException(); 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; } } throw new ConcurrentModificationException(); } } //判断HashTable中是否包含value值 public synchronized boolean contains(Object value) { if (value == null) { //value不能为空 throw new NullPointerException(); } Entry tab[] = table; //从后向前遍历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) { 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)) { return true; } } return false; //删除HashTable中键为key的Entry，并返回value public synchronized V remove(Object key) { Entry tab[] = table; int hash = hash(key); int index = (hash 0x7FFFFFFF) % tab.length; //找到key对应的Entry，然后在链表中找到要删除的节点，删除之。 for (Entry K,V e = tab[index], prev = null ; e != null ; prev = e, e = e.next) { if ((e.hash == hash) e.key.equals(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; //清空HashTable public synchronized void clear() { Entry tab[] = table; modCount++; 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 shouldnt 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) { if (count == 0) { return Collections.emptyIterator(); } else { 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 public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; 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 true; return false; } // 删除元素Object(o) // 首先，在table中找到o对应的Entry(Entry是一个单向链表) // 然后，删除链表中的元素Object public boolean remove(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry K,V entry = (Map.Entry K,V K key = entry.getKey(); Entry[] tab = table; int hash = hash(key); 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.equals(entry)) { modCount++; if (prev != null) prev.next = e.next; else tab[index] = e.next; count--; e.value = null; return true; } } return false; } public int size() { return count; } public void clear() { Hashtable.this.clear(); } // 返回一个被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); //同上 } public int size() { return count; } public boolean contains(Object o) { return containsValue(o); } public void clear() { Hashtable.this.clear(); } //重写equals()方法 // 若两个Hashtable的所有key-value键值对都相等，则判断它们两个相等 public synchronized boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Map)) return false; Map K,V t = (Map K,V if (t.size() != size()) return false; try { 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; } else { if (!value.equals(t.get(key))) return false; } } } catch (ClassCastException unused) { return false; } catch (NullPointerException unused) { return false; } 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 its large enough, this helps distribute the entries. // Guard against the length ending up zero, thats 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); count = 0; 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 if (value == null) { throw new java.io.StreamCorruptedException(); } // Makes sure the key is not already in the hashtable. // This should not happen in deserialized version. 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)) { throw new java.io.StreamCorruptedException(); } } // Creates the new entry. Entry K,V e = tab[index]; tab[index] = new Entry (hash, key, value, e); count++;
Hashtable的遍历方式比较简单，一般分两步：
1. 获得Entry或key或value的集合；
2. 通过Iterator迭代器或者Enumeration遍历此集合。
4.1 遍历HashTable的Entry （效率高）HashTable的遍历就介绍到这吧，至此，HashTable的源码就讨论完了，如有错误之处，欢迎留言指正~
转载：http://blog.csdn.net/eson_15/article/details/51208166
java集合类史上最细讲解 - HashTable，Properties篇 1.基本介绍 HashTable的键和值都不能为空，否则会抛出一个异常 使用方法基本与HashMap一致 HashTable是线程安全的，HashMap是线程不安全的
Java实现HashTable 哈希表(Hash Table)也叫做散列表，是根据键值对(Key Value)而直接访问的数据结构。它通过将关键码值Key映射到表的一个位置来直接访问，以此加快查找的速度。这个映射函数叫做散列函数，存放记录的数值叫做散列表。
【JAVA】对比 Hashtable、HashMap、TreeMap 有什么不同？ Map 是广义 Java 集合框架中的另外一部分，它本身以及相关类型自然也是面试考察的热点。那么你知道，Hashtable、HashMap、TreeMap 有什么不同？
Java中的HashTable详解 HashTable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。
相关文章
- mybatis简单案例源码详细【注释全面】——实体层（User.java）
- Java实现 蓝桥杯VIP 算法训练 与1连通的点的个数（并查集）
- java实现第六届蓝桥杯移动距离
- Java实现 蓝桥杯VIP 算法提高 开灯游戏
- Java实现 蓝桥杯VIP 算法训练 和为T
- 【JAVA】java中char类型数组用数组名打印结果不是地址值而是数组内容
- 源码之Java集合
- Java集合源码分析（七）HashMap<K, V>
- java集合框架11——TreeMap和源码分析（二）
- [Java] ThreadLocal的使用规则和源码分析
- atitit.商业版 源码保护 与 java本地原生代码转换 的方案总结
- Java 使用 poi 导出Excel 源码完整示例
- java通过读取本地文件获取反射方法参数，执行对象方法
- JVM源码分析之一个Java进程究竟能创建多少线程
- Java_io体系之RandomAccessFile简介、走进源码及示例——20
- Linux安装JAVA
- ZZNUOJ_用Java编写程序实现1527：简单加法(附源码)
- 【java】Collection源码阅读(JDK 8)
- 基于JAVA实现的WEB端UI自动化 - WebDriver高级篇 - cookie操作