Hashtable源码分析

集合特性

对于集合框架我们的关注点一般在一下几点：

1. 集合底层实现的数据结构是什么 数组+链表
2. 集合中元素是否允许为空 否 key和value都不能为空
3. 是否允许重复的数据 key唯一值
4. 是否有序(这里的有序是指读取数据和存放数据的顺序是否一致) 否
5. 是否线程安全。 是

针对这些问题，我们先来分析集合框架HashTable

HashTable分析

依赖关系
HashMap主要是继承自Dictionary，实现了Cloneable和Serializable接口使得HashMap具有克隆和序列化的功能、实现了Map接口因此具有Map的性质。

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

put方法分析

    public synchronized V put(K key, V value) {//方法前加synchronized 说明是线程安全的
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {//存在即覆盖，返回旧值
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);//hash冲突怎么办？
        return null;
    }

接着看下addEntry方法

    private void addEntry(int hash, K key, V value, int index) {
        modCount++;

        Entry<?,?> tab[] = table;//这个table也是个链表数组和hashmap一样
        if (count >= threshold) {//负载因子计算得的临界值
            // Rehash the table if the threshold is exceeded
            rehash();//和hashMap resize类似，扩容

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

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);//hash 冲突直接放在链表后面
        count++;
    }
    

看下get方法

    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)) {// 遍历链表，通过equals找到key对应值
                return (V)e.value;
            }
        }
        return null;
    }

Hashtable的实现比较简单，就是单纯的数组+链表的形式，通过synchronized保证线程安全，但是对该方法加锁，效率不容乐观，目前使用场景并不多。