共计 41 篇文章

Java8的HashMap详解(存储结构,功能实现,扩容优化,线程安全,遍历方法)

JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的区别,深入探讨HashMap的结构实现和功能原理,文章末尾附有HashMap的put方法和resize方法的源码解析。 简介 Java为数据结构中的映射定义了一个接口java.util.Map,此接口主要有四个常用的实现类,分别是HashMap、Hashtable、LinkedHashMap和TreeMap,类继承关系如下图所示: 下面针对各个实现类的特点做一些说明: (1) HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。 ...

漫画:高并发下的HashMap

上一期我们介绍了HashMap的基本原理,没看过的小伙伴们可以点击下面的链接: 漫画:什么是HashMap? 这一期我们来讲解高并发环境下,HashMap可能出现的致命问题。 HashMap的容量是有限的。当经过多次元素插入,使得HashMap达到一定饱和度时,Key映射位置发生冲突的几率会逐渐提高。 这时候,HashMap需要扩展它的长度,也就是进行Resize。 影响发生Resize的因素有两个: 1.Capacity HashMap的当前长度。上一期曾经说过,HashMap的长度是2的幂。 2.LoadFactor HashMap负载因子,默认值为0.75f。 衡量HashMap是否进行Resize的条件如下: HashMap. ...

漫画:什么是HashMap?

众所周知,HashMap是一个用于存储Key-Value键值对的集合,每一个键值对也叫做Entry。这些个键值对(Entry)分散存储在一个数组当中,这个数组就是HashMap的主干。 HashMap数组每一个元素的初始值都是Null。 对于HashMap,我们最常使用的是两个方法:Get 和 Put。 1.Put方法的原理 调用Put方法的时候发生了什么呢? 比如调用 hashMap.put("apple", 0) ,插入一个Key为apple的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置(index) ...

HashMap的尾部遍历问题--Tail Traversing

参考:http://stackoverflow.com/questions/22890967/java-hashmap-tail-traversing 在看网上HashMap的resize()设计时,提到尾部遍历。 JDK1.7的HashMap在实现resize()时,新table[]的列表采用LIFO方式,即队头插入。这样做的目的是:避免尾部遍历。 参考stackoverflow的讨论,尾部遍历是为了避免在新列表插入数据时,遍历队尾的位置。因为,直接插入的效率更高。 直接采用队头插入,会使得链表数据倒序 例如原来顺序是: ...

HashMap 里的“bucket”、“负载因子” 介绍

对于 HashMap 及其子类而言,它们采用 Hash 算法来决定集合中元素的存储位置。当系统开始初始化 HashMap 时,系统会创建一个长度为 capacity 的 Entry 数组,这个数组里可以存储元素的位置被称为“桶(bucket)”,每个 bucket 都有其指定索引,系统可以根据其索引快速访问该 bucket 里存储的元素。 无论何时,HashMap 的每个“ ...