博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
回顾HashMap
阅读量:5818 次
发布时间:2019-06-18

本文共 1998 字,大约阅读时间需要 6 分钟。

一、HashMap的原理简述

HashMap是基于哈希表的非线程安全的Map实现,内部采用数组+链表实现,其内部类Node定义了数据元素类型,它扩展了Map.Entry<K,V>增加了指向下一个node结点的指针next。当向Map中加入一个键值对时,先根据键的haseCode计算hash值(为了尽量避免hash冲突,让键值对构成的node结点均匀的分布在数组上),然后算出它在数组中下标值,若此处为null则直接插入,否则比较此处node对象的hash值,若相同则修改,若不同则将要插入的node对象的next指针指向此处的node对象,然后将要插入的node对象放到该位置。

HashMap的性能影响最大的参数就是容量和负载以及hash算法的选择。如果HashMap中元素数超过容量*负载的值时就会产生扩容,为尽量减少扩容造成的性能消耗,在使用HashMap时尽量指定初始容量大小,而实际构造HashMap的初始容量大小会设定为不必指定容量小的2的n次方,以方便使用&运算来代替取模操作提升程序性能。

如果HashMap中元素的键计算的hash值冲突严重,会导致此hash值对应的链表过长,从而影响HashMap的读取性能,因此在JDK8中采用数组+链表+红黑树的方式来优化HashMap,默认当链表长度大于8时就采用红黑树来实现。

HashMap不是线程安全的,JDK采用Fail-Fast机制进行检测错误,当程序在遍历HashMap元素时如果检测到有其它线程修改了HashMap对象,就抛出并发修改异常。其内部实现是用modCount记录HashMap对象的修改次数,每当进行添加、删除、修改元素等修改操作时modCount++,遍历时检测到这个值前后不同就认为被其它线程修改过。Fail-Fast机制是错误检测机制,不一定能得到保证,如果要在多线程中使用,程序必须要在外部做同步处理,比如使用concurrent包下的类。

HashMap是遍历顺序是不确定的,若想要按确定顺序访问,可采用LinkedHashMap,它内部维护了一个双重链表,定义了迭代顺序,这个迭代顺序可以是插入顺序或者是访问顺序。默认是插入顺序,可通过构造函数指定按访问顺序排,可以方便的实现一个LRU缓存。

HashMap元素时无需的,若想要可排序的map,可以采用TreeMap。

二、HashSet的原理

HashSet基于HashMap实现,内部使用HashMap来保存元素。对于HashSet中保存的对象,要重写其equals和hashCode方法,以保证放入对象的唯一性。

三、ConcurrentHashMap原理

ConcurrentHashMap是线程安全的HashMap,它牺牲了遍历get操作的强一致性,通过弱一致性换来了多线程并发的高性能,可以用来代替HashTable或Collections.synchronizedMap(hashMap),因为它们实现同步的方式都是对整个Hash表结构做锁定操作,在锁表过程,其它线程都要等待,这在元素多时性能很低。在JDK1.7中采用分段锁技术来控制并发,内部先是Segment[]成员,它的每个元素时HashEntry[],它里面的每个元素是键值对,因此它在理想情况下可并发访问的线程数是segment数组的大小。它把HashMap分割成若干个Segment,在put的时候需要锁住Segment,get时候不加锁,使用volatile来保证可见性,当要统计全局时(比如size),首先会尝试多次计算modcount来确定,这几次尝试中,是否有其他线程进行了修改操作,如果没有,则直接返回size。如果有,则需要依次锁住所有的Segment来计算。

jdk7中ConcurrentHashmap中,当长度过长碰撞会很频繁,链表的增改删查操作都会消耗很长的时间,影响性能,因此在JDK1.8中采用了进一步的优化,从原来的ReentrantLock+Segment+HashEntry变为synchronized+CAS+Node数组+链表+红黑树来实现,将锁的粒度从Segment降低到首个HashEntry节点,设计了MOVED状态 当resize的中过程中其它线程要put数据时会能帮助resize,使用3个CAS操作来确保node的一些操作的原子性,代替了锁,使用sizeCtl的不同值来代表不同含义,起到了控制的作用。

注意:ConcurrentHashMap再设计实现时要求传入Key和Value都不能为null(为了分辨volatile变量是否是未赋值状态,从而方便多线程并发判断),HashTable中的Key、Value也不能为null。TreeMap不允许Key为null值,HashMap的Key、Value都可以为null值。

 

 

转载地址:http://fswdx.baihongyu.com/

你可能感兴趣的文章
【聚能聊有奖话题】Boring隧道掘进机完成首段挖掘,离未来交通还有多远?
查看>>
盘点物联网网关现有联网技术及应用场景
查看>>
考研太苦逼没坚持下来!看苑老师视频有点上头
查看>>
HCNA——RIP的路由汇总
查看>>
zabbix监控php状态(四)
查看>>
定时任务的创建
查看>>
实战Django:小型CMS Part2
查看>>
原创]windows server 2012 AD架构试验系列 – 16更改DC计算机名
查看>>
统治世界的十大算法
查看>>
linux svn安装和配置
查看>>
SSH中调用另一action的方法(chain,redirect)
查看>>
数据库基础
查看>>
表格排序
查看>>
关于Android四大组件的学习总结
查看>>
java只能的round,ceil,floor方法的使用
查看>>
由于无法创建应用程序域,因此未能执行请求。错误: 0x80070002 系统找不到指定的文件...
查看>>
新开的博客,为自己祝贺一下
查看>>
puppet任务计划
查看>>
【CQOI2011】放棋子
查看>>
采用JXL包进行EXCEL数据写入操作
查看>>