首頁»Java WEB»HashMap和HashTable到底哪不同?

                    HashMap和HashTable到底哪不同?

                    來源:xinzhao 發布時間:2017-12-06 閱讀次數:

                      HashMap和HashTable有什么不同?在面試和被面試的過程中,我問過也被問過這個問題,也見過了不少回答,今天決定寫一寫自己心目中的理想答案。

                      代碼版本

                      JDK每一版本都在改進。本文討論的HashMap和HashTable基于JDK 1.7.0_67。源碼見這里

                      1. 時間

                      HashTable產生于JDK 1.1,而HashMap產生于JDK 1.2。從時間的維度上來看,HashMap要比HashTable出現得晚一些。

                      2. 作者

                      以下是HashTable的作者:

                    以下代碼及注釋來自java.util.HashTable
                    
                    * @author  Arthur van Hoff
                    * @author  Josh Bloch
                    * @author  Neal Gafter

                      以下是HashMap的作者:

                    以下代碼及注釋來自java.util.HashMap
                    
                     * @author  Doug Lea
                     * @author  Josh Bloch
                     * @author  Arthur van Hoff
                     * @author  Neal Gafter

                      可以看到HashMap的作者多了大神Doug Lea。不了解Doug Lea的,可以看這里

                      3. 對外的接口(API)

                      HashMap和HashTable都是基于哈希表來實現鍵值映射的工具類。討論他們的不同,我們首先來看一下他們暴露在外的API有什么不同。

                      3.1 Public Method

                      下面兩張圖,我畫出了HashMap和HashTable的類繼承體系,并列出了這兩個類的可供外部調用的公開方法。

                      從圖中可以看出,兩個類的繼承體系有些不同。雖然都實現了Map、Cloneable、Serializable三個接口。但是HashMap繼承自抽象類AbstractMap,而HashTable繼承自抽象類Dictionary。其中Dictionary類是一個已經被廢棄的類,這一點我們可以從它代碼的注釋中看到:

                    以下代碼及注釋來自java.util.Dictionary
                    
                     * <strong>NOTE: This class is obsolete.  New implementations should
                     * implement the Map interface, rather than extending this class.</strong>

                      同時我們看到HashTable比HashMap多了兩個公開方法。一個是elements,這來自于抽象類Dictionary,鑒于該類已經廢棄,所以這個方法也就沒什么用處了。另一個多出來的方法是contains,這個多出來的方法也沒什么用,因為它跟containsValue方法功能是一樣的。代碼為證:

                    以下代碼及注釋來自java.util.HashTable
                    
                     public synchronized boolean contains(Object value) {
                         if (value == null) {
                             throw new NullPointerException();
                         }
                    
                         Entry tab[] = table;
                         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);
                     }

                      所以從公開的方法上來看,這兩個類提供的,是一樣的功能。都提供鍵值映射的服務,可以增、刪、查、改鍵值對,可以對建、值、鍵值對提供遍歷視圖。支持淺拷貝,支持序列化。

                      3.2 Null Key & Null Value

                      HashMap是支持null鍵和null值的,而HashTable在遇到null時,會拋出NullPointerException異常。這并不是因為HashTable有什么特殊的實現層面的原因導致不能支持null鍵和null值,這僅僅是因為HashMap在實現時對null做了特殊處理,將null的hashCode值定為了0,從而將其存放在哈希表的第0個bucket中。我們一put方法為例,看一看代碼的細節:

                    以下代碼及注釋來自java.util.HashTable
                    
                    public synchronized V put(K key, V value) {
                    
                        // 如果value為null,拋出NullPointerException
                        if (value == null) {
                            throw new NullPointerException();
                        }
                    
                        // 如果key為null,在調用key.hashCode()時拋出NullPointerException
                    
                        // ...
                    }
                    
                    
                    以下代碼及注釋來自java.util.HasMap
                    
                    public V put(K key, V value) {
                        if (table == EMPTY_TABLE) {
                            inflateTable(threshold);
                        }
                        // 當key為null時,調用putForNullKey特殊處理
                        if (key == null)
                            return putForNullKey(value);
                        // ...
                    }
                    
                    private V putForNullKey(V value) {
                        // key為null時,放到table[0]也就是第0個bucket中
                        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                            if (e.key == null) {
                                V oldValue = e.value;
                                e.value = value;
                                e.recordAccess(this);
                                return oldValue;
                            }
                        }
                        modCount++;
                        addEntry(0, null, value, 0);
                        return null;
                    }

                      4. 實現原理

                      本節討論HashMap和HashTable在數據結構和算法層面,有什么不同。

                      4.1 數據結構

                      HashMap和HashTable都使用哈希表來存儲鍵值對。在數據結構上是基本相同的,都創建了一個繼承自Map.Entry的私有的內部類Entry,每一個Entry對象表示存儲在哈希表中的一個鍵值對。

                      Entry對象唯一表示一個鍵值對,有四個屬性:

                      -K key 鍵對象

                      -V value 值對象

                      -int hash 鍵對象的hash值

                      -Entry entry 指向鏈表中下一個Entry對象,可為null,表示當前Entry對象在鏈表尾部

                      可以說,有多少個鍵值對,就有多少個Entry對象,那么在HashMap和HashTable中是怎么存儲這些Entry對象,以方便我們快速查找和修改的呢?請看下圖。

                      上圖畫出的是一個桶數量為8,存有5個鍵值對的HashMap/HashTable的內存布局情況。可以看到HashMap/HashTable內部創建有一個Entry類型的引用數組,用來表示哈希表,數組的長度,即是哈希桶的數量。而數組的每一個元素都是一個Entry引用,從Entry對象的屬性里,也可以看出其是鏈表的節點,每一個Entry對象內部又含有另一個Entry對象的引用。

                      這樣就可以得出結論,HashMap/HashTable內部用Entry數組實現哈希表,而對于映射到同一個哈希桶(數組的同一個位置)的鍵值對,使用Entry鏈表來存儲(解決hash沖突)。

                    以下代碼及注釋來自java.util.HashTable
                    
                    /**
                     * The hash table data.
                     */
                    private transient Entry<K,V>[] table;
                    
                    
                    以下代碼及注釋來自java.util.HashMap
                    
                    /**
                     * The table, resized as necessary. Length MUST Always be a power of two.
                     */
                    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

                      從代碼可以看到,對于哈希桶的內部表示,兩個類的實現是一致的。

                      4.2 算法

                      上一小節已經說了用來表示哈希表的內部數據結構。HashMap/HashTable還需要有算法來將給定的鍵key,映射到確定的hash桶(數組位置)。需要有算法在哈希桶內的鍵值對多到一定程度時,擴充哈希表的大小(數組的大小)。本小節比較這兩個類在算法層面有哪些不同。

                      初始容量大小和每次擴充容量大小的不同。先看代碼:

                    以下代碼及注釋來自java.util.HashTable
                    
                    // 哈希表默認初始大小為11
                    public Hashtable() {
                        this(11, 0.75f);
                    }
                    
                    protected void rehash() {
                        int oldCapacity = table.length;
                        Entry<K,V>[] oldMap = table;
                    
                        // 每次擴容為原來的2n+1
                        int newCapacity = (oldCapacity << 1) + 1;
                        // ...
                    }
                    
                    
                    以下代碼及注釋來自java.util.HashMap
                    
                    // 哈希表默認初始大小為2^4=16
                    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
                    
                    void addEntry(int hash, K key, V value, int bucketIndex) {
                        // 每次擴充為原來的2n 
                        if ((size >= threshold) && (null != table[bucketIndex])) {
                           resize(2 * table.length);
                    }

                      可以看到HashTable默認的初始大小為11,之后每次擴充為原來的2n+1。HashMap默認的初始化大小為16,之后每次擴充為原來的2倍。還有我沒列出代碼的一點,就是如果在創建時給定了初始化大小,那么HashTable會直接使用你給定的大小,而HashMap會將其擴充為2的冪次方大小。

                      也就是說HashTable會盡量使用素數、奇數。而HashMap則總是使用2的冪作為哈希表的大小。我們知道當哈希表的大小為素數時,簡單的取模哈希的結果會更加均勻(具體證明,見這篇文章),所以單從這一點上看,HashTable的哈希表大小選擇,似乎更高明些。但另一方面我們又知道,在取模計算時,如果模數是2的冪,那么我們可以直接使用位運算來得到結果,效率要大大高于做除法。所以從hash計算的效率上,又是HashMap更勝一籌。

                      所以,事實就是HashMap為了加快hash的速度,將哈希表的大小固定為了2的冪。當然這引入了哈希分布不均勻的問題,所以HashMap為解決這問題,又對hash算法做了一些改動。具體我們來看看,在獲取了key對象的hashCode之后,HashTable和HashMap分別是怎樣將他們hash到確定的哈希桶(Entry數組位置)中的。

                    以下代碼及注釋來自java.util.HashTable
                    
                    // hash 不能超過Integer.MAX_VALUE 所以要取其最小的31個bit
                    int hash = hash(key);
                    int index = (hash & 0x7FFFFFFF) % tab.length;
                    
                    // 直接計算key.hashCode()
                    private int hash(Object k) {
                        // hashSeed will be zero if alternative hashing is disabled.
                        return hashSeed ^ k.hashCode();
                    }
                    
                    
                    以下代碼及注釋來自java.util.HashMap
                    int hash = hash(key);
                    int i = indexFor(hash, table.length);
                    
                    // 在計算了key.hashCode()之后,做了一些位運算來減少哈希沖突
                    final int hash(Object k) {
                        int h = hashSeed;
                        if (0 != h && k instanceof String) {
                            return sun.misc.Hashing.stringHash32((String) k);
                        }
                    
                        h ^= k.hashCode();
                    
                        // This function ensures that hashCodes that differ only by
                        // constant multiples at each bit position have a bounded
                        // number of collisions (approximately 8 at default load factor).
                        h ^= (h >>> 20) ^ (h >>> 12);
                        return h ^ (h >>> 7) ^ (h >>> 4);
                    }
                    
                    // 取模不再需要做除法
                    static int indexFor(int h, int length) {
                        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
                        return h & (length-1);
                    }

                      正如我們所言,HashMap由于使用了2的冪次方,所以在取模運算時不需要做除法,只需要位的與運算就可以了。但是由于引入的hash沖突加劇問題,HashMap在調用了對象的hashCode方法之后,又做了一些位運算在打散數據。關于這些位計算為什么可以打散數據的問題,本文不再展開了。感興趣的可以看這里

                      如果你有細心讀代碼,還可以發現一點,就是HashMap和HashTable在計算hash時都用到了一個叫hashSeed的變量。這是因為映射到同一個hash桶內的Entry對象,是以鏈表的形式存在的,而鏈表的查詢效率比較低,所以HashMap/HashTable的效率對哈希沖突非常敏感,所以可以額外開啟一個可選hash(hashSeed),從而減少哈希沖突。因為這是兩個類相同的一點,所以本文不再展開了,感興趣的看這里。事實上,這個優化在JDK 1.8中已經去掉了,因為JDK 1.8中,映射到同一個哈希桶(數組位置)的Entry對象,使用了紅黑樹來存儲,從而大大加速了其查找效率。

                      5. 線程安全

                      我們說HashTable是同步的,HashMap不是,也就是說HashTable在多線程使用的情況下,不需要做額外的同步,而HashMap則不行。那么HashTable是怎么做到的呢?

                    以下代碼及注釋來自java.util.HashTable
                    
                    public synchronized V get(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 e.value;
                            }
                        }
                        return null;
                    }
                    
                    public Set<K> keySet() {
                        if (keySet == null)
                            keySet = Collections.synchronizedSet(new KeySet(), this);
                        return keySet;
                    }

                      可以看到,也比較簡單,就是公開的方法比如get都使用了synchronized描述符。而遍歷視圖比如keySet都使用了Collections.synchronizedXXX進行了同步包裝。

                      6. 代碼風格

                      從我的品位來看,HashMap的代碼要比HashTable整潔很多。下面這段HashTable的代碼,我就覺著有點混亂,不太能接受這種代碼復用的方式。

                    以下代碼及注釋來自java.util.HashTable
                    
                    /**
                     * A hashtable enumerator class.  This class implements both the
                     * Enumeration and Iterator interfaces, but individual instances
                     * can be created with the Iterator methods disabled.  This is necessary
                     * to avoid unintentionally increasing the capabilities granted a user
                     * by passing an Enumeration.
                     */
                    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;
                    
                        /**
                         * Indicates whether this Enumerator is serving as an Iterator
                         * or an Enumeration.  (true -> Iterator).
                         */
                        boolean iterator;
                    
                        /**
                         * The modCount value that the iterator believes that the backing
                         * Hashtable should have.  If this expectation is violated, the iterator
                         * has detected concurrent modification.
                         */
                        protected int expectedModCount = modCount;
                    
                        Enumerator(int type, boolean iterator) {
                            this.type = type;
                            this.iterator = iterator;
                        }
                        
                        //...
                    
                    }

                      7. HashTable已經被淘汰了,不要在代碼中再使用它。

                      以下描述來自于HashTable的類注釋:

                    If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.ConcurrentHashMap in place of Hashtable.

                      簡單來說就是,如果你不需要線程安全,那么使用HashMap,如果需要線程安全,那么使用ConcurrentHashMap。HashTable已經被淘汰了,不要在新的代碼中再使用它。

                      8. 持續優化

                      雖然HashMap和HashTable的公開接口應該不會改變,或者說改變不頻繁。但每一版本的JDK,都會對HashMap和HashTable的內部實現做優化,比如上文曾提到的JDK 1.8的紅黑樹優化。所以,盡可能的使用新版本的JDK吧,除了那些炫酷的新功能,普通的API也會有性能上有提升。

                      為什么HashTable已經淘汰了,還要優化它?因為有老的代碼還在使用它,所以優化了它之后,這些老的代碼也能獲得性能提升。

                    QQ群:WEB開發者官方群(515171538),驗證消息:10000
                    微信群:加小編微信 849023636 邀請您加入,驗證消息:10000
                    提示:更多精彩內容關注微信公眾號:全棧開發者中心(fsder-com)
                    網友評論(共0條評論) 正在載入評論......
                    理智評論文明上網,拒絕惡意謾罵 發表評論 / 共0條評論
                    登錄會員中心
                    福彩试机号今天 买彩票的图片 12选五胆拖中奖规则 浙江福彩3d出号走势图 青海十一选五网上投注 青州娱乐场所招工吗 体彩超级大乐透走 3d2019开奖综合分布图 中国福利彩票 云南十一选五开奘结果23号 北京11选5过滤工具 河南快三今走势图 香港东方心经码报最准料 现在做什么赚钱 贵州快3连线形态走势图 年精彩特码诗