吃透Java集合系列十:HashTable

2024-09-03 01:48

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

一:整体实现

  • HashTable和HashMap实现大致相同,都是基于哈希表来实现的,数组+链表的形式(和HashMap有稍微的区别,HashMap加入了红黑树),它存储的内容是键值对(key-value)映射。
  • Hashtable 继承于Dictionary,实现了Map、Cloneable、java.io.Serializable接口。Dictionary是一个过时的键值对映射的抽象类,jdk已经不建议使用,新的实现应该实现Map接口,而不是扩展这个类。
  • HashTable方法加了synchronized关键字,所以是线程安全的。

二:重要字段

private transient Entry<?,?>[] table;
private transient int count;
private int threshold;
private float loadFactor;
private transient int modCount = 0;

table实现哈希表的数组结构,数组长度最小为1,默认为11,里面存储着Entry

private static class Entry<K,V> implements Map.Entry<K,V> {final int hash;//哈希值,用于定位数组索引位置final K key;//键V value;//值Entry<K,V> next;//链表下一个元素}

Entry是HashTable的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对)。

count是HashTable中实际存在的键值对数量,而modCount字段主要用来记录HashTable内部结构发生变化的次数,主要用于迭代的快速失败。强调一点,内部结构发生变化指的是结构发生变化,例如put新键值对,但是某个key对应的value值被覆盖不属于结构变化。

loadFactor为负载因子(默认值是0.75),threshold是HashTable所能容纳的最大数据量的Entry(键值对)个数。threshold = length * loadFactor。也就是说,在数组定义好长度之后,负载因子越大,所能容纳的键值对个数越多。

threshold就是在此loadFactor和length(数组长度)对应下允许的最大元素数目,超过这个数目就重新rehash(扩容),扩容后的HashTable容量是之前容量的两倍+1。默认的负载因子0.75是对空间和时间效率的一个平衡选择,建议不要修改,除非在时间和空间比较特殊的情况下,如果内存空间很多而又对时间效率要求很高,可以降低负载因子loadFactor的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子loadFactor的值,这个值可以大于1。

三:扩容机制

当前键值对的数量count >= threshold时会触发扩容。

protected void rehash() {int oldCapacity = table.length;Entry<?,?>[] oldMap = table;//新容量=旧容量 * 2 + 1int newCapacity = (oldCapacity << 1) + 1;if (newCapacity - MAX_ARRAY_SIZE > 0) {if (oldCapacity == MAX_ARRAY_SIZE)// Keep running with MAX_ARRAY_SIZE bucketsreturn;newCapacity = MAX_ARRAY_SIZE;}//新建一个size = newCapacity的数组Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];modCount++;//重新计算阀值threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);table = newMap;//将原来的元素拷贝到新的HashTable中,对数组链表数据进行重新 hash index 计算,//rehash之后会使得最早插入的数据回到链表的第一位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;}}}

在这个rehash()方法中我们可以看到容量扩大两倍+1,同时需要将原来HashTable中的元素一一复制到新的HashTable中,并且对每个元素根据hash值从新计算下标,这个过程是比较消耗时间的。

四:put方法

put方法的整个处理流程:计算key的hash值,根据hash值获得key在table数组中的索引位置,然后迭代该key处的Entry链表(我们暂且理解为链表),若该链表中存在一个这个的key对象,那么就直接替换其value值即可,否则在将改key-value节点插入该index索引位置处

public synchronized V put(K key, V value) {// 值不能为空if (value == null) {throw new NullPointerException();}//计算key的hash值,确认在table[]中的索引位置Entry<?,?> tab[] = table;int hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")Entry<K,V> entry = (Entry<K,V>)tab[index];//迭代index索引位置,如果该位置处的链表中存在一个一样的key,则替换其value,返回旧值for(; entry != null ; entry = entry.next) {if ((entry.hash == hash) && entry.key.equals(key)) {V old = entry.value;entry.value = value;return old;}}//如果不存在,则创建entry加入hash表中addEntry(hash, key, value, index);return null;}
//在指定索引位置加入key-value键值对
private void addEntry(int hash, K key, V value, int index) {modCount++;Entry<?,?> tab[] = table;//如果当前元素的数量大于等于阈值,则触发扩容if (count >= threshold) {// Rehash the table if the threshold is exceededrehash();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++;}

五:get方法

get方法比较简单,处理过程就是计算key的hash值,判断在table数组中的索引位置,然后迭代链表,匹配直到找到相对应key的value,若没有找到返回null。

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

六:HashTable和HashMap区别

  • HashMap线程不安全,HashTable是线程安全的。HashMap内部实现没有任何线程同步相关的代码,所以相对而言性能要好一点。如果在多线程中使用HashMap需要自己管理线程同步。HashTable大部分对外接口都使用synchronized包裹,所以是线程安全的,但是性能会相对差一些。
  • 二者的基类不一样。HashMap派生于AbstractMap,HashTable派生于Dictionary。它们都实现Map, Cloneable, Serializable这些接口。AbstractMap中提供的基础方法更多,并且实现了多个通用的方法,而在Dictionary中只有少量的接口,并且都是abstract类型。
  • key和value的取值范围不同。HashMap的key和value都可以为null,但是HashTable key和value都不能为null。对于HashMap如果get返回null,并不能表明HashMap不存在这个key,如果需要判断HashMap中是否包含某个key,就需要使用containsKey这个方法来判断。
  • 算法不一样。HashMap的initialCapacity为16,而HashTable的initialCapacity为11。HashMap中初始容量必须是2的幂,如果初始化传入的initialCapacity不是2的幂,将会自动调整为大于出入的initialCapacity最小的2的幂。HashMap使用自己的计算hash的方法(会依赖key的hashCode方法),HashTable则使用key的hashCode方法得到。

这篇关于吃透Java集合系列十:HashTable的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》:本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中,封装多线程的原理主要围绕着将多线程相关的操

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

Spring Cloud之注册中心Nacos的使用详解

《SpringCloud之注册中心Nacos的使用详解》本文介绍SpringCloudAlibaba中的Nacos组件,对比了Nacos与Eureka的区别,展示了如何在项目中引入SpringClo... 目录Naacos服务注册/服务发现引⼊Spring Cloud Alibaba依赖引入Naco编程s依

java导出pdf文件的详细实现方法

《java导出pdf文件的详细实现方法》:本文主要介绍java导出pdf文件的详细实现方法,包括制作模板、获取中文字体文件、实现后端服务以及前端发起请求并生成下载链接,需要的朋友可以参考下... 目录使用注意点包含内容1、制作pdf模板2、获取pdf导出中文需要的文件3、实现4、前端发起请求并生成下载链接使

Java springBoot初步使用websocket的代码示例

《JavaspringBoot初步使用websocket的代码示例》:本文主要介绍JavaspringBoot初步使用websocket的相关资料,WebSocket是一种实现实时双向通信的协... 目录一、什么是websocket二、依赖坐标地址1.springBoot父级依赖2.springBoot依赖

如何用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?你:好的,我来举个例