Java 集合 - HashTable 解析

2024-05-11 00:38
文章标签 java 解析 集合 hashtable

本文主要是介绍Java 集合 - HashTable 解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、前言


Hashtable 与 HashMap 都是 Map 族中较为常用的实现,也都是 Java Collection Framework 的重要成员,它们的本质都是 链表数组。下面我们来学习一下 HashTable。

 

二、HashTable 解析


2.1 定义

Hashtable 和 HashMap 既是 Java Collection Framework 的重要成员,也是 Map 族(如下图所示)的核心成员,二者的底层实现都是一个链表数组,具有寻址容易、插入和删除也容易的特性。事实上 HashMap 几乎可以等价于 Hashtable,除了 HashMap 是非线程安全的并且可以接受 null 键和 null 值。关于 HashMap 可以看我之前的 Java 集合 - HashMap 解析。

 Hashtable 实现了 Map 接口,并继承 Dictionary 抽象类 (已过时,新的实现应该实现 Map 接口而不是扩展此类),其在 JDK 中的定义为:

public class Hashtable<K,V> extends Dictionary<K,V>implements Map<K,V>, Cloneable, java.io.Serializable {private transient Entry[] table;   // 由Entry对象组成的链表数组private transient int count;   // Hashtable中Entry对象的个数private int threshold;   // Hashtable进行扩容的阈值private float loadFactor;   // 在其容量自动增加之前可以达到多满的一种尺度,默认为0.75private transient int modCount = 0;   // 记录Hashtable生命周期中结构性修改的次数
...
}

与 HashMap 类似,Hashtable 也包括五个成员变量,分别是 table 数组、Hashtable 中 Entry 个数 count、Hashtable 的阈值 threshold、Hashtable 的负载因子 loadFactor 和 Hashtable 结构性修改次数 modCount。下面分别给出这五个成员的具体内涵:

  • Entry 数组 table: 一个由 Entry 对象组成的链表数组,table 数组的每一个数组成员就是一个链表;
  • Entry 个数 count: Hashtable 中 Entry 对象的个数;
  • 阈值 threshold: Hashtable 进行扩容的阈值;
  • 负载因子 loadFactor: 在其容量自动增加之前可以达到多满的一种尺度,默认为0.75;
  • 结构性修改次数 modCount: 记录 Hashtable 生命周期中结构性修改的次数,便于快速失败(所谓快速失败是指其在并发环境中进行迭代操作时,若其他线程对其进行了结构性的修改,这时迭代器能够立马感知到并且立即抛出 ConcurrentModificationException 异常,而不是等到迭代完成之后才告诉你(你已经出错了));

2.2 构造函数

Hashtable 一共提供了四个构造函数,其中默认无参的构造函数和参数为Map的构造函数为 Java Collection Framework 规范的推荐实现,其余两个构造函数则是Hashtable专门提供的。

1、Hashtable(int initialCapacity, float loadFactor)

  该构造函数意在构造一个指定初始容量和指定负载因子的空 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;  // 初始容量完全由用户随意指定,不必是2的n次幂(不同于HashMap)this.loadFactor = loadFactor;  table = new Entry[initialCapacity];   // 创建指定大小为initialCapacity的链表数组threshold = (int) (initialCapacity * loadFactor);   // HashTable的扩容阈值}

2、Hashtable()

  该构造函数意在构造一个具有默认初始容量(11)和默认负载因子(0.75f)的空 Hashtable,是 Java Collection Framework 规范推荐提供的,其源码如下:

    public Hashtable() {this(11, 0.75f);   // 默认容量是11,不同于HashMap的默认初始容量16,默认负载因子0.75}

3、Hashtable(int initialCapacity)

  该构造函数意在构造一个指定初始容量和默认负载因子(0.75f)的空 Hashtable,其源码如下:

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

4、Hashtable(Map<? extends K, ? extends V> t)

  该构造函数意在构造一个与指定 Map 具有相同映射的 Hashtable,其初始容量不小于11(具体依赖于指定Map的大小),负载因子是0.75f,是 Java Collection Framework 规范推荐提供的,其源码如下:

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

与 HashMap 类似,构建一个 Hashtable 时也需要指定初始容量和负载因子这两个非常重要的参数,它们是影响 Hashtable 性能的关键因素。其中,容量表示哈希表中桶的数量(table 数组的大小),初始容量是创建哈希表时桶的数量;负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,它衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。

对于 Hashtable 而言,查找一个元素的平均时间是 O(1+a) (a 指的是链的长度,是一个常数)。特别地,负载因子越大,对空间的利用更充分,但查找效率的也就越低;若负载因子越小,那么哈希表的数据将越稀疏,对空间造成的浪费也就越严重。系统默认负载因子为0.75f,这是时间和空间成本上一种折衷,一般情况下我们是无需修改的。

2.3 Hashtable 的数据结构

我们知道,在 Java 中最常用的两种结构是数组和链表,其中数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。Hashtable 和 HashMap 综合了两者的特性,是一种寻址容易、插入和删除也容易的数据结构。实际上,Hashtable 和 HashMap 本质上都是一个链表数组。数组中存放的元素是 Entry 对象,而 Entry 对象是一种典型链状结构,定义如下:

static class Entry<K,V> implements Map.Entry<K,V> {K key;     // 键值对的键V value;        // 键值对的值Entry<K,V> next;     // 指向下一个节点的指针int hash;     // key 的哈希值(与HashMap中key的哈希值计算方式不同)/*** Creates new entry.*/protected Entry(int h, K k, V v, Entry<K,V> n) {     // Entry 的构造函数value = v;next = n;key = k;hash = h;}......
}

Entry 为 Hashtable 的内部类,实现了 Map.Entry 接口,是个典型的四元组,包含了键 key、值 value、指向下一个节点的指针 next,以及 Key 的 hash 值四个属性。事实上 Entry 是构成哈希表的基石,是哈希表所存储的元素的具体形式。

2.4 Hashtable 的快速存取

我们知道,在 HashMap 中,最常用的两个操作就是:put(Key,Value) 和 get(Key)。同样地,这两个操作也是 Hashtable 最常用的两个操作。下面我们结合 JDK 源码看 Hashtable 的存取实现。

1、Hashtable 的存储实现 put(key, vlaue)

  在Hashtable中,键值对的存储是也是通过 put(key, vlaue) 方法来实现的,不同于 HashMap 的是,其 put 操作是线程安全的,源码如下:

    public synchronized V put(K key, V value) {     // 加锁同步,保证Hashtable的线程安全性// Make sure the value is not nullif (value == null) {      // 不同于HashMap,Hashtable不允许空的valuethrow new NullPointerException();}// Makes sure the key is not already in the hashtable.Entry tab[] = table;int hash = key.hashCode();   // key 的哈希值,同时也暗示Hashtable不同于HashMap,其不允许空的keyint index = (hash & 0x7FFFFFFF) % tab.length;   // 取余计算节点存放桶位,0x7FFFFFFF 是最大的int型数的二进制表示// 先查找Hashtable上述桶位中是否包含具有相同Key的K/V对for (Entry<K, V> e = tab[index]; e != null; e = e.next) {if ((e.hash == hash) && e.key.equals(key)) {V old = e.value;e.value = value;return old;}}// 向Hashtable中插入目标K/V对modCount++;     // 发生结构性改变,modCount加1if (count >= threshold) {    //在插入目标K/V对前,先检查是否需要扩容(不同于HashMap的插入后检查是否需要扩容) // Rehash the table if the threshold is exceededrehash();tab = table;index = (hash & 0x7FFFFFFF) % tab.length;   // 扩容后,重新计算K/V对插入的桶位}// Creates the new entry.Entry<K, V> e = tab[index];tab[index] = new Entry<K, V>(hash, key, value, e); // 将K/V对链入对应桶中链表,并成为头结点count++;     // Hashtable中Entry数目加1return null;}

通过上述源码我们可以看出,Hashtable 与 HashMap 保存数据的过程基本相同:首先,计算 key 的 hash 值并确定 K/V 对要插入的桶位;其次,查找该桶位中是否存在具有相同的 key 的 K/V 对,若存在则覆盖直接对应的 value 值,否则将该节点(K/V)保存在桶中的链表的链头位置(最先保存的元素放在链尾)。当然,若该桶位是空的,则直接保存。特别地,在一些细节上,Hashtable 与 HashMap 还是有一定的差别的:

  • Hashtable不同于HashMap,前者既不允许key为null,也不允许value为null;
  • HashMap中用于定位桶位的Key的hash的计算过程要比Hashtable复杂一点,没有Hashtable如此简单、直接;
  • 在HashMap的插入K/V对的过程中,总是先插入后检查是否需要扩容;而Hashtable则是先检查是否需要扩容后插入;
  • Hashtable不同于HashMap,前者的put操作是线程安全的。

2、Hashtable 的重哈希操作 rehash()

重哈希过程主要是一个重新计算原 Hashtable 中的元素在新 table 数组中的位置并进行复制处理的过程,我们直接看其源码:

    protected void rehash() {int oldCapacity = table.length;   // 先获取旧的Hashtable桶的数量,即容量Entry[] oldMap = table;int newCapacity = oldCapacity * 2 + 1;    // 扩容,扩到原始容量的2倍再加1Entry[] newMap = new Entry[newCapacity];   // 创建扩容后的新的链表数组modCount++;                // 重哈希操作是一个结构性改变操作,modCount加1threshold = (int) (newCapacity * loadFactor);   // 新的阈值   table = newMap;// 将原哈希表中的节点逐个复制到新的哈希表中for (int i = oldCapacity; i-- > 0;) {for (Entry<K, V> old = oldMap[i]; old != null;) {Entry<K, V> e = old;old = old.next;int index = (e.hash & 0x7FFFFFFF) % newCapacity;e.next = newMap[index];newMap[index] = e;}}}

特别需要注意的是,在重哈希的过程中,原属于同一个桶中的 Entry 对象可能会被分到不同的桶,因为 Hashtable 的容量发生了变化,那么(e.hash & 0x7FFFFFFF) % newCapacity 的值也会发生相应的变化。退一步说,如果重哈希后原属于一个桶中的 Entry 对象仍属于同一桶,那么重哈希也就失去了意义。

3、Hashtable 的读取实现

相对于 Hashtable 的存储操作而言,读取就显得比较简单了。因为 Hashtable 只需通过 key 的 hash 值定位到 table 数组的某个特定的桶,然后查找并返回该 key 对应的 value 即可,源码如下:

    public synchronized V get(Object key) {    // 不同于HashMap,Hashtable的读取操作是同步的Entry tab[] = table;int hash = key.hashCode();   int index = (hash & 0x7FFFFFFF) % tab.length;   // 定位K/V对的桶位for (Entry<K, V> e = tab[index]; e != null; e = e.next) {   // 在特定桶中依次查找指定Key的K/V对if ((e.hash == hash) && e.key.equals(key)) {return e.value;       }}return null;   // 查找失败}

在这里能够根据 key 快速的取到 value,除了和 Hashtable 的数据结构密不可分外,还和 Entry 有莫大的关系。在前面就已经提到过,Hashtable 在存储过程中并没有将 key,value 分开来存储,而是当做一个整体 Entry 对象(四元组)来处理的。可以看到,在 Entry 对象中,value 的地位要比 key 低一些,相当于是 key 的附属。在读取细节上,Hashtable 与 HashMap 的主要差别如下:

  • 不同于 HashMap,Hashtable 的读取操作是同步的;
  • 在 HashMap 中,若读取到的 Value 值为 NULL,则存在如下两种可能:该 key 对应的值就是 null 或者 HashMap 中不存在该 key;而在 Hashtable 中却只有一种可能:Hashtable 中不存在含有该 key 的 Entry。造成这种差别的原因正是二者对 Key 和 Value 的限制的不同:HashMap 最多允许一个 Key 为 null,但允许多个 value 值为 null;Hashtable 既不允许空的 Key,也不允许空的 Value。

 

三. HashMap、Hashtable 与 ConcurrentHashMap 的联系与区别

3.1 Hashtable 与 HashMap 的联系与区别

  (1) HashMap 和 Hashtable 的实现模板不同:虽然二者都实现了 Map 接口,但 HashTable 继承于 Dictionary 类,而 HashMap 是继承于 AbstractMap。Dictionary 是是任何可将键映射到相应值的类的抽象父类,而 AbstractMap 是基于 Map 接口的骨干实现,它以最大限度地减少实现此接口所需的工作。

  (2) HashMap 和 Hashtable 对键值的限制不同:HashMap 可以允许存在一个为 null 的 key 和任意个为 null 的 value,但是 HashTable 中的 key 和 value 都不允许为 null。

  (3) HashMap和Hashtable的线程安全性不同:Hashtable 的方法是同步的,实现线程安全的 Map;而 HashMap 的方法不是同步的,是Map的非线程安全实现。

  (4) HashMap 和 Hashtable 的地位不同:在并发环境下,Hashtable 虽然是线程安全的,但是我们一般不推荐使用它,因为有比它更高效、更好的选择 ConcurrentHashMap;而单线程环境下,HashMap 拥有比 Hashtable 更高的效率(Hashtable的操作都是同步的,导致效率低下),所以更没必要选择它了。

3.2 Hashtable 与 ConcurrentHashMap 的联系与区别

  Hashtable 和 ConcurrentHashMap 都可以用于并发环境,但是 Hashtable 的并发性能远不如 ConcurrentHashMap,这种差异是由它们的底层实现决定的。我们知道 ConcurrentHashMap 引入了分段锁机制,在默认理想状态下,ConcurrentHashMap 可以支持16个线程执行并发写操作及任意数量线程的读操作;而 Hashtable 无论在读的过程中还是写的过程中都会锁定整个 map,因此在并发效率上远不如ConcurrentHashMap。此外,Hashtable 和 ConcurrentHashMap 对键值的限制相同,二者的 key 和 value 都不允许是 null。

这篇关于Java 集合 - HashTable 解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/978019

相关文章

如何用java对接微信小程序下单后的发货接口

《如何用java对接微信小程序下单后的发货接口》:本文主要介绍在微信小程序后台实现发货通知的步骤,包括获取Access_token、使用RestTemplate调用发货接口、处理AccessTok... 目录配置参数 调用代码获取Access_token调用发货的接口类注意点总结配置参数 首先需要获取Ac

Java逻辑运算符之&&、|| 与&、 |的区别及应用

《Java逻辑运算符之&&、||与&、|的区别及应用》:本文主要介绍Java逻辑运算符之&&、||与&、|的区别及应用的相关资料,分别是&&、||与&、|,并探讨了它们在不同应用场景中... 目录前言一、基本概念与运算符介绍二、短路与与非短路与:&& 与 & 的区别1. &&:短路与(AND)2. &:非短

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente

什么是 Java 的 CyclicBarrier(代码示例)

《什么是Java的CyclicBarrier(代码示例)》CyclicBarrier是多线程协同的利器,适合需要多次同步的场景,本文通过代码示例讲解什么是Java的CyclicBarrier,感... 你的回答(口语化,面试场景)面试官:什么是 Java 的 CyclicBarrier?你:好的,我来举个例

Java使用Mail构建邮件功能的完整指南

《Java使用Mail构建邮件功能的完整指南》JavaMailAPI是一个功能强大的工具,它可以帮助开发者轻松实现邮件的发送与接收功能,本文将介绍如何使用JavaMail发送和接收邮件,希望对大家有所... 目录1、简述2、主要特点3、发送样例3.1 发送纯文本邮件3.2 发送 html 邮件3.3 发送带

Java实现数据库图片上传功能详解

《Java实现数据库图片上传功能详解》这篇文章主要为大家详细介绍了如何使用Java实现数据库图片上传功能,包含从数据库拿图片传递前端渲染,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、前言2、数据库搭建&nbsChina编程p; 3、后端实现将图片存储进数据库4、后端实现从数据库取出图片给前端5、前端拿到

Java实现将byte[]转换为File对象

《Java实现将byte[]转换为File对象》这篇文章将通过一个简单的例子为大家演示Java如何实现byte[]转换为File对象,并将其上传到外部服务器,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言1. 问题背景2. 环境准备3. 实现步骤3.1 从 URL 获取图片字节数据3.2 将字节数组

Java捕获ThreadPoolExecutor内部线程异常的四种方法

《Java捕获ThreadPoolExecutor内部线程异常的四种方法》这篇文章主要为大家详细介绍了Java捕获ThreadPoolExecutor内部线程异常的四种方法,文中的示例代码讲解详细,感... 目录方案 1方案 2方案 3方案 4结论方案 1使用 execute + try-catch 记录

SpringBoot接收JSON类型的参数方式

《SpringBoot接收JSON类型的参数方式》:本文主要介绍SpringBoot接收JSON类型的参数方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、jsON二、代码准备三、Apifox操作总结一、JSON在学习前端技术时,我们有讲到过JSON,而在

Spring-AOP-ProceedingJoinPoint的使用详解

《Spring-AOP-ProceedingJoinPoint的使用详解》:本文主要介绍Spring-AOP-ProceedingJoinPoint的使用方式,具有很好的参考价值,希望对大家有所帮... 目录ProceedingJoinPoijsnt简介获取环绕通知方法的相关信息1.proceed()2.g