Hashtable和HashMap源码分析

Hashtable和HashMap源码分析

         JDK中自带的Hashtable和HashMap是数据结构中哈希表的实现。除了这两个，还有一个HashSet的实现，但是HashSet基本是基于HashMap实现的，因此在这里我们只讨论Hashtable和HashMap的实现细节。

         首先列出经过源码分析，得出的关于Hashtable和HashMap之间的异同点如下：

         1、Hashtable和HashMap的继承关系比较如下：

 

         其中没有列出它们两个继承的Cloneable和Serializable接口，在下面的分析也是一样，不会分析比较它们的序列化和Cloneable的实现。

 

          2、Hashtable和HashMap之间最为明显的区别：同步处理

                在Hashtable的实现中，所有的外部访问方法都进行了同步化处理，即在方法中添加synchronized关键字；

                Hashtable中的方法示例：

 

Java代码   

1. public synchronized V put(K key, V value) {  
2.           
3.      //此处省略内部实现  
4. }  
5.   
6. public synchronized V remove(Object key) {  
7.            
8.      //此处省略内部实现  
9. }  

                而在HashMap的实现中，没有进行同步化处理；

                HashMap中的同样两个方法示例：

 

Java代码   

1. public V put(K key, V value) {  
2.     //此处省略内部实现  
3. }  
4.   
5. public V remove(Object key) {  
6.     //此处省略内部实现  
7. }  

 

 

          3、Hashtable和HashMap关于输入的key和value的限制：

          在Hashtable的实现中，不允许添加key或是value为null的键值对，如果key为null，则在put(K key,V value)方法调用hash()方法获取hash值时会抛出空指针异常， 而如果value为null，则在刚进入put(K key, V value)是就会检查而抛出空指针异常，如下具体程序所示：

 

         如下所示为Hashtable中的实现：

 

Java代码   

1. public synchronized V put(K key, V value) {  
2.         // Make sure the value is not null  
3.         if (value == null) {//在这里对value值进行了检验，如果为null，则抛出空指针异常  
4.             throw new NullPointerException();  
5.         }  
6.   
7.         // Makes sure the key is not already in the hashtable.  
8.         Entry tab[] = table;  
9.         int hash = hash(key);//在这里调用了下面的hash(Object k)方法  
10.       
11.     //在此省略了下面的实现......  
12. }  
13.   
14. //在下面的方法中可以看出，只要传入的k值为null，则在下面调用时就会产生空指针异常  
15. private int hash(Object k) {  
16.         if (useAltHashing) {  
17.             if (k.getClass() == String.class) {  
18.                 return sun.misc.Hashing.stringHash32((String) k);  
19.             } else {  
20.                 int h = hashSeed ^ k.hashCode();  
21.                 h ^= (h >>> 20) ^ (h >>> 12);  
22.                 return h ^ (h >>> 7) ^ (h >>> 4);  
23.              }  
24.         } else  {  
25.             return k.hashCode();  
26.         }  
27. }  

 

          而在HashMap的实现中，指定索引位置0处用来存放key值为null的键值对，如果在put方法中传入key值为null，如果索引位置0处存在已经存储的元素，则使用现在传进来的value值替换原来的value值，如果没有存储元素，则直接放置。所以我们容易知道，在HashMap中，键值key为null的键值对只能在索引位置为0的地方存储一个，即在整个HashMap中只允许有一个键值对的key为null，后面添加的只是在修改value值。

 

         如下所示为HashMap中的实现：

Java代码   

1. public V put(K key, V value) {  
2.       if (key == null)  
3.           return putForNullKey(value);  
4.     //在这里省略了后面key不为null的实现  
5. }  
6.   
7. //当key为null时调用  
8. private V putForNullKey(V value) {  
9.     for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
10.         //此时索引位置0处不为null，则替换原来的value值  
11.       if (e.key == null) {  
12.             V oldValue = e.value;  
13.             e.value = value;  
14.             e.recordAccess(this);  
15.             return oldValue;  
16.         }  
17.     }  
18.     modCount++;  
19.     //索引位置0处为空，则将键值对放置进去  
20.     addEntry(0, null, value, 0);  
21.     return null;  
22. }  

        

        4、在Hashtable和HashMap中，在每一次添加元素时，都会检查此时表中已有的数据个数与临界值的大小关系，当已存入的数据个数大于等于threshold临界值时，Hashtable会调用rehash()方法来对数组进行扩充，HashMap会调用resize(int capacity)方法来对数组进行扩充，然后依次遍历原数组，重新计算元素的hash值，存储到新的数组中，而且两者都是将数组扩大一倍，其中的临界值threshold = loadFactor(装载因子，默认0.75) * capacity(数组大小)；

 

         5、在Hashtable和HashMap中都提供了迭代器可让外部调用。在Hashtable和HashMap中均有entrySet()、keySet()、values()方法，分别返回Set<Entry<K,V>>、Set<K>、Collection<V>这三种类型的对象引用，其中就像上面说的，Hashtable返回的对象都是经过同步处理的，举个例子如下：

Java代码   

1. public Set<Map.Entry<K,V>> entrySet() {  
2.     if (entrySet==null)  
3.         entrySet = Collections.synchronizedSet(new EntrySet(), this);  
4.     return entrySet;  
5. }  

 而在HashMap中返回的对象引用，没有经过同步处理，举例如下：

Java代码   

1. public Set<Map.Entry<K,V>> entrySet() {  
2.     return entrySet0();  
3. }  
4.   
5. private Set<Map.Entry<K,V>> entrySet0() {  
6.     Set<Map.Entry<K,V>> es = entrySet;  
7.     return es != null ? es : (entrySet = new EntrySet());  
8. }