HashTable的故事

很早之前，在講HashMap的時(shí)候，我們就說(shuō)過(guò)hash是散列，把...弄碎的意思。hashtable中的hash也是這個(gè)意思，而table呢，是指數(shù)據(jù)表格，也就是說(shuō)hashtable的本意是指，一份被數(shù)據(jù)被打散，分散在各處的數(shù)據(jù)表格。

HashTable，作為jdk中，極早提供的容器類(lèi)（jdk1.0），同時(shí)是支持?jǐn)?shù)據(jù)并發(fā)的類(lèi)，其在項(xiàng)目中的使用卻并不是很廣泛。在我所經(jīng)歷的項(xiàng)目中，開(kāi)發(fā)人員往往喜歡使用hashMap然后再通過(guò)鎖，創(chuàng)造出線(xiàn)程安全的環(huán)境。即使是后來(lái)推出concurrentHashMap，其使用的地方也并沒(méi)有特別廣泛。究其原因，我覺(jué)得是由于開(kāi)發(fā)人員對(duì)于其他hash容器并不熟悉。更愿意使用已有的較為熟悉的hash容器，即使他們?cè)诖颂幍膽?yīng)用比較費(fèi)事。

好了，廢話(huà)不多說(shuō)，我們直接開(kāi)始進(jìn)入正題吧：

hashTable繼承自dic類(lèi)，同時(shí)實(shí)現(xiàn)了map接口和Cloneable、Serializable兩個(gè)接口，代表該類(lèi)是可復(fù)制、序列化的類(lèi)。

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

ps：dic類(lèi)和map類(lèi)較為相似，是一個(gè)抽象的hash映射類(lèi)，包含了一些簡(jiǎn)單的空方法和接口。

private transient Entry<?,?>[] table;

瞬時(shí)數(shù)組變量，它就是hashtable中，最核心的數(shù)據(jù)存儲(chǔ)區(qū)域。

 

    /**
     * The total number of entries in the hash table.     */
    private transient int count;

數(shù)組長(zhǎng)度，不知道大家發(fā)現(xiàn)沒(méi)有，jdk非常喜歡用一個(gè)獨(dú)立變量來(lái)表示容器中數(shù)據(jù)的大小，而不是每次返回核心數(shù)據(jù)的size或length。

 

閾值，這個(gè)之前專(zhuān)門(mén)強(qiáng)調(diào)過(guò)，這里簡(jiǎn)單說(shuō)下，他是容積和負(fù)載因子的乘積，表示的含義是當(dāng)前容器中，能表現(xiàn)出較好性能的數(shù)據(jù)量上限。超過(guò)這個(gè)上限時(shí)，容器的性能將會(huì)有比較大的下降。注意容積和閾值是有區(qū)別的。

threshold  ['θr??hold]  n. 入口；門(mén)檻；開(kāi)始；極限；臨界值 

   private int threshold;

負(fù)載因子，是用來(lái)設(shè)定當(dāng)前容器中，元素的填充率的。

你可以理解成容器是一個(gè)城市，這個(gè)城市中最佳入住率的一個(gè)上限是負(fù)載因子。這個(gè)城市的入住用戶(hù)最佳的數(shù)目，就是他的閾值。

    /**
     * The load factor for the hashtable.
     *
     * @serial
     */
    private float loadFactor;

接下來(lái)是modCount ，這個(gè)變量的意義是，記錄hashtable中，被修改的次數(shù)（包括增、刪、改）三個(gè)操作的。而其用途呢，是未來(lái)被用作判定快速失敗時(shí)（fail-fast）的依據(jù)數(shù)據(jù)。關(guān)于快速失敗，這個(gè)我會(huì)在下邊講到。大家這里只要知道m(xù)odCount這個(gè)變量的表示的含義是什么就可以。

    private transient int modCount = 0;

然后是版本序列號(hào)

    private static final long serialVersionUID = 1421746759512286392L;

接著是構(gòu)造函數(shù)，參數(shù)分別為初始容積和負(fù)載因子。

函數(shù)內(nèi)會(huì)首先判斷初始容積和負(fù)載因子是否為正數(shù)。

接著如果初始容積為0，則賦予默認(rèn)值1.也就是說(shuō)，真實(shí)的容積至少都要為1。

接著對(duì)table賦予初始值，一個(gè)長(zhǎng)度為初始容積大小的Entry數(shù)組。(防盜連接：本文首發(fā)自http://www.cnblogs.com/jilodream/ )接著計(jì)算

閾值=（初始容積和負(fù)載因子的乘積），（當(dāng)前系統(tǒng)中最大的數(shù)組長(zhǎng)度+1），二者的最小值。

也就是說(shuō)閾值不能超過(guò)數(shù)組的最大長(zhǎng)度+1。這里注意一個(gè)isNaN()方法,是個(gè)很有意思的方法，研究該方法的源碼后，你會(huì)覺(jué)得很有意思。這個(gè)我會(huì)在以后的文章中講到。

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

public Hashtable(int initialCapacity, float loadFactor) {        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal Load: "+loadFactor);        if (initialCapacity==0)
            initialCapacity = 1;        this.loadFactor = loadFactor;
        table = new Entry<?,?>[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

只要初始容積的構(gòu)造函數(shù)，負(fù)載因子默認(rèn)為0.75

    public Hashtable(int initialCapacity) {        this(initialCapacity, 0.75f);
    }

無(wú)參的構(gòu)造函數(shù)，初始容積使用為11，負(fù)載因子為0.75

    public Hashtable() {        this(11, 0.75f);
    }

不知道大家發(fā)現(xiàn)沒(méi)，盡管提供了一個(gè)可能的，但是jdk的源碼往往系統(tǒng)提供多個(gè)，應(yīng)用于不同場(chǎng)景的接口，這些接口往往其實(shí)只是對(duì)自身其他接口的一個(gè)適配。但是對(duì)于調(diào)用者來(lái)說(shuō)，這樣卻很舒服。

 

接著是最后一個(gè)構(gòu)造函數(shù)，參數(shù)為一個(gè)map，map的k，v分別繼承自hashTable中的K,V.

函數(shù)首先調(diào)用一遍通用的構(gòu)造函數(shù)，負(fù)載因子為0.75。初始容積為map長(zhǎng)度的兩倍以及默認(rèn)的11，二者的較大值。也就是說(shuō)對(duì)于初始容積來(lái)說(shuō)，最小都要取到11。

接著調(diào)用putAll方法，將map中的數(shù)據(jù)添加到HashTable中。

    public Hashtable(Map<? extends K, ? extends V> t) {        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }

size()方法，方法采用同步機(jī)制，返回count變量。由于容器中并不是所有的元素都占滿(mǎn)了數(shù)據(jù)，所以直接用變量返回值的速度和效率會(huì)更高點(diǎn)。同時(shí)由于count會(huì)隨時(shí)變動(dòng)，這里采用同步方法的形式進(jìn)行線(xiàn)程保護(hù)。

    public synchronized int size() {        return count;
    }

isEmpyt，判斷當(dāng)前數(shù)組是否為空，與size()方法一致。

    public synchronized boolean isEmpty() {        return count == 0;
    }

keys，elements方法，分別返回返回hashTable中所有的key和value的枚舉集合。

這里KEYS，VALUES為靜態(tài)int常量。getEnumeration在下文中會(huì)提到。另外與前邊的方法相同，這里也是對(duì)整個(gè)方法進(jìn)行同步加鎖。

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

    public synchronized Enumeration<K> keys() {        return this.<K>getEnumeration(KEYS);
    }    public synchronized Enumeration<V> elements() {        return this.<V>getEnumeration(VALUES);
    }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

 接著是contains方法，方法意義不再贅述。

實(shí)現(xiàn)邏輯，首先判斷value是否為null，如果為null則直接拋出空引用。

接著將table變量賦值給tab臨時(shí)變量。然后循環(huán)tab，依次取出tab中的entry，以及entry的后繼元素。(防盜連接：本文首發(fā)自http://www.cnblogs.com/jilodream/ )如果元素的value equals()判斷等于參數(shù)value，則直接返回true。整個(gè)方法結(jié)束后，為發(fā)現(xiàn)，則會(huì)返回false。同時(shí)方法本身也是加同步鎖進(jìn)行線(xiàn)程安全保護(hù)。

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

    public synchronized boolean contains(Object value) {        if (value == null) {            throw new NullPointerException();
        }

        Entry<?,?> tab[] = table;        for (int i = tab.length ; i-- > 0 ;) {            for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {                if (e.value.equals(value)) {                    return true;
                }
            }
        }        return false;
    }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

接著是實(shí)現(xiàn)map接口的抽象方法，只是對(duì)contains方法進(jìn)行了一層封裝。

    public boolean containsValue(Object value) {        return contains(value);
    }

接著是線(xiàn)程同步方法：containsKey，方法含義不贅述，邏輯如下：

設(shè)定臨時(shí)變量并賦值table。取出key的hashCode。注意這里并沒(méi)有判定key是否為null。

而前文中的value則是判定的。這是由于value是作為equals方法的參數(shù)的。即使是null也無(wú)法被發(fā)現(xiàn)，但是判定一個(gè)映射的value為null表示的真的為null還是沒(méi)有映射到，這很歧義，所以干脆直接拋出異常?；氐秸模鶕?jù)hashCode計(jì)算出其在table數(shù)組中的索引。其實(shí)就是取低8位數(shù)字然后除以數(shù)組length取余數(shù)。(防盜連接：本文首發(fā)自http://www.cnblogs.com/jilodream/ )

接著依次循環(huán)table該索引的后繼元素，判定是否equals()相等。如果有則返回true。如果始終沒(méi)有找到，則返回false。

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

    public synchronized boolean containsKey(Object key) {
        Entry<?,?> tab[] = table;        int hash = key.hashCode();        int index = (hash & 0x7FFFFFFF) % tab.length;        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {            if ((e.hash == hash) && e.key.equals(key)) {                return true;
            }
        }        return false;
    }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

get()方法，與containsKey方法的邏輯是一致的。不同點(diǎn)是，在返回結(jié)果是，如果確實(shí)存在該key，則返回對(duì)應(yīng)的value，否則返回null。

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

    public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;        int hash = key.hashCode();        int index = (hash & 0x7FFFFFFF) % tab.length;        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {            if ((e.hash == hash) && e.key.equals(key)) {                return (V)e.value;
            }
        }        return null;
    }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

接著是前文提到的數(shù)組最大數(shù)字常亮。這里注意看參數(shù)的注釋。部分虛擬機(jī)是設(shè)定數(shù)組的長(zhǎng)度限制的。如果超出，可能會(huì)導(dǎo)致OOM異常

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

接著是rehash方法。這個(gè)方法是一個(gè)受保護(hù)方法。會(huì)在接下來(lái)的，hashtable添加元素的場(chǎng)景中被調(diào)用。他的作用呢，就是重新申請(qǐng)一塊大小合適的內(nèi)存。然后將鍵值元素重新安置到這塊元素中。

那么就需要兩個(gè)步驟。

1、計(jì)算新內(nèi)存的大小。

2、計(jì)算元素在新table中的位置。

    先看代碼：

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

 1     protected void rehash() { 2         int oldCapacity = table.length; 3         Entry<?,?>[] oldMap = table; 4  5         // overflow-conscious code 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 buckets10                 return;11             newCapacity = MAX_ARRAY_SIZE;12         }13         Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];14 15         modCount++;16         threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);17         table = newMap;18 19         for (int i = oldCapacity ; i-- > 0 ;) {20             for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {21                 Entry<K,V> e = old;22                 old = old.next;23 24                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;25                 e.next = (Entry<K,V>)newMap[index];26                 newMap[index] = e;27             }28         }29     }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

代碼中會(huì)首先獲取舊table的長(zhǎng)度oldCapacity 。然后oldCapacity 乘以2再加1.算出新table的長(zhǎng)度newCapacity 。

接著判斷newCapacity 是否超出了hashtable所能設(shè)定的最大值：MAX_ARRAY_SIZE。如果超出，則判斷oldCapacity 是否已經(jīng)等于最大值。如果已經(jīng)等于，則認(rèn)定，當(dāng)前hashtable的長(zhǎng)度已經(jīng)到達(dá)所允許的上限。無(wú)法再繼續(xù)擴(kuò)容。則直接返回。

否則將MAX_ARRAY_SIZE賦值給newCapacity 。作為新的長(zhǎng)度。也就是說(shuō)rehash在大小允許的情況下，一般會(huì)翻倍擴(kuò)容。但是如果翻倍后長(zhǎng)度超出上限，則以上限大小作為擴(kuò)容后新的大小。

接著以newCapacity 作為長(zhǎng)度，new出一個(gè)Entry數(shù)組，作為新的table元素存放容器。

modCount自加1。

接著計(jì)算閾值：newCapacity 乘以負(fù)載因子和MAX_ARRAY_SIZE+1 取較小值。注意這里負(fù)載因子是可以大于1的。因此newCapacity 乘以負(fù)載因子，式可以大于MAX_ARRAY_SIZE的。

接著就是計(jì)算舊有table中的鍵值元素在新table中的位置了：這里使用的是雙層循環(huán)，外層依次遍歷Entry主數(shù)組上的元素。如果entry[i]不等于null值，則將該元素及其后繼元素依次計(jì)算出新的位置，然后插入到主數(shù)組上的對(duì)應(yīng)位置。同時(shí)將主數(shù)組中原來(lái)位置的元素。作為新放置元素的后繼。也就是每個(gè)新元素，插在每個(gè)對(duì)應(yīng)位置的鏈表最前側(cè)。至于為什么不放在這個(gè)對(duì)應(yīng)鏈表的最后位置。其實(shí)很簡(jiǎn)單，因?yàn)檫@是一個(gè)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，需要依次遍歷每個(gè)元素，才能找到隊(duì)尾的元素。

接著是添加元素的私有方法addEntry。(防盜連接：本文首發(fā)自http://www.cnblogs.com/jilodream/ )

首先是modCount自加1.

接著如果當(dāng)前table的數(shù)量已經(jīng)超過(guò)了閾值，那么就進(jìn)行一次rehash，接著根據(jù)key的hashCode計(jì)算出當(dāng)前鍵值對(duì)的輸入索引。接著取出table對(duì)應(yīng)索引位置的元素一同做出一個(gè)新的Entry元素放在這個(gè)對(duì)應(yīng)索引的位置上。（這里要注意后續(xù)的entry 的構(gòu)造方法）同時(shí)count數(shù)目自加1。這里需要注意的是，當(dāng)前數(shù)目如果已經(jīng)超過(guò)閾值，前邊講到的rehash是不一定會(huì)重新做出新數(shù)組的（length超過(guò)了MAX_ARRAY_SIZE的限制時(shí)）很多人在理解這里的時(shí)候，就認(rèn)定只要count超過(guò)閾值就一定會(huì)重新分配table內(nèi)存的地址，這個(gè)理解是存在問(wèn)題的。

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

 1     private void addEntry(int hash, K key, V value, int index) { 2         modCount++; 3  4         Entry<?,?> tab[] = table; 5         if (count >= threshold) { 6             // Rehash the table if the threshold is exceeded 7             rehash(); 8  9             tab = table;10             hash = key.hashCode();11             index = (hash & 0x7FFFFFFF) % tab.length;12         }13 14         // Creates the new entry.15         @SuppressWarnings("unchecked")16         Entry<K,V> e = (Entry<K,V>) tab[index];17         tab[index] = new Entry<>(hash, key, value, e);18         count++;19     }

如果你覺(jué)得寫(xiě)的不錯(cuò)，歡迎轉(zhuǎn)載和點(diǎn)贊。轉(zhuǎn)載時(shí)請(qǐng)保留作者署名jilodream/王若伊_恩賜解脫（博客鏈接：http://www.cnblogs.com/jilodream/）Deep Think

http://www.cnblogs.com/jilodream/p/7209021.html