《Java集合Map》HashMap实现详解
2020/3/1 17:15:08
本文主要是介绍《Java集合Map》HashMap实现详解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1. 概述
JDK1.7中的HashMap是由数组+链表组成的,而JDK1.8中的HashMap是由数组+链表+红黑树组成。数组的默认长度(DEFAULT_INITIAL_CAPACITY
)为16(可以自动变长,也可以指定一个长度),加载因子(DEFAULT_LOAD_FACTOR
)为0.75。
- HashMap的默认长度为16和规定数组长度为2的幂,是为了降低哈希碰撞的几率。
- HashMap中使用链表主要为了解决哈希冲突,链表出现越少或者长度越小,性能才会越好。
数组:具有遍历快,增删慢的特点。数组在堆中是一块连续的存储空间,遍历时数组的首地址是知道的,所以遍历快,遍历的时间复杂度为
O(1)
;当在中间插入或删除元素时,会造成该元素后面所有元素地址的改变,所以增删慢,增删的时间复杂度为O(n)
。
链表:链表具有增删快,遍历慢的特点。链表中各元素的内存空间是不连续的,一个节点至少包含节点数据与后继节点的引用,所以在插入删除时,只需修改该位置的前驱节点与后继节点即可,链表在插入删除时的时间复杂度为
O(1)
。但是在遍历时,get(n)元素时,需要从第一个开始,依次拿到后面元素的地址,进行遍历,直到遍历到第n个元素,遍历的时间复杂度为O(n)
,所以效率极低。
2. 哈希冲突
指两个元素通过hash函数计算出的值是一样的,表示这两个元素存储的是同一个地址。当后面的元素要插入到这个地址时,发现已经被占用了,这时候就产生了哈希冲突。
哈希冲突的解决办法:
- 开放定址法:当发生哈希冲突时,查询产生冲突的地址的下一个地址是否被占用,直到寻找到空的地址。
- 链地址法:当发生哈希冲突时,在冲突的地址上生成一个链表,将冲突的元素的key通过equals进行比较,相同即覆盖,不同则添加到链表上。
HashMap
使用的是链地址法。在JDK1.7中,如果链表过长,效率就会大大降低,查找和添加操作的时间复杂度都为O(n)
;在JDK1.8中,如果链表长度大于8,链表就会转化为红黑树,时间复杂度也就将为O(logn)
,性能得到了很大的提升。
当红黑树节点个数少于6的时候,又会将红黑树转化为链表。因为在数据量较小的情况下,红黑树要维持平衡,比起链表,性能上的优势并不明显。
3. Rehash扩容机制
如果HashMap的大小超过了负载因子(默认为0.75)定义的容量,也就是说,当一个Map填满了75%的Bucket时候,将会创建原来HashMap大小的两倍的Bucket数组,来重新调整Map的大小,并将原来的对象放入新的Bucket数组中。
阈值 = 数组默认的长度 x 负载因子(阈值 = 16 x 0.75 = 12)
1. HashMap扩容限制的负载因子为什么是0.75?为什么不能是0.1或者1呢?
- 如果负载因子为0.5甚至更低的可能的话,最后得到的临时阈值明显会很小,这样的情况就会造成内存的浪费,存在多余的没用的内存空间,也不满足哈希表均匀分布的情况。
- 如果负载因子达到了1的情况,也就是数组存满了才发生扩容,这样会出现大量的哈希冲突的情况,出现链表过长,因此造成get查询数据的效率。
2. 为何数组容量必须是2次幂?
索引计算公式为index = (length - 1) & hash
,如果length为2次幂,那么length-1的低位就全是1,哈希值进行与操作时可以保证低位的值不变,效果等同于hash%length
,从而保证分布均匀。
JDK1.8中在扩容HashMap的时候,不需要像JDK1.7中去重新计算元素的hash,只需要看看原来的hash值新增的哪个二进制数是1还是0就好了「是0还是1可以认为是随机的」,如果是0的话表示索引没有变,是1的话表示索引变成“oldCap+原索引”,这样即省去了重新计算hash值的时间,并且扩容后链表元素位置不会倒置。
4. JDK1.7源码分析
JDK1.7中的HashMap是由数组+链表组成的,组成链表结点的是Entity
包含三个元素:key
、value
和指向下一个Entity的next
。
- 如果定位到的数组位置不含链表(当前Entity的next指向null),那么对于查找和添加等操作的执行速度很快,仅需要一次寻址,时间复杂度为O(1)。
- 如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n)。首先遍历链表,存在即覆盖,否则新增;对于查找操作仍需要遍历链表,然后通过
equals
方法逐一比对查找。
4.1 put()
- 用
table[index]
表示通过hash值计算出元素需要存储在数组中的位置(bucket桶),先判断该位置上是否存在Entity。 - 如果不存在Entity,在该位置上插入一个
Entity<k,v>
对象,插入结束。 - 如果存在Entity,通过equals方法将key和已有的key进行比较,检查是否相同。
- 如果相同,新的value替换老的value;
- 如果不相同,则在table[index]插入该Entity,并将新的Entity的next指向原来的Entity,新插入的Entity的位置永远是在链表的最前面(头插法)。
如果多线程同时put,如果同时触发了Rehash扩容操作,会导致HashMap中的链表中出现循环节点,进而使得后面get的时候,会出现死循环,所以HashMap是非线程安全的。
4.2 get()
先定位到数组元素,再遍历该元素处的链表,在寻找目标元素的时候,除了对比通过key计算出来的hash值,还会用双等或equals方法对key本身来进行比较,两者都为true时才会返回这个元素。
- 按照散列函数的定义,如果两个对象相同,即
obj1.equals(obj2) = true
,则它们的hashCode必须相同;但如果两个对象不同,则它们的hashCode不一定不同。 - 如果两个不同对象的hashcode相同,就称为冲突。冲突会导致操作哈希表的时间开销增大,所以覆盖了equals方法之后一定要覆盖hashCode方法。比如,
String a = new String(“abc”); String b = new String(“abc”); 复制代码
如果不覆盖的话,那么a和b的hashCode就会不同,把这两个类当做key存到HashMap中的话就会出现问题,就会和key的唯一性相矛盾。
如何定位元素?即二进制 hashCode & (leng-1)
- 计算"book"的hashcode 十进制 : 3029737 二进制 : 101110001110101110 1001
- HashMap长度是默认的 16,length - 1 的结果 十进制 : 15 二进制 : 1111
- 把以上两个结果做与运算 101110001110101110 1001 & 1111 = 1001 1001的十进制 : 9,所以 index=9。
5. JDK1.8源码分析
JDK1.7中的HashMap是由数组+链表+红黑树组成的,组成链表结点的是Node
包含三个元素:key
、value
和指向下一个Node的next
。
5.1 put()
- 判断键值对数组table[i]是否为空或为null,如果为空则创建Node;
- 根据键值key计算hash值得到插入的数组索引i,如果
table[i]==null
,直接新建节点添加,转向⑥,如果table[i]不为空,则转向③; - 判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是
hashCode
以及equals
; - 判断table[i]是否为
treeNode
红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤; - 遍历table[i],判断链表长度是否大于8,如果链表长度大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;
- 插入成功后,判断实际存在的键值对数量size是否超多了最大容量
threshold
,如果超过,进行resize()
扩容。
public V put(K key, V value) { // 对key做hash运算得到hashCode return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 步骤①:tab为空则创建。 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 步骤②:计算index。 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 步骤③:节点key存在,直接覆盖value。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 步骤④:判断该链是否为红黑树。 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 步骤⑤:链表 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key,value,null); // 判断链表长度是否大于8,如果链表长度大于8转换为红黑树进行处理。 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果key已经存在并且equals相等,则直接覆盖value。 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 步骤⑥:超过最大容量就扩容。 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 复制代码
5.2 get()
- 判断表是否为空,并且计算索引位置,并对索引位置的值进行判空校验。
- 如果表为空 && 索引位置没有值,直接返回null;
- 如果表不为空 && 索引位置有值,执行步骤②。
- 判断入参key与索引处第一个key的hashCode是否相等、 key是否相等或者equals是否相等。
- 如果步骤②条件满足,则直接返回;否则执行步骤③;
- 判断链接是否为红黑树。
- 如果链表是红黑树,则按照红黑树二叉查找法获取值;
- 如果不是红黑树(链表长度小于8为普通链表),则遍历链表,直到找到与入参key的hashCode相等、equals相等的key,并获取该key的值。
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; // Node不为空 && 计算索引位置并且索引处有值 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 判断key的hashCode是否相等 // && 判断索引处第一个key与传入key是否相等 // && 判断key的equals是否相等。 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 判断链表是否是红黑树,如果是红黑树,就从树中获取值。 if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 如果不是红黑树,遍历链表。 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; } 复制代码
6. 使用示例
public class HashMapDemo { @Test public void test1() { // 第一种:普通使用,二次取值 Map<String, Object> map = new HashMap<String, Object>(); for (int i = 0; i < 1000000; i++) { map.put("test" + i, "test" + i); } long before = System.currentTimeMillis(); for (String key : map.keySet()) { map.get(key); } long after = System.currentTimeMillis(); System.out.println("HashMap遍历:" + (after - before) + "ms"); } @Test public void test2() { // 推荐,尤其是容量大时 Map<String, Object> map = new HashMap<String, Object>(); for (int i = 0; i < 1000000; i++) { map.put("test" + i, "test" + i); } long before = System.currentTimeMillis(); for (Map.Entry<String, Object> entry : map.entrySet()) { entry.getValue(); entry.getKey(); } long after = System.currentTimeMillis(); System.out.println("HashMap遍历:" + (after - before) + "ms"); } @Test public void test3() { // 通过Map.entrySet使用iterator遍历key和value Map<String, Object> map = new HashMap<String, Object>(); for (int i = 0; i < 1000000; i++) { map.put("test" + i, "test" + i); } long before = System.currentTimeMillis(); Iterator<Entry<String, Object>> iterator = map.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<String, Object> entry = (Entry<String, Object>) iterator.next(); entry.getKey(); entry.getValue(); } long after = System.currentTimeMillis(); System.out.println("HashMap遍历:" + (after - before) + "ms"); } @Test public void test4() { // 通过Map.values()遍历所有的value,但不能遍历key Map<String, Object> map = new HashMap<String, Object>(); for (int i = 0; i < 1000000; i++) { map.put("test" + i, "test" + i); } long before = System.currentTimeMillis(); for (@SuppressWarnings("unused") Object object : map.values()) { } long after = System.currentTimeMillis(); System.out.println("HashMap遍历:" + (after - before) + "ms"); } } 复制代码
这篇关于《Java集合Map》HashMap实现详解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南