当前位置： 首页 > article >正文

java源码阅读 - HashTable

article 2025/1/16 18:51:52

往期文章

  • 用最简单的话讲最明白的红黑树
  • java源码阅读 - HashMap
  • 数据结构 - 堆与堆排序

文章目录

  • 往期文章
  • 一、介绍
  • 二、类的声明
  • 三、底层实现
  • 四、内部类Entry
  • 五、成员变量
  • 六、构造方法
  • 七、扩容方法rehash()
  • 八、addEntry()
  • 九、常用方法
  • 十、总结

一、介绍

在往期文章中，我们从源码分析了java集合框架中Map一族的HashMap，它为我们提供了保存 <key, value>键值对的一系列方法，底层是基于哈希表+链表+红黑树实现的，但是在多线程并发的环境下，表现出线程不安全的特性，今天我们介绍另一个同样是保存 <key, value>键值对但底层是基于哈希表+链表 且 线程安全的HashTable。

下面看一下HashTable的UML图

在这里插入图片描述

二、类的声明

我们来看一下HashMap的声明，可以大致了解他的功能。

public class Hashtable<K,V> extends Dictionary<K,V>
						    implements Map<K,V>, Cloneable, java.io.Serializable
  • 继承了Dictionary类，提供了一些字典相关的基本功能如添加、删除、判空、获取元素数量等。
  • 实现了Map接口，说明HashMap是一个以<K，V>键值对存储数据的结构
  • 实现了Cloneable接口，提供了对象克隆方法，但请注意，是浅克隆。
  • 实现了Serializable接口，支持序列化。

Dictionary类是我们在java集合框架学习过程中首次见到的类，我们看一下他是什么

从下面源码中可以看到，Dictionary是一个抽象类，该类中声明的方法全是抽象方法，没有默认实现，且这些抽象方法在Map接口中都有体现，因此我们可以忽略Dictionary类，将注意点都放在HashTable本身。

另外还需要注意到一个事实，在Dictionary的文档中我们看到，jdk已经建议我们忽略它，并且将用Map接口代替它。

/**
 * NOTE: This class is obsolete. New implementations should implement the Map interface, rather than extending this class.
 *
 **/
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);
}

三、底层实现

HashTable的底层实现为哈希表+链表，相较于底层为哈希表+链表+红黑树实现的HashMap，少了红黑树的结构，因此并没有那么复杂，如下图所示

在这里插入图片描述

四、内部类Entry

在HashTable中，将键值对封装成节点的类为其内部类Entry，该内部类继承于Map接口的内部接口Entry，从上面HashTable的UML图中也有所体现。我们看一下该内部类的源码：

private static class Entry<K,V> implements Map.Entry<K,V> {
    // 键值对节点中key的哈希值
    final int hash;
    // 键值对节点中的key
    final K key;
    // 键值对节点中的value
    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;
    }
}

从源码可以看出，HashTable中保存键值对的节点类Entry其实与HashMap中保存键值对的节点类Node是完全相同的。

五、成员变量

// 哈希表中的数组
private transient Entry<?,?>[] table;
// 哈希表中键值对节点数量
private transient int count;
// 扩容阈值
private int threshold;
// 加载因子，默认0.75
private float loadFactor;
// 结构性修改次数，用于快速失败
private transient int modCount = 0;

六、构造方法

HashMap提供了以下四个构造方法来创建实例

  • 无参构造

    通过默认初始容量11 和 默认加载因子为0.75 构造实例

    public Hashtable() {
    this(11, 0.75f);
}

  • 指定初始容量和加载因子

    对指定的初始容量和加载因子进行校验后，设置初始容量大小的数组和加载因子，并计算出扩容阈值。

    还记得在HashMap中，数组和扩容阈值都是在第一次扩容时初始化的。而在HashTable中，取消了这种延时初始化。

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

  • 指定初始容量

    指定初始容量，并使用默认的加载因子0.75。

    public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}

  • 通过传入一个Map对象实例化

    通过这种方式构造HashTable实例时，会先创建实例，再调用putAll()方法将map中的数据批量保存到实例中。

    注意：在构造HashTable实例时，初始容量为 map容量*2+1 和 默认初始容量11的较小值，

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

七、扩容方法rehash()

该方法的源码如下，相较于HashMap那么长的扩容resize()方法，是否简单了一点呢？在HashMap的扩容resize()方法中，还要一堆判断去确定数组容量、扩容阈值等信息，而且由于HashMap中数组长度为2的n次方，还需要判断哪些键值对在扩容前后的数组下标是否不变等等。

而在HashTable中，由于在扩容前哈希表就已经完成初始化了，且由于哈希表数组长度可能为任意值，也不存在扩容后键值对位于数组的下标不变的情况，因此，简单粗暴的，直接扩容，然后将原哈希表中的键值对重新计算数组下标，放在扩容后的哈希表中。

要注意一点：在HashMap中，原哈希表中链表上的元素采用尾插法放在新哈希表。而在HashTable中采用的是头插法。

protected void rehash() {
    // 扩容前的哈希数组容量
    int oldCapacity = table.length;
    // 扩容前的哈希数组
    Entry<?,?>[] oldMap = table;

    // 1.计算扩容后的容量，新容量= 原容量*2 +1
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    // 2. 遍历原哈希表，将原哈希表中的键值对重新计算数组下标后，通过头插法，放至新的哈希表中。
    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;
            // 头插法
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

八、addEntry()

该方法采用头插法的方式向哈希表中添加元素，在添加元素前，判断是否需要先调用rehash()方法进行扩容。

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

有一点需要注意，HashTable不像HashMap那样对hashcode()值的高16位和低16位按位与得到hash值，再对数组长度取余，从而得到数组下标，而是直接通过** hashcode()值与 0x7FFFFFFF 按位与，在对数组长度取余，从而得到数组下标**。

我们分析一下index = (hash & 0x7FFFFFFF) % tab.length

0x7FFFFFFF为16进制表示法，换成2进制为：0111 1111 1111 1111 1111 1111 1111 1111共32位，其中最高位为0，而我们知道，在二进制表示中，最高位为0表示正数，1表示负数，因此(hash & 0x7FFFFFFF)表示将key的hashcode()值的最高位设置为0，解决了key的hashcode()值为负数的情况，再对数组长度取余，便可得到数组下标。

九、常用方法

  • size()

    获取哈希表中键值对节点的数量。该方法被synchronized修饰，表示线程安全

    public synchronized int size() {
    return count;
}

  • isEmpty()

    判断哈希表中是否不存在键值对，该方法被synchronized修饰，表示线程安全

    public synchronized boolean isEmpty() {
    return count == 0;
}

  • contains() 与 containsValue()

    判断哈希表中是否存在指定的value，遍历方式与HashMap相同，该方法被synchronized修饰，表示线程安全

    从方法首行的判空语句可知，HashTable中不允许value值为空

    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[i] ; e != null ; e = e.next) {
            if (e.value.equals(value)) {
                return true;
            }
        }
    }
    return false;
}

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

  • containsKey()

    判断哈希表中是否存在指定的key，遍历方式与HashMap相同，该方法被synchronized修饰，表示线程安全

    从方法第二行int hash = key.hashCode();来看，HashTable中不允许key值为空，否则会抛出空指针异常。

    逻辑与HashMap相同，都是先通过计算哈希值确认哈希表中数组的下标，再通过遍历链表的形式，查找是否存在键值对的key与指定的key相同。

    public synchronized boolean containsKey(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 true;
        }
    }
    return false;
}

  • get()

    根据指定的key，从哈希表中获取该key对应的value，遍历方式与HashMap相同，该方法被synchronized修饰，表示线程安全

    public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    // 计算哈希值确认哈希表中数组的下标
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // 遍历链表，查找到相同的key的键值对，并返回该键值对的value
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

  • put()

    将指定的 <key, value> 键值对保存，该方法被synchronized修饰，表示线程安全

    从方法首行的判空语句可知，HashTable中不允许value值为空。

    public synchronized V put(K key, V value) {
    // 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;
    // 根据参数key计算出对应的数组下标
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // 对该数组下标上的链表进行遍历，如果存在key相等的键值对，则对其对应的value值进行覆盖
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            // 覆盖value
            entry.value = value;
            return old;
        }
    }

    // 如果不存在key相等的键值对，则调用addEntry()方法通过头插法保存键值对
    addEntry(hash, key, value, index);
    return null;
}

  • remove()

    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];
    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 {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}

十、总结

  • 底层结构为数组+单链表实现的哈希表

  • 当出现哈希冲突或扩容，且当前位置为链表时，采用尾插法将节点插入到链表

  • 插入的数据是无序的

  • 线程安全

  • 保存键值对节点的类为Entry，而HashMap中保存键值对节点的类为Node

  • 哈希表数组默认初始容量为11，默认加载因子为0.75

  • 哈希表数组的容量可任意指定，扩容后的容量 为 扩容前容量*2 + 1

  • 哈希表和扩容阈值在构造方法中完成初始化，是即时加载而不是延时初始化

  • key和value都不允许为空，在HashMap中为key和value都允许为空。

  • HashTable的扩容方法为rehash()，HashMap的扩容方法为resize()

  • 先扩容，后插入。在HashMap中为先插入后扩容。



纸上得来终觉浅，绝知此事要躬行。

————————————————我是万万岁，我们下期再见————————————————


http://www.kler.cn/a/4482.html

相关文章：

  • 在AI智能中有几种重要的神经网络类型？6种重要的神经网络类型分享！
  • 怎样利用海外云手机进行引流？
  • Java 锁
  • HTML实战课堂之启动动画弹窗
  • SQL面试题1：连续登陆问题
  • day08_Kafka
  • 提升代码可读性，减少 if-else 的几个小技巧
  • 合泰HT32单片机使用PDMA和ADC采集多路模拟值并显示在OLED屏上
  • Vue+springboot笔记本电脑商城销售系统
  • 校招失败后，在外包公司熬了 2 年终于进了字节跳动，竭尽全力....
  • python Django运用——（1.创立项目）
  • 进程与线程的关系
  • 【协议】03、深度解剖之HTTP协议
  • leetcode 有序数组的平方(977)
  • （四）Tomcat源码阅读：Service组件分析
  • 垃圾回收机制——把我回收了吧
  • 我的黑苹果安装经验
  • 深入浅出Java线程池Worker类
  • Java Web的三种获取参数的方法
  • Linux部署Docker
  • 分组函数·union·limit·order by排序·group by分组·外键
  • 面试字节跳动软件测试岗，收到offer后我却毫不犹豫拒绝了....
  • day15-面向对象作业2
  • 常用的 IntelliJ IDEA 快捷键
  • Element Plus 实例详解（三）___Date Picker 日期选择
  • 大数据应用——Hadoop运行模式（本地运行）