黑马程序员技术交流社区

标题: 【上海校区】Java篇 - 并发容器之Hashtable源码分析 [打印本页]

---

作者: 不二晨    时间: 2019-2-15 09:57
标题: 【上海校区】Java篇 - 并发容器之Hashtable源码分析
1. Hashtable 简介

和HashMap一样，Hashtable 也是一个散列表，它存储的内容是键值对(key-value)映射。
Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。
Hashtable 的函数都是同步的，这意味着它是线程安全的。它的key、value都不可以为null。此外，Hashtable中的映射不是有序的。

Hashtable 的实例有两个参数影响其性能：初始容量和加载因子。容量是哈希表中桶的数量，初始容量就是哈希表创建时的容量。注意，哈希表的状态为open：在发生"哈希冲突"的情况下，单个桶会存储多个条目，这些条目必须按顺序搜索。加载因子是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用 rehash 方法的具体细节则依赖于该实现。

通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查找某个条目的时间（在大多数 Hashtable 操作中，包括 get 和 put 操作，都反映了这一点）。



2. 源码分析



2.1 类的定义
public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
}
从Hashtable的类定义来看，它接收键值对泛型，继承Dictionary类，实现Map，Cloneable, Serializable接口。

Dictionary类：

public abstract class Dictionary<K,V> {

    public Dictionary() {
    }

    abstract public int size();

    abstract public boolean isEmpty();

    abstract public Enumeration<K> keys();

    abstract public Enumeration<V> elements();

    abstract public V get(Object key);

    abstract public V put(K key, V value);

    abstract public V remove(Object key);
}
Dictionary是一个抽象类，并且里面的方法全是抽象的。





2.2 全局变量和常量说明
    /**
     * Hashtable存储的数据，一个键值对对应一个Entry对象
     */
    private transient Entry<?,?>[] table;

    /**
     * Hashtable中Entry的数量
     */
    private transient int count;

    /**
     * 当表的大小超过此阈值时，表将扩容. 值为(int)(capacity * loadFactor).
     */
    private int threshold;

    /**
     * Hashtable的加载因子
     */
    private float loadFactor;

    /**
     * Hashtable已被修改的次数
     */
    private transient int modCount = 0;

    /**
     * 数组最大size
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
里面有个Entry数组，看看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;
        }

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

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public V setValue(V value) {
            if (value == null)
                throw new NullPointerException();

            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        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()));
        }

        public int hashCode() {
            return hash ^ Objects.hashCode(value);
        }

        public String toString() {
            return key.toString()+"="+value.toString();
        }
    }
通过源码可以得知，Entry实现Map.Entry接口，是一个单链表结构。里面存储着hash值，key, value和指向下一个Entry的引用。

并且重写了equals, hashCode, toString方法。





2.3 构造器分析
    /**
     * 传入初始化容量和加载因子
     */
    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;
        // 根据初始容量构建一个Entry数组
        table = new Entry<?,?>[initialCapacity];
        // 扩容的阈值 initialCapacity * loadFactor与MAX_ARRAY_SIZE + 1较小的值
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

    /**
     * 传入初始化容量，加载因子为0.75
     */
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    /**
     * 无参构造器，初始化容量为11，加载因子为0.75
     */
    public Hashtable() {
        this(11, 0.75f);
    }

    /**
     * 通过一个Map构建一个Hashtable
     */
    public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }
拓展3个问题：

(1) 什么是加载因子，有什么作用？

加载因子是表示Hash表中元素的填满的程度，加载因子越大，填满的元素越多，空间利用率越高，但冲突的机会加大了。反之，加载因子越小，填满的元素越少，冲突的机会减小，但空间浪费多了。

冲突的机会越大，则查找的成本越高。反之，查找的成本越小。

因此,必须在"冲突的机会"与"空间利用率"之间寻找一种平衡与折衷。

(2) 为什么默认的加载因子是0.75f，而不是别的值？

这应该是个经验数字，在Open Hashing中，加载因子选得太大了，访问的时候冲突太多，会降低效率；选得太小了，会浪费大量存储空间。Open Addressing的wikipedia中简略探讨了这个问题。

As the load factor increases towards 100%, the number of probes that may be required to find or insert a given key rises dramatically. Once the table becomes full, probing algorithms may even fail to terminate. Even with good hash functions, load factors are normally limited to 80%.

(3) 哈希冲突怎么破？

1. 开放地址法

Hi=(H(key) + di) MOD m i=1,2,...k(k<=m-1)其中H(key)为哈希函数；m为哈希表表长；di为增量序列。

缺点：

这种方法建立起来的hash表当冲突多的时候数据容易堆聚在一起，这时候对查找不友好；
删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点；
当空间满了，还要建立一个溢出表来存多出来的元素。
2. 再哈希法

Hi = RHi（key），i=1,2,...k
RHi均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到不发生冲突为止。这种方法不易产生聚集，但是增加了计算时间。

缺点：增加了计算时间。

3. 建立一个公共溢出区

假设哈希函数的值域为[0,m-1]，则设向量HashTable[0...m-1]为基本表，每个分量存放一个记录，另设立向量OverTable[0....v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管他们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。

简单地说就是搞个新表存冲突的元素。

4. 链地址法（拉链法）

将所有关键字为同义词的记录存储在同一线性链表中，也就是把冲突位置的元素构造成链表。

拉链法的优点:

拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
拉链法的缺点：

指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使加载因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
Hashtable采用的是链地址法。



2.4 成员方法分析

先看看读方法：

    /**
     * 获取size，加锁
     */
    public synchronized int size() {
        return count;
    }

    /**
     * 是否为空，加锁
     */
    public synchronized boolean isEmpty() {
        return count == 0;
    }

    /**
     * 获取所有key，加锁
     */
    public synchronized Enumeration<K> keys() {
        return this.<K>getEnumeration(KEYS);
    }

    /**
     * 获取所有value，加锁
     */
    public synchronized Enumeration<V> elements() {
        return this.<V>getEnumeration(VALUES);
    }

    /**
     * 是否包含某元素，加锁
     */
    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 ; e != null ; e = e.next) {
                if (e.value.equals(value)) {
                    return true;
                }
            }
        }
        return false;
    }

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

    /**
     * 是否包含某个key，加锁
     */
    public synchronized boolean containsKey(Object key) {
        Entry<?,?> tab[] = table;
        // 先获取key的哈希码
        int hash = key.hashCode();
        // 通过hash值获取元素索引
        int index = (hash & 0x7FFFFFFF) % tab.length;
        // 单链表追踪，如果找到该key则返回true
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 和containsKey原理类似
     */
    @SuppressWarnings("unchecked")
    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;
    }



再来看看写方法：

    /**
     * 存放一个键值对，加锁
     */
    public synchronized V put(K key, V value) {
        // 不允许空值
        if (value == null) {
            throw new NullPointerException();
        }

        Entry<?,?> tab[] = table;
        // key不能为空值，获取hash值
        int hash = key.hashCode();
        // 计算出索引
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        // 先看有没有hash冲突，有的话存入冲突元素的单链表
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
        // 没有冲突的话调用addEntry
        addEntry(hash, key, value, index);
        return null;
    }

    /**
     * 移除一个元素，加锁
     */
    public synchronized V remove(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>)tab[index];
        // 先通过hash值计算索引，定位到该元素
        for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                // 修改数++
                modCount++;
                if (prev != null) {
                    // 单链表改变next索引
                    prev.next = e.next;
                } else {
                    // index位置指向下一个元素
                    tab[index] = e.next;
                }
                // 大小递减1
                count--;
                V oldValue = e.value;
                e.value = null;
                return oldValue;
            }
        }
        return null;
    }

    /**
     * 添加一个entry
     */
    private void addEntry(int hash, K key, V value, int index) {
        modCount++;

        Entry<?,?> tab[] = table;
        // 前面讲过加载因子控制容量，threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1)
        if (count >= threshold) {
            // 超过threshold则rehash
            rehash();

            // 拿到新的table
            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // 创建Entry存入数组
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }

    /**
     * rehash方法，扩容
     */
    @SuppressWarnings("unchecked")
    protected void rehash() {
        int oldCapacity = table.length;
        Entry<?,?>[] oldMap = table;

        // 新的容量 = 旧容量 * 2 + 1
        int newCapacity = (oldCapacity << 1) + 1;
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        // 重新构建数组，采用new的方法而不是arraycopy的方法
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

        modCount++;
        // 重新计算threshold
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;
        // 把旧值copy到新数组中
        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry<K,V> old = (Entry<K,V>)oldMap ; old != null ; ) {
                Entry<K,V> e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = (Entry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }
    }
Tips:

上面我们看到：int index = (hash & 0x7FFFFFFF) % tab.length;

hash值为int 4个字节 32bit.

为了在hash为负值的情况下，去掉起符号位，所以和0x7FFFFFFF进行&操作。

0x7FFFFFFF 二进制 0111 1111 1111 1111 1111 1111 1111 1111

负数与其进行&操作将产生一个正整数。

从上面看，Hashtable不允许存放空key和空value。

同时同步性能，扩容性能，空间复杂度都不太好。

所以一般现在同步散列表一般用ConcurrentHashMap，后面会有一章分析它的源码。
---------------------
【转载，仅作分享，侵删】
作者：况众文
原文：https://blog.csdn.net/u014294681/article/details/85298342
版权声明：本文为博主原创文章，转载请附上博文链接！

---

作者: 不二晨    时间: 2019-2-20 09:38
今天也要加油鸭

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2