JDK源码阅读之Hashtable

Author：带翅膀的猫
发布时间：March 22, 2020
2318views
No comments
6764 words
Categories： JDK源码

在面试时经常将HashMap和Hashtable进行对比，我们已经阅读了HashMap的源代码了，自然不会放过Hashtable的学习。

类前注释

      该类实现了一个哈希表，它将键映射到值。任何非null对象都可以用作键值或值。(说明HashTable的key和value都不能为空，这和HashMap是不同的)
      为了能成功对Hashtable存储和获取对象，作为key的对象必须实现 hashCode和equals方法。
      有两个影响Hashtable实例性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。请注意，哈希表是使用拉链法(open hashing)处理哈希冲突的：在“哈希冲突”的情况下，单个存储桶存储多个条目，必须依次搜索。负载因子是在容量自动增加之前允许哈希表得到满足的度量。初始容量和负载因子参数仅仅是实现的提示。关于何时以及是否调用rehash方法的具体细节是依赖于实现的。

所谓拉链法就是当两个key的hash值相同时，放在同一个桶中。与之对应的 Closed Hashing称为开放地址法，即是因为哈希冲突后，并不会在本身之外开拓新的空间，而是继续顺延下去某个位置来存放，所以是一个密闭的空间，所以叫“Closed”。

      通常，默认负载因子(.75)提供了时间和空间成本之间的良好折衷。更高的值会减少空间开销，但会增加查询条目的时间成本(这反映在大多数Hashtable操作中，包括get和put)。
      初始容量对空间浪费与rehash操作耗时进行了折中。如何hash表元素数量大于初始容量乘加载因子，则需要执行rehash操作。然而，设置初始容量太高可能会浪费空间。
      如果要在哈希表中创建许多条目，则创建一个足够大的容量可能比使表根据需要增长并自动重新哈希处理更有效。(最好是创建确定容量的Hashtable，避免自动增长和rehash。HashMap也是同理)
      如下示例创建一个数字散列表。它使用数字的名称作为键：

Hashtable<String, Integer> numbers = new Hashtable<String, Integer>();
numbers.put("one", 1);
numbers.put("two", 2);
numbers.put("three", 3);

如下获取HashTable中的key对应的值：
Integer n = numbers.get("two");
if (n != null) {
  System.out.println("two = " + n);
}

      由所有这个类的“集合视图方法”调用iterator方法返回的迭代器是快速失败(fail-fast)的：如果Hashtable在迭代器创建之后的任何时间被结构地修改(增，删)，除了通过迭代器自己的remove方法，迭代器会抛出一个ConcurrentModificationException。因此，面对并发修改，迭代器将快速失败，而不是在未来未确定的时间冒着任意的非确定性行为的风险。Hashtable的键和元素方法返回的枚举不是快速失败的。
      请注意，迭代器的快速失败行为无法保证，因为一般来说，在不同步并发修改的情况下，无法做出任何硬性保证。快速失败迭代器尽力抛出ConcurrentModificationException 。因此，编写依赖于此异常的程序的正确性将是错误的：迭代器的快速失败行为应仅用于检测错误。
      与新的集合实现不同，Hashtable是同步的。如果不需要线程安全的实现，建议使用HashMap代替Hashtable。如果需要线程安全的并发实现，那么建议使用ConcurrentHashMap代替Hashtable。

成员变量

//存储Hashtable数据
private transient Entry<?,?>[] table;

//Hashtable中所以entry的个数
private transient int count;

//当Hashtablerehash的阈值(capacity * loadFactor)
private int threshold;

//负载因子，默认为0.75
private float loadFactor;

//记录Hashtable被结构化修改的次数，用于迭代器的快速失败机制
private transient int modCount = 0;

//数组最大分配容量。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

Hashtable将数据存在Entry数组中，所以需要先了解这是一个什么结构。

private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;//key的hash值
    final K key;
    V value;
    Entry<K,V> next;//下一节点的引用

    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 Hashtable() {
    this(11, 0.75f);
}

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;
    table = new Entry<?,?>[initialCapacity];
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}

我们常用无参构造方法创建Hashtable,可以发现默认容量为11。如果往传递一个Map对象则创建的容量为Math.max(2*t.size(), 11)，再使用putAll方法进行添加。

put

put方法是Hashtable中关键。

public synchronized V put(K key, V value) {
    // 确保value是null的，否则抛出NPE
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();//这里隐式设定key为not-null
    /**
     * hash & 0x7FFFFFFF 对负数转正进行了操作，取模获取待插入位置索引
     */
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        //待插入位置处有entry，遍历链表
        if ((entry.hash == hash) && entry.key.equals(key)) {
            //寻找到key相同的值，进行更新操作，返回旧值
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    //待插入位置为空或者链表中也没有相同的key执行addEntry方法
    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
        rehash();
        tab = table;
        hash = key.hashCode();
        //重新计算待插入的index
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    @SuppressWarnings("unchecked")
    //暂存index处的旧entry索引
    Entry<K,V> e = (Entry<K,V>) tab[index];
    //头插法插入新节点
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

rehash

在数组容量达到threshold时需要进行扩容和rehash操作，将自动调用rehash方法，理解此方法是关键。

protected void rehash() {
    //旧容量
    int oldCapacity = table.length;
    //暂存旧table
    Entry<?,?>[] oldMap = table;

    // overflow-conscious code
    //新的容量是旧容量的2倍+1
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        
        if (oldCapacity == MAX_ARRAY_SIZE)
            //旧容量为MAX_ARRAY_SIZE，不能再扩容了，直接返回
            return;
        //新容量大于MAX_ARRAY_SIZE则设置为MAX_ARRAY_SIZE
        newCapacity = MAX_ARRAY_SIZE;
    }
    //根据新容量新建Entry数组
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    //重新计算threshold
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    //旧table指向新table
    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;
            //重新计算key的在新table中的index
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            //头插法插入entry
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

remove

public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    //计算key在table中对应的index
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index];
    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) {
                //前进节点指向后继节点，完成删除
                prev.next = e.next;
            } else {
                //index处即为待删除节点，直接将index处置为后继节点
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            //返回旧值
            return oldValue;
        }
    }
    //table中不存在对应的key，返回null
    return null;
}

Enumerator和Iterator

Hashtable中有两种迭代器：Enumerator和Iterator。但是需要注意的是Enumerator不是快速失败的，在变量过程中进行结构化修改并不会抛ConcurrentModificationException，但是由Collection调用iterator方法返回的Iterator是快速失败的。

Hashtable<String,String> table = new Hashtable<>() ;
table.put("a","1");
table.put("b","2");
table.put("c","3");
table.put("d","4");

Enumeration<String> elements = table.keys();
while (elements.hasMoreElements()){
    String key = elements.nextElement();
    if(key.equals("a")){
        table.remove(key);//成功删除，没抛异常
    }    
}

Iterator<String> iterator = table.keySet().iterator();
while (iterator.hasNext()){
    String next = iterator.next();
    if("a".equals(next)){
        table.remove(next);//抛出ConcurrentModificationException
    }    
}

版权属于：带翅膀的猫
本文链接：https://www.chengpengper.cn/archives/63/
转载时须注明出处及本声明

Last modification：August 6th, 2020 at 07:04 pm

如果觉得我的文章对你有用，请随意赞赏

JDK源码阅读之Hashtable

带翅膀的猫 • 2020 年 03 月 22 日

在面试时经常将HashMap和Hashtable进行对比，我们已经阅读了HashMap的源代码了，自然不会放过Hashtable的学习。

类前注释

所谓拉链法就是当两个key的hash值相同时，放在同一个桶中。与之对应的 Closed Hashing称为开放地址法，即是因为哈希冲突后，并不会在本身之外开拓新的空间，而是继续顺延下去某个位置来存放，所以是一个密闭的空间，所以叫“Closed”。

Hashtable<String, Integer> numbers = new Hashtable<String, Integer>();
numbers.put("one", 1);
numbers.put("two", 2);
numbers.put("three", 3);

如下获取HashTable中的key对应的值：
Integer n = numbers.get("two");
if (n != null) {
  System.out.println("two = " + n);
}

成员变量

//存储Hashtable数据
private transient Entry<?,?>[] table;

//Hashtable中所以entry的个数
private transient int count;

//当Hashtablerehash的阈值(capacity * loadFactor)
private int threshold;

//负载因子，默认为0.75
private float loadFactor;

//记录Hashtable被结构化修改的次数，用于迭代器的快速失败机制
private transient int modCount = 0;

//数组最大分配容量。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

Hashtable将数据存在Entry数组中，所以需要先了解这是一个什么结构。

private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;//key的hash值
    final K key;
    V value;
    Entry<K,V> next;//下一节点的引用

    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 Hashtable() {
    this(11, 0.75f);
}

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;
    table = new Entry<?,?>[initialCapacity];
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}

我们常用无参构造方法创建Hashtable,可以发现默认容量为11。如果往传递一个Map对象则创建的容量为Math.max(2*t.size(), 11)，再使用putAll方法进行添加。

put

put方法是Hashtable中关键。

public synchronized V put(K key, V value) {
    // 确保value是null的，否则抛出NPE
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();//这里隐式设定key为not-null
    /**
     * hash & 0x7FFFFFFF 对负数转正进行了操作，取模获取待插入位置索引
     */
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        //待插入位置处有entry，遍历链表
        if ((entry.hash == hash) && entry.key.equals(key)) {
            //寻找到key相同的值，进行更新操作，返回旧值
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    //待插入位置为空或者链表中也没有相同的key执行addEntry方法
    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
        rehash();
        tab = table;
        hash = key.hashCode();
        //重新计算待插入的index
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    @SuppressWarnings("unchecked")
    //暂存index处的旧entry索引
    Entry<K,V> e = (Entry<K,V>) tab[index];
    //头插法插入新节点
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

rehash

在数组容量达到threshold时需要进行扩容和rehash操作，将自动调用rehash方法，理解此方法是关键。

protected void rehash() {
    //旧容量
    int oldCapacity = table.length;
    //暂存旧table
    Entry<?,?>[] oldMap = table;

    // overflow-conscious code
    //新的容量是旧容量的2倍+1
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        
        if (oldCapacity == MAX_ARRAY_SIZE)
            //旧容量为MAX_ARRAY_SIZE，不能再扩容了，直接返回
            return;
        //新容量大于MAX_ARRAY_SIZE则设置为MAX_ARRAY_SIZE
        newCapacity = MAX_ARRAY_SIZE;
    }
    //根据新容量新建Entry数组
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    //重新计算threshold
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    //旧table指向新table
    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;
            //重新计算key的在新table中的index
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            //头插法插入entry
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

remove

public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    //计算key在table中对应的index
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index];
    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) {
                //前进节点指向后继节点，完成删除
                prev.next = e.next;
            } else {
                //index处即为待删除节点，直接将index处置为后继节点
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            //返回旧值
            return oldValue;
        }
    }
    //table中不存在对应的key，返回null
    return null;
}

Enumerator和Iterator

Hashtable<String,String> table = new Hashtable<>() ;
table.put("a","1");
table.put("b","2");
table.put("c","3");
table.put("d","4");

Enumeration<String> elements = table.keys();
while (elements.hasMoreElements()){
    String key = elements.nextElement();
    if(key.equals("a")){
        table.remove(key);//成功删除，没抛异常
    }    
}

Iterator<String> iterator = table.keySet().iterator();
while (iterator.hasNext()){
    String next = iterator.next();
    if("a".equals(next)){
        table.remove(next);//抛出ConcurrentModificationException
    }    
}

版权属于：带翅膀的猫
本文链接：https://www.chengpengper.cn/archives/63/
转载时须注明出处及本声明

JDK源码阅读之Hashtable

类前注释

成员变量

构造方法

put

rehash

remove

Enumerator和Iterator

Leave a Comment Cancel reply

手机扫码，文章阅读转移功能

Nginx场景实战之跨域访问

JDK源码阅读之Thread

一致性哈希算法

折腾Redis之主从复制

Netty之服务端启动流程

JDK源码阅读之TreeMap

MySql优化之间隙锁的危害

Nginx模块之random_index

JDK源码阅读之Byte

JDK源码阅读之Hashtable

类前注释

成员变量

构造方法

put

rehash

remove

Enumerator和Iterator