java集合框架09——HashTable和源码分析-阿里云开发者社区

开发者社区> 开发与运维> 正文

java集合框架09——HashTable和源码分析

简介:

     上一章我们学习了HashMap的源码,这一节我们来讨论一下HashTable,HashTable和HashMap在某种程度上是类似的。我们依然遵循以下步骤:先对HashTable有个整体的认识,然后学习它的源码,深入剖析HashTable。

1.HashTable简介

        首先看一下HashTable的继承关系

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. java.lang.Object  
  2.    ↳     java.util.Dictionary<K, V>  
  3.          ↳     java.util.Hashtable<K, V>  
  4.   
  5. public class Hashtable<K,V> extends Dictionary<K,V>  
  6.     implements Map<K,V>, Cloneable, java.io.Serializable { }  
        我们可以看出,HashTable不但继承了Dictionary,而且实现了Map、Cloneable和Serializable接口,所以HashTable也可以实例化。HashTable和hashMap不同,HashTable是线程安全的(等会我们在源码中就能看出)。下面我们先总览一下HashTable都有哪些API,然后我们详细分析它们。

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. synchronized void                clear()  
  2. synchronized Object              clone()  
  3.              boolean             contains(Object value)  
  4. synchronized boolean             containsKey(Object key)  
  5. synchronized boolean             containsValue(Object value)  
  6. synchronized Enumeration<V>      elements()  
  7. synchronized Set<Entry<K, V>>    entrySet()  
  8. synchronized boolean             equals(Object object)  
  9. synchronized V                   get(Object key)  
  10. synchronized int                 hashCode()  
  11. synchronized boolean             isEmpty()  
  12. synchronized Set<K>              keySet()  
  13. synchronized Enumeration<K>      keys()  
  14. synchronized V                   put(K key, V value)  
  15. synchronized void                putAll(Map<? extends K, ? extends V> map)  
  16. synchronized V                   remove(Object key)  
  17. synchronized int                 size()  
  18. synchronized String              toString()  
  19. synchronized Collection<V>       values()  

        从HashTable的API中可以看出,HashTable之所以是线程安全的,是因为方法上都加了synchronized关键字。

2. HashTable的数据结构

2.1 存储结构

        和HashMap一样,HashTable内部也维护了一个数组,数组中存放的是Entry<K,V>实体,数组定义如下:

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. private transient Entry<K,V>[] table;  
        然后我们看看Entry实体的定义:

2.2 Entry实体

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. /** 
  2.  * Entry实体类的定义 
  3.  */  
  4. private static class Entry<K,V> implements Map.Entry<K,V> {  
  5.     int hash; //哈希值  
  6.     final K key;  
  7.     V value;  
  8.     Entry<K,V> next; //指向的下一个Entry,即链表的下一个节点  
  9.   
  10.     //构造方法  
  11.     protected Entry(int hash, K key, V value, Entry<K,V> next) {  
  12.         this.hash = hash;  
  13.         this.key =  key;  
  14.         this.value = value;  
  15.         this.next = next;  
  16.     }  
  17.     //由于HashTable实现了Cloneable接口,所以支持克隆操作  
  18.     protected Object clone() {  
  19.         return new Entry<>(hash, key, value, (next==null ? null : (Entry<K,V>) next.clone()));  
  20.     }  
  21.   
  22.     //下面对Map.Entry的具体操作了  
  23.   
  24.     public K getKey() { //拿到key  
  25.         return key;  
  26.     }  
  27.   
  28.     public V getValue() { //拿到value  
  29.         return value;  
  30.     }  
  31.   
  32.     public V setValue(V value) { //设置value  
  33.         if (value == null//从这里可以看出,HashTable中的value是不允许为空的!  
  34.             throw new NullPointerException();  
  35.   
  36.         V oldValue = this.value;  
  37.         this.value = value;  
  38.         return oldValue;  
  39.     }  
  40.     //判断两个Entry是否相等  
  41.     public boolean equals(Object o) {  
  42.         if (!(o instanceof Map.Entry))  
  43.             return false;  
  44.         Map.Entry<?,?> e = (Map.Entry)o;  
  45.         //必须两个Entry的key和value均相等才行  
  46.         return key.equals(e.getKey()) && value.equals(e.getValue());  
  47.     }  
  48.   
  49.     public int hashCode() { //计算hashCode  
  50.         return (Objects.hashCode(key) ^ Objects.hashCode(value));  
  51.     }  
  52.   
  53.     public String toString() { //重写toString方法  
  54.         return key.toString()+"="+value.toString();  
  55.     }  
  56. }  
        从Entry实体的源码中可以看出,HashTable其实就是个存储Entry的数组,Entry中包含了键值对以及下一个Entry(用来处理冲突的),形成链表。而且Entry中的value是不允许为nul的。好了,我们对HashTable整体上了解了后,下面开始详细分析HashTable中的源码。

3.HashTable源码分析(基于JDK1.7)

3.1 成员属性

        首先我们看看HashTable都有哪些关键属性:

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. private transient Entry<K,V>[] table;  
  2.   
  3. private transient int count;//记录HashTable中有多少Entry实体  
  4.   
  5. //阈值,用于判断是否需要调整Hashtable的容量(threshold = 容量*加载因子)  
  6. private int threshold;  
  7.   
  8. private float loadFactor; // 加载因子  
  9.   
  10.   
  11. private transient int modCount = 0// Hashtable被改变的次数,用于fail-fast  
  12.   
  13. // 序列版本号  
  14. private static final long serialVersionUID = 1421746759512286392L;  
  15.   
  16. //最大的门限阈值,不能超过这个  
  17. static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;  
        这写成员属性的功能和HashMap基本上都一样的,这里就不再赘述了,详细信息可以看下上一篇博文HashMap对应的该部分。下面看看HashTable的几个构造方法:

3.2 构造方法

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. //参数为数组容量和加载因子的构造方法  
  2. public Hashtable(int initialCapacity, float loadFactor) {  
  3.     if (initialCapacity < 0)  
  4.         throw new IllegalArgumentException("Illegal Capacity: "+  
  5.                                            initialCapacity);  
  6.     if (loadFactor <= 0 || Float.isNaN(loadFactor))  
  7.         throw new IllegalArgumentException("Illegal Load: "+loadFactor);  
  8.   
  9.     if (initialCapacity==0)  
  10.         initialCapacity = 1;  
  11.     this.loadFactor = loadFactor;  
  12.     table = new Entry[initialCapacity]; //初始化数组  
  13.     //初始化门限 = 容量 * 加载因子  
  14.     threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);  
  15.     initHashSeedAsNeeded(initialCapacity);  
  16. }  
  17.   
  18. //参数为初始容量的构造方法  
  19. public Hashtable(int initialCapacity) {  
  20.     this(initialCapacity, 0.75f); //我们可以看出,默认加载因子为0.75  
  21. }   
  22.   
  23. //默认构造方法  
  24. public Hashtable() { //可以看出,默认容量为11,加载因子为0.75  
  25.     this(110.75f);  
  26. }  
  27.   
  28. //包含“子Map”的构造函数  
  29. public Hashtable(Map<? extends K, ? extends V> t) {  
  30.     this(Math.max(2*t.size(), 11), 0.75f);//先比较容量,如果Map的2倍容量大于11,则使用新的容量  
  31.     putAll(t);  
  32. }  
        我们可以看到,如果我们不指定数组容量和加载因子,HashTable会自动初始化容量为11,加载因子为0.75。加载因子和HashMap是相同的。

3.3 存取方法

        和HashMap的分析一样,HashTable的存取部分重点分析put和get方法,其他的方法我放到代码中分析。首先看看HashTable是如何存储数据的:

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. public synchronized V put(K key, V value) {  
  2.     //确保value不为空  
  3.     if (value == null) {  
  4.         throw new NullPointerException();  
  5.     }  
  6.   
  7.     Entry tab[] = table;  
  8.     int hash = hash(key); //计算哈希值  
  9.     int index = (hash & 0x7FFFFFFF) % tab.length; //根据哈希值计算在数组中的索引  
  10.     for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {  
  11.         if ((e.hash == hash) && e.key.equals(key)) { //如果对应的key已经存在  
  12.             V old = e.value;  
  13.             e.value = value; //替换掉原来的value  
  14.             return old;  
  15.         }  
  16.     }  
  17.     //否则新添加一个Entry  
  18.     modCount++;  
  19.     if (count >= threshold) { //判断数组中的Entry数量是否已经达到阈值  
  20.         rehash(); //如果达到了,扩容  
  21.   
  22.         tab = table;  
  23.         hash = hash(key); //重新计算哈希值  
  24.         index = (hash & 0x7FFFFFFF) % tab.length; //重新计算在新的数组中的索引  
  25.     }  
  26.   
  27.     //创建一个新的Entry  
  28.     Entry<K,V> e = tab[index];  
  29.     //存到对应的位置,并将其next置为原来该位置的Entry,这样就与原来的连上了  
  30.     tab[index] = new Entry<>(hash, key, value, e);  
  31.     count++;  
  32.     return null;  
  33. }  
        put方法中,首先检测value是否为null,如果为null则会抛出NullPointerException异常。然后往下走,跟HashMap的过程一样,先计算哈希值,再根据哈希值计算在数组中的索引位置,不过这里计算索引位置的方法和HashMap不同,HashMap里使用的是 hash & (length-1)的方法,其实本质上跟这里用的(hash & 0x7FFFFFFF) % table.length一样的效果,但是HashMap中的方法效率要高,至于它们两为啥本质一样的,可以参见我的上一博客:HashMap,那里分析的很详细。HashTable中的很好理解,直接取余就是索引值,地球人都知道~
              然后便开始往数组中存数据了,如果当前的key已经在里面了,那么直接替换原来旧的value,如果不存在,先判断数组中的Entry数量有没有达到门限值,达到了就要调用rehash方法进行扩容,然后重新计算当前key在新的数组中的索引值,然后在该位置添加进去即可。下面我们看一下rehash方法:

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;  
  2.   
  3. protected void rehash() {  
  4.     int oldCapacity = table.length;  
  5.     Entry<K,V>[] oldMap = table; //保存旧数组  
  6.   
  7.     int newCapacity = (oldCapacity << 1) + 1//新数组容量 = 2 * 旧容量 + 1  
  8.     if (newCapacity - MAX_ARRAY_SIZE > 0) {  
  9.         if (oldCapacity == MAX_ARRAY_SIZE)   
  10.             return;  
  11.         newCapacity = MAX_ARRAY_SIZE; //不能超出最大值  
  12.     }  
  13.     Entry<K,V>[] newMap = new Entry[newCapacity];  
  14.   
  15.     modCount++;  
  16.     threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);  
  17.     boolean rehash = initHashSeedAsNeeded(newCapacity);  
  18.   
  19.     table = newMap;  
  20.   
  21.     for (int i = oldCapacity ; i-- > 0 ;) {  
  22.         for (Entry<K,V> old = oldMap[i] ; old != null ; ) {  
  23.             Entry<K,V> e = old;  
  24.             old = old.next;  
  25.   
  26.             if (rehash) {  
  27.                 e.hash = hash(e.key);  
  28.             }  
  29.             int index = (e.hash & 0x7FFFFFFF) % newCapacity;//重新计算在新的数组中的索引  
  30.             //第一次newMap[index]为空,后面每次的nex都是当前的Entry,这样才能连上  
  31.             e.next = newMap[index];  
  32.             newMap[index] = e;//然后将该Entry放到当前位置  
  33.         }  
  34.     }  
  35. }  
        到这里put方法就分析完了,还有个putAll方法,是将整个Map加到当前HashTable中,内部也是遍历每个Entry,然后调用上面的put方法而已,简单看一下吧:

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. public synchronized void putAll(Map<? extends K, ? extends V> t) {  
  2.     for (Map.Entry<? extends K, ? extends V> e : t.entrySet())  
  3.         put(e.getKey(), e.getValue());  
  4. }  
        到这里,是不是感觉HashTable其实很简单,比HashMap简单多了。下面来看看get方法,也很简单,我觉得已经不用再分析了……

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. public synchronized V get(Object key) {  
  2.     Entry tab[] = table;  
  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; //拿到value  
  8.         }  
  9.     }  
  10.     return null;  
  11. }  

3.4 其他方法

        上面分析完了存取方法,剩下来的其他方法我放到代码里分析了,也很简单:

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. //返回数组中Entry数  
  2. public synchronized int size() {  
  3.     return count;  
  4. }  
  5. //判断是否为空  
  6. public synchronized boolean isEmpty() {  
  7.     return count == 0;  
  8. }  
  9.   
  10. //返回所有key的枚举对象  
  11. public synchronized Enumeration<K> keys() {  
  12.     return this.<K>getEnumeration(KEYS);  
  13. }  
  14.   
  15. //返回所有value的枚举对象  
  16. public synchronized Enumeration<V> elements() {  
  17.     return this.<V>getEnumeration(VALUES);  
  18. }  
  19.   
  20. //内部私有方法,返回枚举对象  
  21. private <T> Enumeration<T> getEnumeration(int type) {  
  22.     if (count == 0) {  
  23.         return Collections.emptyEnumeration();  
  24.     } else {  
  25.         return new Enumerator<>(type, false); //new一个Enumeration对象,见下面:  
  26.     }  
  27. }  
  28.   
  29. // Types of Enumerations/Iterations  
  30. private static final int KEYS = 0;  
  31. private static final int VALUES = 1;  
  32. private static final int ENTRIES = 2;  
  33.   
  34. //私有内部类,实现了Enumeration接口和Iterator接口  
  35. private class Enumerator<T> implements Enumeration<T>, Iterator<T> {  
  36.     Entry[] table = Hashtable.this.table;  
  37.     int index = table.length;  
  38.     Entry<K,V> entry = null;  
  39.     Entry<K,V> lastReturned = null;  
  40.     int type;  
  41.   
  42.     //该字段用来决定是使用iterator还是Enumeration  
  43.     boolean iterator; //false表示使用Enumeration  
  44.   
  45.     //fail-fast  
  46.     protected int expectedModCount = modCount;  
  47.   
  48.     Enumerator(int type, boolean iterator) {  
  49.         this.type = type;  
  50.         this.iterator = iterator;  
  51.     }  
  52.   
  53.     public boolean hasMoreElements() { //判断是否含有下一个元素  
  54.         Entry<K,V> e = entry;  
  55.         int i = index;  
  56.         Entry[] t = table;  
  57.         /* Use locals for faster loop iteration */  
  58.         while (e == null && i > 0) {  
  59.             e = t[--i];  
  60.         }  
  61.         entry = e;  
  62.         index = i;  
  63.         return e != null;  
  64.     }  
  65.   
  66.     public T nextElement() { //获得下一个元素  
  67.         Entry<K,V> et = entry;  
  68.         int i = index;  
  69.         Entry[] t = table;  
  70.         /* Use locals for faster loop iteration */  
  71.         while (et == null && i > 0) {  
  72.             et = t[--i];  
  73.         }  
  74.         entry = et;  
  75.         index = i;  
  76.         if (et != null) {  
  77.             Entry<K,V> e = lastReturned = entry;  
  78.             entry = e.next;  
  79.             //根据传进来的关键字决定返回什么  
  80.             return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);  
  81.         }  
  82.         throw new NoSuchElementException("Hashtable Enumerator");  
  83.     }  
  84.   
  85.     // Iterator methods  
  86.     public boolean hasNext() {  
  87.         return hasMoreElements();  
  88.     }  
  89.   
  90.     public T next() {  
  91.         if (modCount != expectedModCount)  
  92.             throw new ConcurrentModificationException();  
  93.         return nextElement();  
  94.     }  
  95.   
  96.     public void remove() {  
  97.         if (!iterator)  
  98.             throw new UnsupportedOperationException();  
  99.         if (lastReturned == null)  
  100.             throw new IllegalStateException("Hashtable Enumerator");  
  101.         if (modCount != expectedModCount)  
  102.             throw new ConcurrentModificationException();  
  103.   
  104.         synchronized(Hashtable.this) { //保证了线程安全  
  105.             Entry[] tab = Hashtable.this.table;  
  106.             int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;  
  107.   
  108.             for (Entry<K,V> e = tab[index], prev = null; e != null;  
  109.                  prev = e, e = e.next) {  
  110.                 if (e == lastReturned) {  
  111.                     modCount++;  
  112.                     expectedModCount++;  
  113.                     if (prev == null)  
  114.                         tab[index] = e.next;  
  115.                     else  
  116.                         prev.next = e.next;  
  117.                     count--;  
  118.                     lastReturned = null;  
  119.                     return;  
  120.                 }  
  121.             }  
  122.             throw new ConcurrentModificationException();  
  123.         }  
  124.     }  
  125. }  
  126.   
  127. //判断HashTable中是否包含value值  
  128. public synchronized boolean contains(Object value) {  
  129.     if (value == null) { //value不能为空  
  130.         throw new NullPointerException();  
  131.     }  
  132.   
  133.     Entry tab[] = table;  
  134.     //从后向前遍历table数组中的元素(Entry)  
  135.     for (int i = tab.length ; i-- > 0 ;) {  
  136.         for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {  
  137.             if (e.value.equals(value)) {  
  138.                 return true;  
  139.             }  
  140.         }  
  141.     }  
  142.     return false;  
  143. }  
  144.   
  145. public boolean containsValue(Object value) {  
  146.     return contains(value);  
  147. }  
  148.   
  149. //判断HashTable中是否包含key  
  150. public synchronized boolean containsKey(Object key) {  
  151.     Entry tab[] = table;  
  152.     int hash = hash(key);  
  153.     int index = (hash & 0x7FFFFFFF) % tab.length;  
  154.     for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {  
  155.         if ((e.hash == hash) && e.key.equals(key)) {  
  156.             return true;  
  157.         }  
  158.     }  
  159.     return false;  
  160. }  
  161.   
  162. //删除HashTable中键为key的Entry,并返回value  
  163. public synchronized V remove(Object key) {  
  164.     Entry tab[] = table;  
  165.     int hash = hash(key);  
  166.     int index = (hash & 0x7FFFFFFF) % tab.length;  
  167.     //找到key对应的Entry,然后在链表中找到要删除的节点,删除之。  
  168.     for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {  
  169.         if ((e.hash == hash) && e.key.equals(key)) {  
  170.             modCount++;  
  171.             if (prev != null) {  
  172.                 prev.next = e.next;  
  173.             } else {  
  174.                 tab[index] = e.next;  
  175.             }  
  176.             count--;  
  177.             V oldValue = e.value;  
  178.             e.value = null;  
  179.             return oldValue;  
  180.         }  
  181.     }  
  182.     return null;  
  183. }  
  184.   
  185. //清空HashTable  
  186. public synchronized void clear() {  
  187.     Entry tab[] = table;  
  188.     modCount++;  
  189.     for (int index = tab.length; --index >= 0; )  
  190.         tab[index] = null//将HashTable中数组值全部设置为null  
  191.     count = 0;  
  192. }  
  193.   
  194. //克隆一个HashTable,并以Object的形式返回  
  195. public synchronized Object clone() {  
  196.     try {  
  197.         Hashtable<K,V> t = (Hashtable<K,V>) super.clone();  
  198.         t.table = new Entry[table.length];  
  199.         for (int i = table.length ; i-- > 0 ; ) {  
  200.             t.table[i] = (table[i] != null)  
  201.                 ? (Entry<K,V>) table[i].clone() : null;  
  202.         }  
  203.         t.keySet = null;  
  204.         t.entrySet = null;  
  205.         t.values = null;  
  206.         t.modCount = 0;  
  207.         return t;  
  208.     } catch (CloneNotSupportedException e) {  
  209.         // this shouldn't happen, since we are Cloneable  
  210.         throw new InternalError();  
  211.     }  
  212. }  
  213.   
  214. //重写toString方法:{, ,}  
  215. public synchronized String toString() {  
  216.     int max = size() - 1;  
  217.     if (max == -1)  
  218.         return "{}";  
  219.   
  220.     StringBuilder sb = new StringBuilder();  
  221.     Iterator<Map.Entry<K,V>> it = entrySet().iterator();  
  222.   
  223.     sb.append('{');  
  224.     for (int i = 0; ; i++) {  
  225.         Map.Entry<K,V> e = it.next();  
  226.         K key = e.getKey();  
  227.         V value = e.getValue();  
  228.         sb.append(key   == this ? "(this Map)" : key.toString());  
  229.         sb.append('=');  
  230.         sb.append(value == this ? "(this Map)" : value.toString());  
  231.   
  232.         if (i == max)  
  233.             return sb.append('}').toString();  
  234.         sb.append(", ");  
  235.     }  
  236. }     
  237.   
  238. // Hashtable的“key的集合”。它是一个Set,意味着没有重复元素  
  239. private transient volatile Set<K> keySet = null;  
  240. // Hashtable的“key-value的集合”。它是一个Set,意味着没有重复元素  
  241. private transient volatile Set<Map.Entry<K,V>> entrySet = null;  
  242. // Hashtable的“value的集合”。它是一个Collection,意味着可以有重复元素  
  243. private transient volatile Collection<V> values = null;  
  244.   
  245. //返回一个被synchronizedSet封装后的keySet对象  
  246. //synchronizedSet封装的目的是对keySet的所有方法都添加synchronized,实现多线程同步  
  247. public Set<K> keySet() {  
  248.     if (keySet == null)  
  249.         keySet = Collections.synchronizedSet(new KeySet(), this);  
  250.     return keySet;  
  251. }  
  252.   
  253.   
  254. private class KeySet extends AbstractSet<K> {  
  255.     public Iterator<K> iterator() {  
  256.         return getIterator(KEYS); //返回一个迭代器,装有HashTable的信息  
  257.         //从这里也可以看出,获取到了key的Set集合后,要想取数据,只能通过迭代器  
  258.     }  
  259.     public int size() {  
  260.         return count;  
  261.     }  
  262.     public boolean contains(Object o) {  
  263.         return containsKey(o);  
  264.     }  
  265.     public boolean remove(Object o) {  
  266.         return Hashtable.this.remove(o) != null;  
  267.     }  
  268.     public void clear() {  
  269.         Hashtable.this.clear();  
  270.     }  
  271. }  
  272.   
  273. // 获取Hashtable的迭代器  
  274. // 若Hashtable的实际大小为0,则返回“空迭代器”对象;  
  275. // 否则,返回正常的Enumerator的对象。(由上面代码可知,Enumerator实现了迭代器和枚举两个接口)  
  276. private <T> Iterator<T> getIterator(int type) {  
  277.     if (count == 0) {  
  278.         return Collections.emptyIterator();  
  279.     } else {  
  280.         return new Enumerator<>(type, true);  
  281.     }  
  282. }  
  283.   
  284. //返回一个被synchronizedSet封装后的entrySet对象  
  285. public Set<Map.Entry<K,V>> entrySet() {  
  286.     if (entrySet==null)  
  287.         entrySet = Collections.synchronizedSet(new EntrySet(), this);  
  288.     return entrySet;  
  289. }  
  290. //跟keySet类似  
  291. private class EntrySet extends AbstractSet<Map.Entry<K,V>> {  
  292.     public Iterator<Map.Entry<K,V>> iterator() {  
  293.         return getIterator(ENTRIES);  
  294.     }  
  295.   
  296.     public boolean add(Map.Entry<K,V> o) {  
  297.         return super.add(o);  
  298.     }  
  299.       
  300.     // 查找EntrySet中是否包含Object(o)  
  301.     // 首先,在table中找到o对应的Entry(Entry是一个单向链表)  
  302.     // 然后,查找Entry链表中是否存在Object  
  303.     public boolean contains(Object o) {  
  304.         if (!(o instanceof Map.Entry))  
  305.             return false;  
  306.         Map.Entry entry = (Map.Entry)o;  
  307.         Object key = entry.getKey();  
  308.         Entry[] tab = table;  
  309.         int hash = hash(key);  
  310.         int index = (hash & 0x7FFFFFFF) % tab.length;  
  311.   
  312.         for (Entry e = tab[index]; e != null; e = e.next)  
  313.             if (e.hash==hash && e.equals(entry))  
  314.                 return true;  
  315.         return false;  
  316.     }  
  317.     // 删除元素Object(o)  
  318.     // 首先,在table中找到o对应的Entry(Entry是一个单向链表)  
  319.     // 然后,删除链表中的元素Object  
  320.     public boolean remove(Object o) {  
  321.         if (!(o instanceof Map.Entry))  
  322.             return false;  
  323.         Map.Entry<K,V> entry = (Map.Entry<K,V>) o;  
  324.         K key = entry.getKey();  
  325.         Entry[] tab = table;  
  326.         int hash = hash(key);  
  327.         int index = (hash & 0x7FFFFFFF) % tab.length;  
  328.   
  329.         for (Entry<K,V> e = tab[index], prev = null; e != null;  
  330.              prev = e, e = e.next) {  
  331.             if (e.hash==hash && e.equals(entry)) {  
  332.                 modCount++;  
  333.                 if (prev != null)  
  334.                     prev.next = e.next;  
  335.                 else  
  336.                     tab[index] = e.next;  
  337.   
  338.                 count--;  
  339.                 e.value = null;  
  340.                 return true;  
  341.             }  
  342.         }  
  343.         return false;  
  344.     }  
  345.   
  346.     public int size() {  
  347.         return count;  
  348.     }  
  349.   
  350.     public void clear() {  
  351.         Hashtable.this.clear();  
  352.     }  
  353. }  
  354.   
  355. // 返回一个被synchronizedCollection封装后的ValueCollection对象  
  356. // synchronizedCollection封装的目的是对ValueCollection的所有方法都添加synchronized,实现多线程同步  
  357. public Collection<V> values() {  
  358.     if (values==null)  
  359.         values = Collections.synchronizedCollection(new ValueCollection(),  
  360.                                                     this);  
  361.     return values;  
  362. }  
  363.   
  364. private class ValueCollection extends AbstractCollection<V> {  
  365.     public Iterator<V> iterator() {  
  366.         return getIterator(VALUES); //同上  
  367.     }  
  368.     public int size() {  
  369.         return count;  
  370.     }  
  371.     public boolean contains(Object o) {  
  372.         return containsValue(o);  
  373.     }  
  374.     public void clear() {  
  375.         Hashtable.this.clear();  
  376.     }  
  377. }  
  378.   
  379. //重写equals()方法  
  380. // 若两个Hashtable的所有key-value键值对都相等,则判断它们两个相等  
  381. public synchronized boolean equals(Object o) {  
  382.     if (o == this)  
  383.         return true;  
  384.   
  385.     if (!(o instanceof Map))  
  386.         return false;  
  387.     Map<K,V> t = (Map<K,V>) o;  
  388.     if (t.size() != size())  
  389.         return false;  
  390.   
  391.     try {  
  392.         Iterator<Map.Entry<K,V>> i = entrySet().iterator();  
  393.         while (i.hasNext()) {  
  394.             Map.Entry<K,V> e = i.next();  
  395.             K key = e.getKey();  
  396.             V value = e.getValue();  
  397.             if (value == null) {  
  398.                 if (!(t.get(key)==null && t.containsKey(key)))  
  399.                     return false;  
  400.             } else {  
  401.                 if (!value.equals(t.get(key)))  
  402.                     return false;  
  403.             }  
  404.         }  
  405.     } catch (ClassCastException unused)   {  
  406.         return false;  
  407.     } catch (NullPointerException unused) {  
  408.         return false;  
  409.     }  
  410.   
  411.     return true;  
  412. }  
  413.   
  414. //计算哈希值  
  415. //若HashTable的实际大小为0或者加载因子<0,则返回0  
  416. //否则返回“HashTable中的每个Entry的key和value的异或值的总和”  
  417. public synchronized int hashCode() {  
  418.   
  419.     int h = 0;  
  420.     if (count == 0 || loadFactor < 0)  
  421.         return h;  // Returns zero  
  422.   
  423.     loadFactor = -loadFactor;  // Mark hashCode computation in progress  
  424.     Entry[] tab = table;  
  425.     for (Entry<K,V> entry : tab)  
  426.         while (entry != null) {  
  427.             h += entry.hashCode();  
  428.             entry = entry.next;  
  429.         }  
  430.     loadFactor = -loadFactor;  // Mark hashCode computation complete  
  431.   
  432.     return h;  
  433. }  
  434.   
  435. // java.io.Serializable的写入函数  
  436. // 将Hashtable的“总的容量,实际容量,所有的Entry”都写入到输出流中  
  437. private void writeObject(java.io.ObjectOutputStream s)  
  438.         throws IOException {  
  439.     Entry<K, V> entryStack = null;  
  440.   
  441.     synchronized (this) {  
  442.         // Write out the length, threshold, loadfactor  
  443.         s.defaultWriteObject();  
  444.   
  445.         // Write out length, count of elements  
  446.         s.writeInt(table.length);  
  447.         s.writeInt(count);  
  448.   
  449.         // Stack copies of the entries in the table  
  450.         for (int index = 0; index < table.length; index++) {  
  451.             Entry<K,V> entry = table[index];  
  452.   
  453.             while (entry != null) {  
  454.                 entryStack =  
  455.                     new Entry<>(0, entry.key, entry.value, entryStack);  
  456.                 entry = entry.next;  
  457.             }  
  458.         }  
  459.     }  
  460.   
  461.     // Write out the key/value objects from the stacked entries  
  462.     while (entryStack != null) {  
  463.         s.writeObject(entryStack.key);  
  464.         s.writeObject(entryStack.value);  
  465.         entryStack = entryStack.next;  
  466.     }  
  467. }  
  468.   
  469. // java.io.Serializable的读取函数:根据写入方式读出  
  470. // 将Hashtable的“总的容量,实际容量,所有的Entry”依次读出  
  471. private void readObject(java.io.ObjectInputStream s)  
  472.      throws IOException, ClassNotFoundException  
  473. {  
  474.     // Read in the length, threshold, and loadfactor  
  475.     s.defaultReadObject();  
  476.   
  477.     // Read the original length of the array and number of elements  
  478.     int origlength = s.readInt();  
  479.     int elements = s.readInt();  
  480.   
  481.     // Compute new size with a bit of room 5% to grow but  
  482.     // no larger than the original size.  Make the length  
  483.     // odd if it's large enough, this helps distribute the entries.  
  484.     // Guard against the length ending up zero, that's not valid.  
  485.     int length = (int)(elements * loadFactor) + (elements / 20) + 3;  
  486.     if (length > elements && (length & 1) == 0)  
  487.         length--;  
  488.     if (origlength > 0 && length > origlength)  
  489.         length = origlength;  
  490.   
  491.     Entry<K,V>[] newTable = new Entry[length];  
  492.     threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);  
  493.     count = 0;  
  494.     initHashSeedAsNeeded(length);  
  495.   
  496.     // Read the number of elements and then all the key/value objects  
  497.     for (; elements > 0; elements--) {  
  498.         K key = (K)s.readObject();  
  499.         V value = (V)s.readObject();  
  500.         // synch could be eliminated for performance  
  501.         reconstitutionPut(newTable, key, value);  
  502.     }  
  503.     this.table = newTable;  
  504. }  
  505.   
  506. private void reconstitutionPut(Entry<K,V>[] tab, K key, V value)  
  507.     throws StreamCorruptedException  
  508. {  
  509.     if (value == null) {  
  510.         throw new java.io.StreamCorruptedException();  
  511.     }  
  512.     // Makes sure the key is not already in the hashtable.  
  513.     // This should not happen in deserialized version.  
  514.     int hash = hash(key);  
  515.     int index = (hash & 0x7FFFFFFF) % tab.length;  
  516.     for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {  
  517.         if ((e.hash == hash) && e.key.equals(key)) {  
  518.             throw new java.io.StreamCorruptedException();  
  519.         }  
  520.     }  
  521.     // Creates the new entry.  
  522.     Entry<K,V> e = tab[index];  
  523.     tab[index] = new Entry<>(hash, key, value, e);  
  524.     count++;  
  525. }  

4.HashTable的遍历方式

        Hashtable的遍历方式比较简单,一般分两步:

        1. 获得Entry或key或value的集合;

        2. 通过Iterator迭代器或者Enumeration遍历此集合。

4.1 遍历HashTable的Entry (效率高)

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. // 假设table是HashTable对象  
  2. // table中的key是String类型,value是Integer类型  
  3. Integer value = null;  
  4. Iterator iter = table.entrySet().iterator();  
  5. while(iter.hasNext()) {  
  6.     Map.Entry entry = (Map.Entry)iter.next();  
  7.     // 获取key  
  8.     key = (String)entry.getKey();  
  9.     // 获取value  
  10.     value = (Integer)entry.getValue();  
  11. }  

4.2 遍历HashTable的key

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. String key = null;  
  2. Integer value = null;  
  3. Iterator iter = table.keySet().iterator();  
  4. while (iter.hasNext()) {  
  5.     // 获取key  
  6.     key = (String)iter.next();  
  7.     // 根据key,获取value  
  8.     value = (Integer)table.get(key);  
  9. }  

4.3 遍历HashTable的value

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. Integer value = null;  
  2. Collection c = table.values();  
  3. Iterator iter= c.iterator();  
  4. while (iter.hasNext()) {  
  5.     value = (Integer)iter.next();  
  6. }  

4.5 通过Enumeration遍历HashTable的key(效率高)

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. Enumeration enu = table.keys();  
  2. while(enu.hasMoreElements()) {  
  3.     System.out.println(enu.nextElement());  
  4. }  

4.6 通过Enumeration遍历HashTable的value (效率高)

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. Enumeration enu = table.elements();  
  2. while(enu.hasMoreElements()) {  
  3.     System.out.println(enu.nextElement());  
  4. }  

        HashTable的遍历就介绍到这吧,至此,HashTable的源码就讨论完了,如有错误之处,欢迎留言指正~


转载:http://blog.csdn.net/eson_15/article/details/51208166

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章