HashTable的源码分析

谁借莪１个温暖的怀抱￠ 2022-06-03 05:50 175阅读 0赞

看的是JDK1.8的源码

HashTable和HashMap类似:

> 1.threshold，loadFactor
> 
> 2.都有扩容机制
> 
> 3.内部都是单链表的数组

不同:

> 1.HashTable继承Dictionary
> 
> 2.HashTable里的Capacity不需要2的n次幂
> 
> 3.HashTable里好多方法是synchronized
> 
> 4.HashTable不允许value有 null
> 
> 5.寻找数组下标的hash算法不同,HashMap的算法效率更好些

HashMap的key的hash，如果是null，则hash是0
    static final int hash(Object key) {
            int h;
            //hashcode的高位 和 hashcode 异或运算
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

HashMap: int index = (key.hashCode() ^ (key.hashCode() >>> 16))&(桶数组长度-1)

HashTable没有对key是否为null做处理，因此HashTable不允许key为null,传null为key会报空指针
    HashTable:int index = (key.hashCode() & 0x7FFFFFFF) % 桶数组长度

HashTable的内部机构和HashMap是基本一样的  
最关键的还是容器，该容器是个HashTable.Entry 类的数组

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

Entry

private static class Entry<K,V> implements Map.Entry<K,V> { 
            final int hash;
            final K key;
            V value;
            Entry<K,V> next;
            protected Entry(int hash, K key, V value, Entry<K,V> next) {
                this.hash = hash;
                this.key =  key;
                this.value = value;
                this.next = next;
            }
    ......
    }

HashMap最常用的是put方法,这里也分析HashTable的put方法，比对HashMap,HashTable的源码要容易懂得多

public synchronized V put(K key, V value) {
            //HashTable不接受null value
            if (value == null) {
                throw new NullPointerException();
            }
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            //对数组容器长度取模得到下标
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            Entry<K,V> entry = (Entry<K,V>)tab[index];
            //tab[index]如果找到不为空，则沿着当前存储得单链表往下找
            for(; entry != null ; entry = entry.next) {
            //如果某个entry的hash相等，key也相等,则替换，返回旧value
                if ((entry.hash == hash) && entry.key.equals(key)) {
                    V old = entry.value;
                    entry.value = value;
                    return old;
                }
            }
            //!!!如果tab[index]没找到，或tab[index]里的单链表有，单没有该值，则加入
            addEntry(hash, key, value, index);
            return null;
        }

private void addEntry(int hash, K key, V value, int index) {
            modCount++;
    
            Entry<?,?> tab[] = table;
            //超过阈值
            if (count >= threshold) {
                // !!!扩容
                rehash();
    
                tab = table;
                hash = key.hashCode();
                //扩容的话，需要重新算index
                index = (hash & 0x7FFFFFFF) % tab.length;
            }
    
            //取得容器里entry
            Entry<K,V> e = (Entry<K,V>) tab[index];
            //!!!新建立以entry,entry的next是传入的e
            tab[index] = new Entry<>(hash, key, value, e);
            count++;
        }

rehash

protected void rehash() {
            int oldCapacity = table.length;
            Entry<?,?>[] oldMap = table;
    
            //扩容后的数组长度为旧数组长度*2
            int newCapacity = (oldCapacity << 1) + 1;
           //新数组长度超过最大值
            if (newCapacity - MAX_ARRAY_SIZE > 0) {
                if (oldCapacity == MAX_ARRAY_SIZE)
                   //先判读如果旧数组长度已经最大，返回
                    return;
                 //新数组长度直接就是最大了 
                newCapacity = MAX_ARRAY_SIZE;
            }
            //新建立的2倍长度数组
            Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    
            modCount++;
            threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
            table = newMap;
    
            //遍历旧的数组
            for (int i = oldCapacity ; i-- > 0 ;) {
            //遍历数组里的单链表
                for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                    Entry<K,V> e = old;
                    old = old.next;
                    //对每个单链表里的元素重新计算下标
                    int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                    //将元素的next加上，按老规则新元素加在链表的头部
                    e.next = (Entry<K,V>)newMap[index];
                    newMap[index] = e;
                }
            }
        }

遍历

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

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

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

public Set<K> keySet() {
            if (keySet == null)
                keySet = Collections.synchronizedSet(new KeySet(), this);
            return keySet;
        }