HashMap,HashTable,HashSet区别剖析
[size=13.3333px]HashMap、HashSet、HashTable之间的区别是Java程序员的一个常见面试题目，在此深入源代码进行分析：
在分析之前，先将其区别列于下面
1:HashSet底层采用的是HashMap进行实现的，但是没有key-value，只有HashMap的key set的视图，HashSet不容许重复的对象。

1. //HashSet类的部份源代码  
   
2. public class HashSet<E>  
   
3.     extends AbstractSet<E>  
   
4.     implements Set<E>, Cloneable, java.io.Serializable  
   
5. {   //用于类的序列化，可以不用管它  
   
6.     static final long serialVersionUID = -5024744406713321676L;  
   
7.     //从这里可以看出HashSet类里面真的是采用HashMap来实现的  
   
8.     private transient HashMap<E,Object> map;  
   
9.   
   
10.     // Dummy value to associate with an Object in the backing Map  
    
11.     //这里是生成一个对象，生成这个对象的作用是将每一个键的值均关联于此对象，以满足HashMap的键值对  
    
12.     private static final Object PRESENT = new Object();  
    
13.   
    
14.     /**
    
15.      * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
    
16.      * default initial capacity (16) and load factor (0.75).
    
17.      */  
    
18.     //这里是一个构造函数，开构生成一个HashMap对象，用来存放数据  
    
19.     public HashSet() {  
    
20.     map = new HashMap<E,Object>();  
    
21.     }  

复制代码

从上面的代码中得出的结论是HashSet的确是采用HashMap来实现的，而且每一个键都关键同一个Object类的对象，因此键所关联的值没有意义，真正有意义的是键。而HashMap里的键是不允许重复的，因此1也就很容易明白了。


2:Hashtable是基于Dictionary类的，而HashMap是基于Map接口的一个实现。

1. //从这里可以看得出Hashtable是继承于Dictionary,实现了Map接口  
   
2. public class Hashtable<K,V>  
   
3.     extends Dictionary<K,V>  
   
4.     implements Map<K,V>, Cloneable, java.io.Serializable {
   

复制代码

1. //这里可以看出的是HashMap是继承于AbstractMap类，实现了Map接口  
   
2. //因此与Hashtable继承的父类不同  
   
3. public class HashMap<K,V>  
   
4.     extends AbstractMap<K,V>  
   
5.     implements Map<K,V>, Cloneable, Serializable

复制代码

3:Hashtable里默认的方法是同步的，而HashMap则是非同步的，因此Hashtable是多线程安全的。

[url=]4:HashMap可以将空值作为一个表的条目的key或者value,HashMap中由于键不能重复，因此只有一条记录的Key可以是空值，而value可以有多个为空，但HashTable不允许null值(键与值均不行)。
[/url]找一个具有针对性的方法看看，这个方法就是put

1.     //Hashtable里的向集体增加键值对的方法，从这里可以明显看到的是  
   
2.     //采用了synchronized关键字，这个关键字的作用就是用于线程的同步操作  
   
3.     //因此下面这个方法对于多线程来说是安全的，但这会影响效率     
   
4.     public synchronized V put(K key, V value) {  
   
5.         // Make sure the value is not null  
   
6.         //如果值为空的，则会抛出异常  
   
7.         if (value == null) {  
   
8.             throw new NullPointerException();  
   
9.         }  
   
10.       
    
11.         // Makes sure the key is not already in the hashtable.  
    
12.         Entry tab[] = table;  
    
13.         //获得键值的hashCode,从这里也可以看得出key!=null,否则的话会抛出异常的呦  
    
14.         int hash = key.hashCode();  
    
15.         //获取键据所在的哈希表的位置  
    
16.         int index = (hash & 0x7FFFFFFF) % tab.length;  
    
17.         //从下面这个循环中可以看出的是，内部实现采用了链表，即桶状结构  
    
18.         for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {  
    
19.             //如果向Hashtable中增加同一个元素时，则会重新更新元素的值   
    
20.             if ((e.hash == hash) && e.key.equals(key)) {  
    
21.                     V old = e.value;  
    
22.                     e.value = value;  
    
23.                     return old;  
    
24.             }  
    
25.         }  
    
26.         //后面的暂时不用管它，大概的意思就是内存的个数少于某个阀值时，进行重新分配内存  
    
27.         modCount++;  
    
28.         if (count >= threshold) {  
    
29.             // Rehash the table if the threshold is exceeded  
    
30.             rehash();  
    
31.       
    
32.                 tab = table;  
    
33.                 index = (hash & 0x7FFFFFFF) % tab.length;  
    
34.         }  

复制代码

1.     //HashMap中的实现则相对来说要简单的很多了，如下代码  
   
2.     //这里的代码中没有synchronize关键字，即可以看出，这个关键函数不是线程安全的  
   
3.         public V put(K key, V value) {  
   
4.         //对于键是空时，将向Map中放值一个null-value构成的键值对  
   
5.         //对值却没有进行判空处理，意味着可以有多个具有键，键所对应的值却为空的元素。  
   
6.             if (key == null)  
   
7.                 return putForNullKey(value);  
   
8.         //算出键所在的哈希表的位置  
   
9.             int hash = hash(key.hashCode());  
   
10.             int i = indexFor(hash, table.length);  
    
11.         //同样从这里可以看得出来的是采用的是链表结构，采用的是桶状  
    
12.             for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
    
13.                 Object k;  
    
14.                 //对于向集体中增加具有相同键的情况时，这里可以看出，并不增加进去，而是进行更新操作  
    
15.                 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
    
16.                     V oldValue = e.value;  
    
17.                     e.value = value;  
    
18.                     e.recordAccess(this);  
    
19.                     return oldValue;  
    
20.                 }  
    
21.             }  
    
22.             //开始增加元素  
    
23.             modCount++;  
    
24.             addEntry(hash, key, value, i);  
    
25.             return null;  
    
26.         }  
    
27. 
    
28. 
    

复制代码

5:内存初始大小不同，HashTable初始大小是11，而HashMap初始大小是16。

1. public Hashtable() {  
   
2.    //从这里可以看出，默认的初始化大小11，这里的11并不是11个字节，而是11个Entry,这个Entry是  
   
3.    //实现链表的关键结构  
   
4.    //这里的0.75代表的是装载因子  
   
5. this(11, 0.75f);  
   
6. }  

复制代码

1. //这里均是一些定义  
   
2. public HashMap() {  
   
3. //这个默认的装载因子也是0.75  
   
4.      this.loadFactor = DEFAULT_LOAD_FACTOR;  
   
5. //默认的痤为0.75*16  
   
6.      threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);  
   
7. //这里开始是默认的初始化大小，这里大小是16  
   
8.      table = new Entry[DEFAULT_INITIAL_CAPACITY];  
   
9.      init();  
   
10. }  

复制代码

6:内存扩容时采取的方式也不同，Hashtable采用的是2*old+1,而HashMap是2*old。

1. //Hashtable中调整内存的函数，这个函数没有synchronize关键字，但是protected呦  
   
2. protected void rehash() {  
   
3.     //获取原来的表大小  
   
4.     int oldCapacity = table.length;  
   
5.     Entry[] oldMap = table;  
   
6.   //设置新的大小为2*oldCapacity+1  
   
7.     int newCapacity = oldCapacity * 2 + 1;  
   
8.     //开设空间  
   
9.     Entry[] newMap = new Entry[newCapacity];  
   
10.   //以下就不用管了。。。  
    
11.     modCount++;  
    
12.     threshold = (int)(newCapacity * loadFactor);  
    
13.     table = newMap;  
    
14.   
    
15.     for (int i = oldCapacity ; i-- > 0 ;) {  
    
16.         for (Entry<K,V> old = oldMap[i] ; old != null ; ) {  
    
17.         Entry<K,V> e = old;  
    
18.         old = old.next;  
    
19.   
    
20.         int index = (e.hash & 0x7FFFFFFF) % newCapacity;  
    
21.         e.next = newMap[index];  
    
22.         newMap[index] = e;  
    
23.         }  
    
24.     }  
    
25.     }  

复制代码

1.     //HashMap中要简单的多了，看看就知道了  
   
2.     void addEntry(int hash, K key, V value, int bucketIndex) {  
   
3.     Entry<K,V> e = table[bucketIndex];  
   
4.            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
   
5.            //如果超过了阀值  
   
6.            if (size++ >= threshold)  
   
7.            //就将大小设置为原来的2倍  
   
8.                resize(2 * table.length);  
   
9.        }  

复制代码

7:哈希值的计算方法不同，Hashtable直接使用的是对象的hashCode,而HashMap则是在对象的hashCode的基础上还进行了一些变化。

1. //Hashtable中可以看出的是直接采用关键字的hashcode作为哈希值  
   
2. int hash = key.hashCode();  
   
3. //然后进行模运算，求出所在哈希表的位置   
   
4. int index = (hash & 0x7FFFFFFF) % tab.length;  

复制代码

1. //Hashtable中可以看出的是直接采用关键字的hashcode作为哈希值  
   
2. int hash = key.hashCode();  
   
3. //然后进行模运算，求出所在哈希表的位置   
   
4. int index = (hash & 0x7FFFFFFF) % tab.length;  

复制代码

上面的HashMap中可以看出关键在两个函数hash与indexFor

源码如下:

1.     static int hash(int h) {  
   
2.             // This function ensures that hashCodes that differ only by  
   
3.              // constant multiples at each bit position have a bounded  
   
4.              // number of collisions (approximately 8 at default load factor).  
   
5.              //这个我就不多说了，>>>这个是无符号右移运算符，可以理解为无符号整型  
   
6.               h ^= (h >>> 20) ^ (h >>> 12);  
   
7.        return h ^ (h >>> 7) ^ (h >>> 4);  
   
8.     }  

复制代码

1. //求位于哈希表中的位置  
   
2. static int indexFor(int h, int length) {  
   
3.           return h & (length-1);  
   
4. }

复制代码

这确实是面试中出现的比较多的一道题了，学习中

很强大啊，这个帖子收藏了！