不多说,直接上干货!
福利 => 每天都推送
欢迎大家,关注微信扫码并加入我的4个微信公众号: 大数据躺过的坑 Java从入门到架构师 人工智能躺过的坑 Java全栈大联盟 每天都有大量的学习视频资料和精彩技术文章推送… 人生不易,唯有努力。 百家号 :九月哥快讯 快手号: jiuyuege
HashMap的实现原理
HashMap是基于java.util.map接口的实现,该实现提供了所有的对Map的可选操作,同时也允许null类型的key以及value (HashTable与此大致相同,只是HashTable是同步的,不过HashTable一般被认为是已经过时的,很少有人再去用了)。
HashMap不保证Map中的顺序,特别是不能保证数据在一段时间内的顺序性。
如果散列函数(Hash函数)在正确的在桶中分散元素,HashMap的实现提供了对基本的操作(put与get)时间性能为常数。
集合视图的迭代需要的时间与HashMap实例的容量capacity值(桶数)和大小(键值对个数)成正比,所以如果对迭代器的性能比较关注, 那么不要把初始化的容量capacity值设的太高或不要将装填因子load factor设的太小就非常重要。
HashMap的实例总有两个非常重要的影响性能的参数:初始容量大小(initial capacity)与装填因子(load factor)。
在HashMap中,capacity就是buckets的数量,初始容量大小就是在HashMap创建的时候指定的capacity。
装填因子指的是HashMap在多满的时候就需要提前自动扩容了(如初始化容量16,装填因子0.75,一旦元素个数 超过16*0.75=12个的时候,就需要对容量进行扩充,翻倍) 扩容需要rehash,也就是说HashMap内部结构会被重新构建。
通常来讲,默认的装填因子0.75提供了一个基于时间与空间代价比较好的平衡。桶中装的更满意味着空间开销更低, 但是查找开销变大(反映到HashMap中就是包含get与put在内各种操作开销变大,时间变长)。
当设置初始容量大小时,应该考虑HashMap中预期的数量以及装填因子,这样才能让rehash执行的次数最少, 如果初始化大小的值比实际数据的条数乘以装填因子的积还要大,那么就不会发生rehash。
如果有非常多的记录存在HashMap中,那么在初始化这个HashMap的时候将容量capacity设置的足够大,比自动rehash 扩容效率更高。
注意如果很多key有了相同的hashCode值,那么会对性能造成很大的影响(产生聚集问题,rehash次数变多,性能下降),为了改善这种情况 当key可以进行比较(继承了Comparable接口之类的),HashMap会采用对key进行比较排序。
注意:HashMap不是线程同步的。
如果多线程并发访问一个HashMap,同时至少有一个线程修改了HashMap的结构,那么该HashMap必须要在外部进行同步 (结构的改变指的是添加或删除一个映射关系-键值对,只是根据key修改了value的值不会对HashMap造成结构上的影响) 这种同步操作通常在封装有HashMap的Object中实现;如果没有这样的对象实现,那么HashMap需要采用Collections.synchronizedMap 来保证多线程并发环境下的数据同步问题,这个操作最好在创建HashMap的时候就去做。 Map m = Collections.synchronizedMap(new HashMap(…));
如果HashMap产生的迭代器创建后,HashMap数据结构又发生了变化,则除了remove方法外,迭代器iterator会抛出一个 ConcurrentModificationException异常,这就是迭代器的快速失败(fail-fast)。 因此面对并发修改,迭代器采用快速而干净的失败来取代在未来的某一个不确定的时间产生不确定的后果。
注意:迭代器的快速失败行为是无法保证的,通常来讲,在非同步并发修改的情况下这种硬性保证都没法给出,快速失败也只能尽量抛出 ConcurrentModificationException异常,所以不能写一段代码去基于该异常做出义务逻辑处理,最好快速失败进行BUG探测。
更多详细,见
牛客网Java刷题知识点之Java 集合框架的构成、集合框架中的迭代器Iterator、集合框架中的集合接口Collection(List和Set)、集合框架中的Map集合
牛客网Java刷题知识点之Map的两种取值方式keySet和entrySet、HashMap 、Hashtable、TreeMap、LinkedHashMap、ConcurrentHashMap 、WeakHashMap
HashMap的存储结构
HashMap的存储,本质上是构造了一个table,根据计算的hashCode将对应的KV存储到该table中,一旦发生hashCode冲突,那么就会将该KV放到对应的已有元素的后面, 此时,形成了一个链表式的存储结构,即:HashMap 就是一个table数组 + 链表实现的存储结构(在JDK1.8之前的存储结构),如下图所示: