https://yq.aliyun.com/articles/38213
摘要: HashMap和Hashtable的区别 HashMap和Hashtable都实现了Map接口,但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有:线程安全性,同步(synchronization),以及速度。 HashMap几乎可以等价于Hashtable,除了HashMap是非sync...
HashMap和Hashtable的区别
HashMap和Hashtable都实现了Map接口,但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有:线程安全性,同步(synchronization),以及速度。
HashMap几乎可以等价于Hashtable,除了HashMap是非synchronized的,并可以接受null(HashMap可以接受为null的键值(key)和值(value),而Hashtable则不行)。
HashMap是非synchronized,而Hashtable是synchronized,这意味着Hashtable是线程安全的,多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。
另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。
由于Hashtable是线程安全的也是synchronized,所以在单线程环境下它比HashMap要慢。如果你不需要同步,只需要单一线程,那么使用HashMap性能要好过Hashtable。
HashMap不能保证随着时间的推移Map中的元素次序是不变的。
要注意的一些重要术语:
1) sychronized意味着在一次仅有一个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要首先获得同步锁,其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。
2) Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator,然后其它的线程试图“结构上”更改集合对象,将会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的,因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改,再调用set()方法,将会抛出IllegalArgumentException异常。
3) 结构上的更改指的是删除或者插入一个元素,这样会影响到map的结构。
我们能否让HashMap同步?
HashMap可以通过下面的语句进行同步:
Map m = Collections.synchronizeMap(hashMap);
结论
Hashtable和HashMap有几个主要的不同:线程安全以及速度。仅在你需要完全的线程安全的时候使用Hashtable,而如果你使用Java 5或以上的话,请使用ConcurrentHashMap吧。
HashMap和ConcurrentHashMap分享
大家一看到这两个类就能想到HashMap不是线程安全的,ConcurrentHashMap是线程安全的。除了这些,还知道什么呢?
先看一下简单的类图:
从类图中可以看出来在存储结构中ConcurrentHashMap比HashMap多出了一个类Segment,而Segment是一个可重入锁。
ConcurrentHashMap是使用了锁分段技术技术来保证线程安全的。
锁分段技术:首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。
属性说明:
我们会发现HashMap和Segment里的属性值基本是一样的,因为Segment的本质上就是一个加锁的HashMap,下面是每个属性的意义:
table:数据存储区
size,count: 已存数据的大小
threshold:table需要扩容的临界值,等于table的大小*loadFactor
loadFactor: 装载因子
modCount: table结构别修改的次数
hash算法和table数组长度:
仔细阅读HashMap的构造方法的话,会发现他做了一个操作保证table数组的大小是2的n次方。
如果使用new HashMap(10)新建一个HashMap,你会发现这个HashMap中table数组实际的大小是16,并不是10.
为什么要这么做呢?这就要从HashMap里的hash和indexFor方法开始说了。
static int hash(int h) {
// 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);
}
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
HashMap里的put和get方法都使用了这两个方法将key散列到table数组上去。
indexFor方法是通过hash值和table数组的长度-1进行于操作,来确定具体的位置。
为什么要减1呢?因为数组的长度是2的n次方,减1以后就变成低位的二进制码都是1,和hash值做与运算的话,就能得到一个小于数组长度的数了。
那为什么对hashCode还要做一次hash操作呢?因为如果不做hash操作的话,只有低位的值参与了hash的运算,而高位的值没有参加运算。hash方法是让高位的数字也参加hash运算。
假如:数组的长度是16 我们会发现hashcode为5和53的散列到同一个位置.
hashcode:53 00000000 00000000 00000000 00110101
hashcode:5 00000000 00000000 00000000 00000101
length-1:15 00000000 00000000 00000000 00001111
只要hashcode值的最后4位是一样的,那么他们就会散列到同一个位置。
hash方法是通过一些位运算符,让高位的数值也尽可能的参加到运算中,让它尽可能的散列到table数组上,减少hash冲突。
ConcurrentHashMap的初始化:
仔细阅读ConcurrentHashMap的构造方法的话,会发现是由initialCapacity,loadFactor, concurrencyLevel几个参数来初始化segments数组的。
segmentShift和segmentMask是在定位segment时的哈希算法里需要使用的,让其能够尽可能的散列开。
initialCapacity:ConcurrentHashMap的初始大小
loadFactor:装载因子
concurrencyLevel:预想的并发级别,为了能够更好的hash,也保证了concurrencyLevel的值是2的n次方
segements数组的大小为concurrencyLevel,每个Segement内table的大小为initialCapacity/ concurrencyLevel
ConcurrentHashMap的put和get
int hash = hash(key.hashCode());
return segmentFor(hash).get(key, hash);
可以发现ConcurrentHashMap通过一次hash,两次定位来找到具体的值的。
先通过segmentFor方法定位到具体的Segment,再在Segment内部定位到具体的HashEntry,而第二次在Segment内部定位的时候是加锁的。
ConcurrentHashMap的hash算法比HashMap的hash算法更复杂,应该是想让他能够更好的散列到数组上,减少hash冲突。
HashMap和Segment里modCount的区别:
modCount都是记录table结构被修改的次数,但是对这个次数的处理上,HashMap和Segment是不一样的。
HashMap在遍历数据的时候,会判断modCount是否被修改了,如果被修改的话会抛出ConcurrentModificationException异常。
Segment的modCount在ConcurrentHashMap的containsValue、isEmpty、size方法中用到,ConcurrentHashMap先在不加锁的情况下去做这些计算,如果发现有Segment的modCount被修改了,会再重新获取锁计算。
HashMap和ConcurrentHashMap的区别:
如果仔细阅读他们的源码,就会发现HashMap是允许插入key和value是null的数据的,而ConcurrentHashMap是不允许key和value是null的。这个是为什么呢?ConcurrentHashMap的作者是这么说的:
The main reason that nulls aren't allowed in ConcurrentMaps (ConcurrentHashMaps, ConcurrentSkipListMaps) is that ambiguities that may be just barely tolerable in non-concurrent maps can't be accommodated. The main one is that if map.get(key) returns null, you can't detect whether the key explicitly maps to null vs the key isn't mapped. In a non-concurrent map, you can check this via map.contains(key), but in a concurrent one, the map might have changed between calls.
为什么重写了equals方法就必须重写hashCode方法呢?
绝大多数人都知道如果要把一个对象当作key使用的话,就需要重写equals方法。重写了equals方法的话,就必须重写hashCode方法,否则会出现不正确的结果。那么为什么不重写hashCode方法就会出现不正确结果了呢?这个问题只要仔细阅读一下HashMap的put方法,看看它是如何确定一个key是否已存在的就明白了。关键代码:
int hash = hash(key.hashCode());
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;
}
}
首先通过key的hashCode来确定具体散列到table的位置,如果这个位置已经有值的话,再通过equals方法判断key是否相等。
如果只重写equals方法而不重写hashCode方法的话,即使这两个对象通过equals方法判断是相等的,但是因为没有重写hashCode方法,他们的hashCode是不一样的,这样就会被散列到不同的位置去,变成错误的结果了。所以hashCode和equals方法必须一起重写。
分享到:
相关推荐
HashMap 和 HashTable 的区别 1. 线程安全性:HashMap 是非线程安全的,HashTable 是线程安全的。 2. 键和值的 null 值:HashMap 的键和值都允许有 null 值存在,而 HashTable 则不行。 3. 效率:HashMap 的效率比 ...
hashmap和hashtable的区别 HashMap和Hashtable都实现了Map接口,但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有:线程安全性,同步(synchronization),以及速度。 1. HashMap几乎可以等价于Hashtable,...
1.说一下 HashMap 的实现原理? 2.HashMap在JDK1.7和JDK1.8中有哪些不同?HashMap的底层实现? 3.HashMap的put方法的具体流程...17.HashMap 和 ConcurrentHashMap 的区别? 18.ConcurrentHashMap 和 Hashtable 的区别?
HashMap 和 Hashtable 的区别,HashSet如何检查重复,HashMap的底层实现,HashMap 多线程操作导致死循环问题,ConcurrentHashMap 和 Hashtable 的区别,ConcurrentHashMap线程安全的具体实现⽅式/底层具体实现,...
本文总结了Java中级面试题,涵盖了集合、HashMap、HashSet、HashTable、ConcurrentHashMap、红黑树、Java 8对HashMap的优化、LinkedHashMap、TreeMap、IdentityHashMap等知识点。 集合 * List和Set都是继承自...
17.HashMap、Hashtable、ConcurrentHashMap底层实现原理及区别 18.HashMap底层数据结构 19.说说HashMap如何处理碰撞的,或者说说它的扩容? 20.jdk7/8中对HashMap做了哪些改变? 21.负载因子为什么会影响HashMap性能...
就是一些通用java集合知识点整理,ArrayList LinkedList,HashMap,HashTable ,ConcurrentHashMap,HashSet,LinkedHashSet类通过线程安全否: 底层: 初始值: 扩容 : 区别(对比优势) 图解
区别、HashMap的底层实现、HashMap 和 Hashtable 的区别、HashMap 的长度为什么是2的幂次方、HashSet 和 HashMap 区别、ConcurrentHashMap 和 Hashtable 的区别、ConcurrentHashMap线程安全的具体实现方式/底层具体...
java8 源码 目录 Java 基础 容器 并发 JVM I/O Java ...(String和StringBuffer、StringBuilder的区别是什么?...的区别、ConcurrentHashMap线程安全的具体实现方式/底层具体实现、集合框架底层数据结构总结
1. 经历了一个半月的时间学习,已拿到阿里,腾讯,...Hashmap和Hashtable和concurrentHashmap的区别 二面 简答Spring与Springboot之间的问题 回答JVM上的问题 回答Java中锁机制 回答Java中的数据库问题 三面 回答Java
HashMap,Hashtable和ConcurrentHashMap的区别 在ArrayList和LinkedList尾部添加元素,谁的效率更高 如果HashMap或者hashTable的key是一个自定义的类该怎么办 为什么重写equals还要重写hashCode? 介绍一下volatile jdk...
2. ConcurrentHashMap,jdk1.7 添加了分段锁,就是在底层数组上,几个索引上添加一把锁,jdk1.8 添加的则是乐观锁,在每一个索引上都添加锁; 3. Conllections. synchronizedMap(map) 给 HashMap 整个集合添加了锁。...
这篇文章记录在准备Java后端面试复习过程中网上常见的考题,同时也会标明题目出现频率...Java Map高频hashtable和hashmap的区别及实现原理,请你说明HashMap和Hashtable的区别?HashMap 和 ConcurrentHashMap?如何使Has
leetcode下载 目录 操作系统 虚拟内存与物理内存转化 CPU 调度方式 进程栈大小 进程与线程区别 线程状态 网络 ...HashTable ConcurrentHashMap JAVA IO Go Redis Redis Cluster Redis 持久化方式 Redis
HashMap,HashTable,ConcurrentHashMap 实现原理以及区别? HashSet 与 HashMap 怎么判断集合元素重复? String、StringBuffer、StringBuilder 之间的区别? 对反射的了解? 对注解的了解? 对依赖注入的了解? 对...
ConcurrentHashMap 详解 异常相关 代理机制 JDBC BIO NIO AIO 创建类的方法 final finally finalize 反射 序列化与反序列化 transient 枚举 注解 JDK7新特性 JDK8新特性 JDK9新特性 JDK10新特性 运行时数据区 对象 ...
此外,文档介绍了哈希冲突的概念和解决方法,以及HashMap的查询流程和与Hashtable的区别。特别强调了Hashtable不允许插入null的原因,以及ConcurrentHashMap在线程安全实现和锁优化方面的策略。 总的来说,这份文档...
此外,文件介绍了哈希冲突的概念和解决方法,以及HashMap的查询流程和与Hashtable的区别。特别强调了Hashtable不允许插入null的原因,以及ConcurrentHashMap在线程安全实现和锁优化方面的策略。 总的来说,这份文件...
对比:Hashtable、HashMap、LinkedHashMap、ConcurrentHashMap、TreeMap (看第六条就可以) HashMap 用什么数据结构实现的 加载因子是什么 HashMap 初始化传入的容量参数的值是就是 HashMap 实际分配的空间么 ...
HashMap是线程不安全的,并允许null key 和 null value。 HashMap在我当前的jdk版本(11)的默认容量为0,在第一次添加元素的时候才初始化容量为 16, 之后才扩容为原来的2倍。 HashMap的扩容是根据 threshold决定的 : ...