HashTable的源码分析

看的是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);
    }
1
2
3
4
5
6

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

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

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

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

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;
        }
......
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

遍历

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

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

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

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