Java容器HashMap与HashTable详解
作者:siqq 发布时间:2022-03-05 19:25:00
1、HashMap
HashMap继承抽象类AbstractMap,实现接口Map、Cloneable, Serializable接口。HashMap是一种以键值对存储数据的容器,
由数组+链表组成,其中key和value
都可以为空,key的值唯一。HashMap
是非线程安全的, 对于键值对<Key,Value>,
HashMap内部会将其封装成一个对应的Entry<Key,Value>
对象。HashMap的存储空间大小是可以动态改变的:
存储过程
每个对象都有一个对应的HashCode
值,根据HashCode值,调用hash函数,计算出一个hash值,根据该hash值调用indexFor函数,计算出在table中的存储位置,如果该位置已经有值,则存储在该位置对应的桶中。
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
public final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue())
}
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
获取值
首先根据key的HashCode码计算出hash值,然后调用indexFor函数计算该entry对象在table中的存储位置,遍历该位置对应桶中存储的entry对象,如果存在对象的hash值和key与要查找的相同,则返回该对象。
public final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
两map相等的判断
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
自反性:对于任何非空引用值 x,x.equals(x) 都应返回 true。
对称性:对于任何非空引用值 x 和 y,当且仅当 y.equals(x) 返回 true 时,x.equals(y) 才应返回 true。
传递性:对于任何非空引用值 x、y 和 z,如果 x.equals(y) 返回 true,并且 y.equals(z) 返回
true,那么 x.equals(z) 应返回 true。
一致性:对于任何非空引用值 x 和 y,多次调用 x.equals(y) 始终返回 true 或始终返回 false,前提是对象上
equals 比较中所用的信息没有被修改。
对于任何非空引用值 x,x.equals(null) 都应返回 false。
存储空间动态分配
HashMap
的桶数目,即Entry[] table
数组的长度,由于数组是内存中连续的存储单元,它的空间代价是很大的,但是它的随机存取的速度是Java
集合中最快的。我们增大桶的数量,而减少Entry<Key,Value>
链表的长度,来提高从HashMap中读取数据的速度。这是典型的拿空间换时间的策略。
但是我们不能刚开始就给HashMap
分配过多的桶(即Entry[] table
数组起始不能太大),这是因为数组是连续的内存空间,它的创建代价很大,况且我们不能确定给HashMap分配这么大的空间,它实际到底能够用多少,为了解决这一个问题,HashMap采用了根据实际的情况,动态地分配桶的数量。
要动态分配桶的数量,这就要求要有一个权衡的策略了,HashMap的权衡策略是这样的:
如果 HashMap的大小 > HashMap的容量(即Entry[] table的大小)*加载因子(经验值0.75)
则 HashMap中的Entry[] table 的容量扩充为当前的一倍;然后重新将以前桶中的`Entry<Key,Value>`链表重新分配到各个桶中
上述的 HashMap的容量(即Entry[] table的大小) * 加载因子(经验值0.75)就是所谓的阀值(threshold)。
2、HashTable
HashTable继承Dictionary类,实现Map, Cloneable,Serializable接口,不允许key为空,采用拉链法实现与HashMap类似。
HashTable是线程安全的(但是在Collections类中存在一个静态方法:synchronizedMap(),该方法创建了一个线程安全的Map对象,通过该方法我们可以同步访问潜在的HashMap,对整个map对象加锁。CurrentHashMap是线程安全的,并且只对桶加锁,不会影响map对象上其它桶的操作)。
希望本文对各位朋友有所帮助
来源:http://blog.csdn.net/si136339327/article/details/70161834
猜你喜欢
- 前言CompletableFuture实现了CompletionStage接口和Future接口,前者是对后者的一个扩展,增加了异步回调、流
- 1、自定义消息转换器MessageConverter在WebMvcAutoConfiguration类中有一个方法configureMess
- 一、BufferedImage类介绍生成验证码图片主要用到了一个BufferedImage类,如下:创建一个DrawImage Servle
- 前言JDK 1.5 之前 synchronized 的性能是比较低的,但在 JDK 1.5 中,官方推出一个重量级功能 Lock,一举改变了
- 一:什么是SparkSQL?(一)SparkSQL简介Spark SQL是Spark的一个模块,用于处理结构化的数据,它提供了一个数据抽象D
- 前言古语有云:道为术之灵,术为道之体;以道统术,以术得道。其中:“道”指“规律、道理、理论”,“术”指“方法、技巧、技术”。意思是:“道”是
- 本文实例讲述了Java泛型类与泛型方法的定义。分享给大家供大家参考,具体如下:Java泛型类的定义一 点睛泛型类定义的语法如下:[访问修饰符
- 本文以实例形式详细讲述了Java的反射机制,是Java程序设计中重要的技巧。分享给大家供大家参考。具体分析如下:首先,Reflection是
- 1、Service层:业务层–>控制业务业务模块的逻辑功能设计,和DAO层一样都是先设计接口,再创建要实现的类,然
- 序列化一般应用与以下场景之中:1.永久性保存对象,把对象通过序列化字节流保存到本地文件中;2.通过序列化在网络中传输对象3.通过序列化在进程
- 主要从以下十几个方面对Hibernate做总结,包括Hibernate的检索方式,Hibernate中对象的状态,Hibernate的3种检
- Mybatis typeAlias配置1.定义别名<typeAliases> <ty
- 前言本文是精讲RestTemplate第7篇,前篇的blog访问地址如下:RestTemplate在Spring或非Spring环境下使用精
- 概述LruCache的核心原理就是对LinkedHashMap的有效利用,它的内部存在一个LinkedHashMap成员变量,值得注意的4个
- Java实现PC微信扫码支付做一个电商网站支付功能必不可少,那我们今天就来盘一盘微信支付。微信支付官方网站业务流程:开发指引文档支付服务开发
- 目前常用的ORM框架有 Mybatis(batis)、MybatisPlus,Hibernate、Jpa等几个框架,今天就简单介绍一下搭建M
- 这篇文章介绍了Java+Nginx实现POP、IMAP、SMTP邮箱代理服务,我们本次使用的环境为Centos7下,java程序我们通过ec
- 在style中如下面那样定义:<style name="mystyle"> <item name=&
- 一.概述在微服务框架中,一个由客户端发起的请求在后端系统中会经过多个不同的的服务节点调用来协同产生最后的请求结果,每一个前段请求都会形成一条
- 本文实例为大家分享了SSM实现学生管理系统的具体代码,供大家参考,具体内容如下概述基于Spring + Spring MVC 的学生管理系统