[关闭]
@kiraSally 2018-03-12T18:29:13.000000Z 字数 5211 阅读 2231

集合番@Hashtable一文通(1.7版)

JAVA COLLECTIONS 源码 1.7版本


1.Hashtable的定义

2.Hashtable的数据结构

2.1 类定义

  1. public class Hashtable<K,V>
  2. extends Dictionary<K,V>
  3. implements Map<K,V>, Cloneable, java.io.Serializable

2.2 重要全局变量

  1. //The hash table data.
  2. //底层维护一个Entry(键值对)数组
  3. private transient Entry<K,V>[] table;
  4. //The total number of entries in the hash table.
  5. //元素总量,等同于HashMap的size
  6. private transient int count;
  7. //The load factor for the hashtable.
  8. //负载因子
  9. private float loadFactor;
  10. /**
  11. * The table is rehashed when its size exceeds this threshold.
  12. * (The value of this field is (int)(capacity * loadFactor).)
  13. * 超过阈值进行rehash
  14. */
  15. private int threshold;
  16. /**
  17. * The number of times this Hashtable has been structurally modified
  18. * Structural modifications are those that change the number of entries in
  19. * the Hashtable or otherwise modify its internal structure (e.g.,
  20. * rehash). This field is used to make iterators on Collection-views of
  21. * the Hashtable fail-fast. (See ConcurrentModificationException).
  22. * 结构性变动时modCount计数+1,用于遍历时的fail-fast机制生效
  23. */
  24. private transient int modCount = 0;

2.3 构造器

  1. /**
  2. * initialCapacity 默认11
  3. * loadFactor 默认 0.75
  4. */
  5. public Hashtable() {
  6. this(11, 0.75f);
  7. }
  8. /**
  9. * 跟JDK1.7的HashMap基本一致
  10. * @param initialCapacity 容量默认11
  11. * @param loadFactor 负载因子默认0.75
  12. */
  13. public Hashtable(int initialCapacity, float loadFactor) {
  14. if (initialCapacity < 0)
  15. throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
  16. if (loadFactor <= 0 || Float.isNaN(loadFactor))
  17. throw new IllegalArgumentException("Illegal Load: "+loadFactor);
  18. //区别在于没有强制令cap为2次幂,当initCap=0时,默认为1
  19. if (initialCapacity==0)
  20. initialCapacity = 1;
  21. this.loadFactor = loadFactor;
  22. table = new Entry[initialCapacity];
  23. threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  24. //useAltHashing为boolean,其如果为真,则执行另一散列的字符串键,以减少由于弱哈希计算导致的哈希冲突的发生
  25. useAltHashing = sun.misc.VM.isBooted() &&
  26. (initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
  27. }

3.Hashtable的重要方法

3.1 put方法

  1. public synchronized V put(K key, V value) {
  2. // Make sure the value is not null,而HashMap选择将key为null永远存放为table[0]位置
  3. if (value == null) {
  4. throw new NullPointerException();
  5. }
  6. // Makes sure the key is not already in the hashtable.
  7. //确保key不在hashtable中
  8. //首先,通过hash方法计算key的哈希值,并计算得出index值,确定其在table[]中的位置
  9. //其次,迭代index索引位置的链表,如果该位置处的链表存在相同的key,则替换value,返回旧的value
  10. Entry tab[] = table;
  11. int hash = hash(key);
  12. //计算下标,这里使用%方法,性能远不及HashMap的位运算 (这也是不推荐使用HashTable的原因之一)
  13. int index = (hash & 0x7FFFFFFF) % tab.length;
  14. for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
  15. //直接使用equals比较,而HashMap多了一层地址比较 `((k = e.key) == key || key.equals(k))`
  16. if ((e.hash == hash) && e.key.equals(key)) {
  17. V old = e.value;
  18. e.value = value;
  19. return old;
  20. }
  21. }
  22. //结构性变更操作 modCount计数+1
  23. modCount++;
  24. //HashMap选择新增addEntry方法封装一下逻辑
  25. if (count >= threshold) {
  26. // Rehash the table if the threshold is exceeded
  27. //如果超过阀值,就进行rehash操作
  28. rehash();
  29. tab = table;
  30. hash = hash(key);
  31. index = (hash & 0x7FFFFFFF) % tab.length;
  32. }
  33. // Creates the new entry.
  34. //将值插入,返回的为null
  35. Entry<K,V> e = tab[index];
  36. // 创建新的Entry节点,并将新的Entry插入Hashtable的index位置,并设置e为新的Entry的下一个元素
  37. tab[index] = new Entry<>(hash, key, value, e);
  38. //size++
  39. count++;
  40. return null;
  41. }

3.2 rehash方法

  1. protected void rehash() {
  2. int oldCapacity = table.length;
  3. Entry<K,V>[] oldMap = table;//使用临时拷贝,保证当前数据时效性(参见JAVA的`观察者`模式实现)
  4. // overflow-conscious code
  5. //原容量的2倍+1
  6. int newCapacity = (oldCapacity << 1) + 1;
  7. if (newCapacity - MAX_ARRAY_SIZE > 0) {
  8. if (oldCapacity == MAX_ARRAY_SIZE)
  9. // Keep running with MAX_ARRAY_SIZE buckets
  10. return;
  11. newCapacity = MAX_ARRAY_SIZE;
  12. }
  13. Entry<K,V>[] newMap = new Entry[newCapacity];
  14. //rehash也属于结构化变更,modCount计数+1
  15. modCount++;
  16. threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  17. boolean currentAltHashing = useAltHashing;
  18. useAltHashing = sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
  19. boolean rehash = currentAltHashing ^ useAltHashing;
  20. table = newMap;
  21. //遍历原数组重新赋值给新数组
  22. for (int i = oldCapacity ; i-- > 0 ;) {
  23. for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
  24. Entry<K,V> e = old;
  25. old = old.next;
  26. if (rehash) {
  27. e.hash = hash(e.key);//重新hash计算
  28. }
  29. //还是坑爹的%运算
  30. int index = (e.hash & 0x7FFFFFFF) % newCapacity;
  31. e.next = newMap[index];
  32. newMap[index] = e;
  33. }
  34. }
  35. }

3.3 get方法

  1. public synchronized V get(Object key) {
  2. Entry tab[] = table;//使用临时拷贝,保证当前数据时效性(参见JAVA的`观察者`模式实现)
  3. int hash = hash(key);
  4. int index = (hash & 0x7FFFFFFF) % tab.length;
  5. for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
  6. if ((e.hash == hash) && e.key.equals(key)) {
  7. return e.value;
  8. }
  9. }
  10. return null;
  11. }

4.Hashtable的迭代

  1. //1、使用keys()
  2. Enumeration<String> en1 = table.keys();
  3. while(en1.hasMoreElements()) {
  4. en1.nextElement();
  5. }
  6. //2、使用elements()
  7. Enumeration<String> en2 = table.elements();
  8. while(en2.hasMoreElements()) {
  9. en2.nextElement();
  10. }
  11. //3、使用keySet()
  12. Iterator<String> it1 = table.keySet().iterator();
  13. while(it1.hasNext()) {
  14. it1.next();
  15. }
  16. //4、使用entrySet()
  17. Iterator<Entry<String, String>> it2 = table.entrySet().iterator();
  18. while(it2.hasNext()) {
  19. it2.next();
  20. }

5.Hashtable vs HashMap

  • HashTable 基于 Dictionary 类,而 HashMap 是基于 AbstractMap。Dictionary 是任何可将键映射到相应值的类的抽象父类,而 AbstractMap 是基于 Map 接口的实现,它以最大限度地减少实现此接口所需的工作.
  • HashMap 的 key 和 value 都允许为 null,而 Hashtable 的 key 和 value 都不允许为 null。HashMap 遇到 key 为 null 的时候,调用 putForNullKey 方法进行处理(统一放入table[0]位置),而对 value 没有处理;Hashtable遇到 null,直接返回 NullPointerException.
  • Hashtable 方法是同步,而HashMap则不是。Hashtable 中的几乎所有的 public 的方法都是 synchronized 的,而有些方法也是在内部通过 synchronized 代码块来实现。
  • HashTable由于使用sync和%运算(以及相关算法实现)的缘故,相比于HashMap,性能较低,因此非常不推荐继续使用HashTable.
    非竞争环境下推荐使用HashMap
    多线程环境下推荐使用ConcurrentHashMap

集合番@Hashtable一文通(1.7版)黄志鹏kira 创作,采用 知识共享 署名-非商业性使用 4.0 国际 许可协议 进行许可。

本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注