成都网站建设企业,贵阳seo网站推广,小程序开发多少钱,网站建设价格山东济南兴田德润什么活动本文转载自 夏雪冬日#xff1a;https://www.cnblogs.com/heyonggang/p/9112731.html 在实际面试过程中出现集合 Map 的概率接近 100%#xff0c;可见不背上个 Map 相关的题目都不好意思去面试了。 如果你去面试#xff0c;面试官不问你这个问题#xff0c;你来找我^_^
下… 本文转载自 夏雪冬日https://www.cnblogs.com/heyonggang/p/9112731.html 在实际面试过程中出现集合 Map 的概率接近 100%可见不背上个 Map 相关的题目都不好意思去面试了。 如果你去面试面试官不问你这个问题你来找我^_^
下面直接来干货先说这三个 Map 的区别
1、HashTable
底层数组链表实现无论key还是value都不能为null线程安全实现线程安全的方式是在修改数据时锁住整个HashTable效率低ConcurrentHashMap做了相关优化初始size为11扩容newsize olesize*21计算index的方法index (hash 0x7FFFFFFF) % tab.length
2、HashMap
底层数组链表实现可以存储null键和null值线程不安全初始size为16扩容newsize oldsize*2size一定为2的n次幂扩容针对整个Map每次扩容时原来数组中的元素依次重新计算存放位置并重新插入插入元素后才判断该不该扩容有可能无效扩容插入后如果扩容如果没有再次插入就会产生无效扩容当Map中元素总数超过Entry数组的75%触发扩容操作为了减少链表长度元素分配更均匀计算index方法index hash (tab.length – 1)
HashMap的初始值还要考虑加载因子:
哈希冲突若干Key的哈希值按数组大小取模后如果落在同一个数组下标上将组成一条Entry链对Key的查找需要遍历Entry链上的每个元素执行equals()比较。加载因子为了降低哈希冲突的概率默认当HashMap中的键值对达到数组大小的75%时即会触发扩容。因此如果预估容量是100即需要设定100/0.75134的数组大小。空间换时间如果希望加快Key查找的时间还可以进一步降低加载因子加大初始大小以降低哈希冲突的概率。
HashMap和Hashtable都是用hash算法来决定其元素的存储因此HashMap和Hashtable的hash表包含如下属性
容量capacityhash表中桶的数量初始化容量initial capacity创建hash表时桶的数量HashMap允许在构造器中指定初始化容量尺寸size当前hash表中记录的数量负载因子load factor负载因子等于“size/capacity”。负载因子为0表示空的hash表0.5表示半满的散列表依此类推。轻负载的散列表具有冲突少、适宜插入与查询的特点但是使用Iterator迭代元素时比较慢
除此之外hash表里还有一个“负载极限”“负载极限”是一个01的数值“负载极限”决定了hash表的最大填满程度。当hash表中的负载因子达到指定的“负载极限”时hash表会自动成倍地增加容量桶的数量并将原有的对象重新分配放入新的桶内这称为rehashing。
HashMap和Hashtable的构造器允许指定一个负载极限HashMap和Hashtable默认的“负载极限”为0.75这表明当该hash表的3/4已经被填满时hash表会发生rehashing。
“负载极限”的默认值0.75是时间和空间成本上的一种折中
较高的“负载极限”可以降低hash表所占用的内存空间但会增加查询数据的时间开销而查询是最频繁的操作HashMap的get()与put()方法都要用到查询较低的“负载极限”会提高查询数据的性能但会增加hash表所占用的内存开销 程序猿可以根据实际情况来调整“负载极限”值。
3、ConcurrentHashMap
底层采用分段的数组链表实现线程安全通过把整个Map分为N个Segment可以提供相同的线程安全但是效率提升N倍默认提升16倍。(读操作不加锁由于HashEntry的value变量是 volatile的也能保证读取到最新的值。)Hashtable的synchronized是针对整张Hash表的即每次锁住整张表让线程独占ConcurrentHashMap允许多个修改操作并发进行其关键在于使用了锁分离技术有些方法需要跨段比如size()和containsValue()它们可能需要锁定整个表而而不仅仅是某个段这需要按顺序锁定所有段操作完毕后又按顺序释放所有段的锁扩容段内扩容段内元素超过该段对应Entry数组长度的75%触发扩容不会对整个Map进行扩容插入前检测需不需要扩容有效避免无效扩容
Hashtable和HashMap都实现了Map接口但是Hashtable的实现是基于Dictionary抽象类的。Java5提供了ConcurrentHashMap它是HashTable的替代比HashTable的扩展性更好。
HashMap基于哈希思想实现对数据的读写。当我们将键值对传递给put()方法时它调用键对象的hashCode()方法来计算hashcode然后找到bucket位置来存储值对象。当获取对象时通过键对象的equals()方法找到正确的键值对然后返回值对象。HashMap使用链表来解决碰撞问题当发生碰撞时对象将会储存在链表的下一个节点中。HashMap在每个链表节点中储存键值对对象。当两个不同的键对象的hashcode相同时它们会储存在同一个bucket位置的链表中可通过键对象的equals()方法来找到键值对。如果链表大小超过阈值TREEIFY_THRESHOLD,8链表就会被改造为树形结构。
在HashMap中null可以作为键这样的键只有一个但可以有一个或多个键所对应的值为null。当get()方法返回null值时即可以表示HashMap中没有该key也可以表示该key所对应的value为null。因此在HashMap中不能由get()方法来判断HashMap中是否存在某个key应该用containsKey()方法来判断。而在Hashtable中无论是key还是value都不能为null。
Hashtable是线程安全的它的方法是同步的可以直接用在多线程环境中。而HashMap则不是线程安全的在多线程环境中需要手动实现同步机制。
Hashtable与HashMap另一个区别是HashMap的迭代器Iterator是fail-fast迭代器而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构增加或者移除元素将会抛出ConcurrentModificationException但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为要看JVM。
先看一下简单的类图 从类图中可以看出来在存储结构中ConcurrentHashMap比HashMap多出了一个类Segment而Segment是一个可重入锁。
ConcurrentHashMap是使用了锁分段技术来保证线程安全的。
锁分段技术首先将数据分成一段一段的存储然后给每一段数据配一把锁当一个线程占用锁访问其中一个段数据的时候其他段的数据也能被其他线程访问。
ConcurrentHashMap提供了与Hashtable和SynchronizedMap不同的锁机制。Hashtable中采用的锁机制是一次锁住整个hash表从而在同一时刻只能由一个线程对其进行操作而ConcurrentHashMap中则是一次锁住一个桶。
ConcurrentHashMap默认将hash表分为16个桶诸如get、put、remove等常用操作只锁住当前需要用到的桶。这样原来只能一个线程进入现在却能同时有16个写线程执行并发性能的提升是显而易见的。 4、小试牛刀
讲一下HashMap哈HashTable的区别HashTable和ConcurrentHashMap的区别
相同点
底层数组 链表实现都可以用来存储 key-value 的数据
区别
HashTable 无论key还是value都不能为null线程安全HashMap 可以存储null键和null值线程不安全
我想线程安全但是我又想效率高
使用 ConcurrentHashMap其底层采用分段的数组链表实现线程安全通过把 Map 分为 N 个 Segment(部分)可以提供相同的线程安全但是效率提升N倍默认提升16倍。
Hashtable 之所以效率低主要是使用了 synchronized 关键字对 put 等操作进行加锁而 synchronized 关键字加锁是对整张 Hash 表的即每次锁住整张表让线程独占致使效率低下而 ConcurrentHashMap 在对象中保存了一个 Segment 数组即将整个Hash表划分为多个分段而每个Segment元素即每个分段则类似于一个Hashtable这样在执行put操作时首先根据hash算法定位到元素属于哪个Segment然后对该Segment加锁即可因此 ConcurrentHashMap 在多线程并发编程中可是实现多线程put操作。
