數(shù)據(jù)結(jié)構(gòu)解析-HashTable

概要

HashTable也是散列表的一種實(shí)現(xiàn)，我們在上一篇解析了HashMap,在這里我們與HashMap做個(gè)對比，讓你能清晰的了解兩者的區(qū)別:

散列表 實(shí)現(xiàn)方式 數(shù)據(jù)安全 數(shù)據(jù)安全實(shí)現(xiàn)方式 key\value是否可為Null
HashMap 數(shù)組+單向鏈表+紅黑樹 不安全 無 可為Null
HashTable 數(shù)組+單向鏈表 安全 Synchronized 不可為 Null

HashTable

1.繼承關(guān)系

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

2.常量&構(gòu)造方法


    /**
     * The hash table data.
     */
    private transient HashtableEntry<?,?>[] table;

    //HashTable條目數(shù)總量
    private transient int count;

    //下次擴(kuò)容量
    private int threshold;

    //負(fù)載因子
    private float loadFactor;

    //修改次數(shù)
    private transient int modCount = 0;

    //默認(rèn)的構(gòu)造函數(shù)
    public Hashtable() {
        this(11, 0.75f);
    }
    //指定容量大小
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }
     //指定容量大小和負(fù)載因子大小
    public Hashtable(int initialCapacity, float loadFactor) {
        //指定的容量大小不可以小于0,否則將拋出IllegalArgumentException異常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        ////指定的負(fù)載因子不可以小于0或?yàn)镹ull，若判定成立則拋出IllegalArgumentException異常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);
       //若指定的容量大小為0,則賦為1 即容量初始大小最小為 1
        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        //聲明table實(shí)例
        table = new HashtableEntry<?,?>[initialCapacity];
        //下次擴(kuò)容量長度
        threshold = (int)Math.min(initialCapacity, MAX_ARRAY_SIZE + 1);
    }
     //傳入一個(gè)Map集合,將Map集合中元素Map.Entry全部添加進(jìn)HashTable實(shí)例中
    public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }

3.HashtableEntry單向鏈表的實(shí)現(xiàn)

private static class HashtableEntry<K,V> implements Map.Entry<K,V> {
    // END Android-changed: Renamed Entry -> HashtableEntry.
        final int hash;
        final K key;
        V value;
        HashtableEntry<K,V> next;
         //構(gòu)造函數(shù)
        protected HashtableEntry(int hash, K key, V value, HashtableEntry<K,V> next) {
            this.hash = hash;
            this.key =  key;
            this.value = value;
            this.next = next;
        }

        @SuppressWarnings("unchecked")
        protected Object clone() {
            return new HashtableEntry<>(hash, key, value,
                                  (next==null ? null : (HashtableEntry<K,V>) next.clone()));
        }

        // Map.Entry Ops
         //獲取key
        public K getKey() {
            return key;
        }
         //獲取value
        public V getValue() {
            return value;
        }
        //設(shè)置value
        public V setValue(V value) {
            if (value == null)
                throw new NullPointerException();

            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }
         //equals對比
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;

            return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
               (value==null ? e.getValue()==null : value.equals(e.getValue()));
        }
        //獲取hash值
        public int hashCode() {
            return hash ^ Objects.hashCode(value);
        }

        public String toString() {
            return key.toString()+"="+value.toString();
        }
    }

4.Hashtable put函數(shù)源碼實(shí)現(xiàn)

 //這里使用Synchronized鎖方法的方式來保證put方法的在多線程下的數(shù)據(jù)安全
public synchronized V put(K key, V value) {
        // 確定value值不可為null
        if (value == null) {
            throw new NullPointerException();
        }

        // 確定key已經(jīng)在table中存在 
        HashtableEntry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        HashtableEntry<K,V> entry = (HashtableEntry<K,V>)tab[index];
        //通過for循環(huán),查找符合條件的key，賦予新的Value
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
        //添加新的Entry
        addEntry(hash, key, value, index);
        return null;
    }
private void addEntry(int hash, K key, V value, int index) {
        //修改次數(shù)+1
        modCount++;

        HashtableEntry<?,?> tab[] = table;
        //如果HashTable的子條目大小 大于 下次擴(kuò)容大小
        if (count >= threshold) {
            // 如果超過閾值，則重新組織HashTable 即對HashTable進(jìn)行擴(kuò)容
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        //將tab中索引位置下的Entry賦予 e
        HashtableEntry<K,V> e = (HashtableEntry<K,V>) tab[index];
        //創(chuàng)建新的HashtableEntry賦予tab中索引位置
        tab[index] = new HashtableEntry<>(hash, key, value, e);
        //table的條目樹+1
        count++;
    }
梳理以下HashTable.put函數(shù)的執(zhí)行過程
  • 1.確定value值不可為null
  • 2.若key已經(jīng)在table中存在，通過for循環(huán),查找符合條件的key，賦予新的Value 返回 舊值
  • 3.若不存在則進(jìn)行新增操作;
  • 3.1 修改次數(shù)+1，判斷HashTable是否需要擴(kuò)容
  • 3.2 獲取tab索引下的Entry 賦給 e
  • 3.3 創(chuàng)建一個(gè)HashTableEntry賦給tab指定索引位置
  • 3.4 tab的條目數(shù) +1

5.Hashtable get函數(shù)源碼實(shí)現(xiàn)

    //這里使用Synchronized 鎖方法的方式來保證get函數(shù)在多線程下的數(shù)據(jù)安全
    public synchronized V get(Object key) {
        HashtableEntry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
         //通過for循環(huán)來查找如何條件的value
        for (HashtableEntry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

6.Hashtable rehash函數(shù)源碼實(shí)現(xiàn)

 protected void rehash() {
        int oldCapacity = table.length;
        HashtableEntry<?,?>[] oldMap = table;

        // 舊表長度 二進(jìn)制左移1位+1 當(dāng)作新表的長度
        int newCapacity = (oldCapacity << 1) + 1;
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        HashtableEntry<?,?>[] newMap = new HashtableEntry<?,?>[newCapacity];
        //修改次數(shù)+1
        modCount++;
        //記錄下次擴(kuò)容量
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        //將新表賦予當(dāng)前操作表
        table = newMap;
        //通過for循環(huán)將舊表數(shù)據(jù)賦予新表中
        for (int i = oldCapacity ; i-- > 0 ;) {
            //通過for循環(huán)遍歷老表索引下的節(jié)點(diǎn)數(shù)據(jù),賦予新表中
            for (HashtableEntry<K,V> old = (HashtableEntry<K,V>)oldMap[i] ; old != null ; ) {
                HashtableEntry<K,V> e = old;
                 //將老表的下一個(gè)節(jié)點(diǎn)重新賦給old
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = (HashtableEntry<K,V>)newMap[index];
                //賦予新表的指定索引位置
                newMap[index] = e;
            }
        }
    }
結(jié)束分析
  • 通過上面的分析我們可以清楚地知道,HashTable的put函數(shù)和get函數(shù)在多線程下可以保證數(shù)據(jù)安全,實(shí)現(xiàn)方式都是使用Synchronized 同步鎖 鎖方法的方式實(shí)現(xiàn)的,而相對于HashMap是沒有采取任何方式保證數(shù)據(jù)安全,所以HashMap在多線程下無法保證數(shù)據(jù)安全.
  • 也同樣由于HashTable采用Synchronized同步鎖 鎖方法方式 鎖住了整個(gè)table保證數(shù)據(jù)安全,在多線程競爭激烈的情況下效率非常低;因?yàn)榫€程訪問同步時(shí),其他線程訪問HashTable的同步方法時(shí)可能會(huì)進(jìn)入阻塞或輪詢狀態(tài).
若想了解更多的關(guān)于Synchronized可以訪問我之前寫的一篇JAVA線程鎖---Synchronized

This ALL! Thanks EveryBody!

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容