首页 > 其他分享 >HashMap 的长度为什么是 2 的 N 次方?HashMap 与 ConcurrentHashMap 的异同

HashMap 的长度为什么是 2 的 N 次方?HashMap 与 ConcurrentHashMap 的异同

时间:2023-09-25 19:00:50浏览次数:34  
标签:ConcurrentHashMap HashMap JDK1.8 链表 数组 次方

一、HashMap 的长度为什么是 2 的 N 次方

为了能让HashMap存数据和取数据的效率高,尽可能地减少hash值碰撞,也就是说尽量把数据能平均分配,每个链表或者红黑树长度尽量相等。

取余(%)操作中,如果除数是2的幂次,则等价于与其除数减一的与(&)操作。

即:hash%length == hash &(length -1),这个等式成立的前提是length是2的n次方。

采用二进制位操作&相对于%能够大大提高运算效率。

二、HashMap 与 ConcurrentHashMap 的异同

1、都是key-value形式存储数据;

2、HashMap线程不安全,ConcurrentHashMap是JUC下的线程安全的;

3、HashMap底层数据结构是数组+链表(JDK1.8之前)。JDK1.8之后是数组+链表+红黑树。当链表中元素个数达到8的时候,链表的查询速度不如红黑树快,链表会转为红黑树;

4、HashMap初始数组大小为16(默认),当出现扩容时,以0.75*数组大小的方式进行扩容;

5、ConcurrentHashMap在JDK1.8之前是采用分段锁来实现的Segment+HashEntry,Segment数组大小默认是16,2的n次方;JDK1.8之后采用Node+CAS+Synchronized来保证并发安全的实现

标签:ConcurrentHashMap,HashMap,JDK1.8,链表,数组,次方
From: https://blog.51cto.com/u_16255459/7598426

相关文章

  • lambda HashMap 排序
    目录TreeMaplambdacomparingByKey示例代码TreeMap按key排序生成map可以有TreeMap完成,TreeMap可以按key的自然顺序排序(Comparable实现)lambdacomparingByKey使用lambda也可以很方便的对map排序Map.Entry.comparingByKey()按key排序的ComparatorMap.Entry.comparingBy......
  • HashMap源码解析
    HashMap简介HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键,但最多只允许一条记录的键为null。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长。HashMap是......
  • HashMap的实现原理
    HashMap的数据结构:底层使用hash表数据结构,即数组和链表或红黑树当我们往HashMap中put元素时,利用key的hashCode重新hash计算出当前对象元素在数组中的下标存储时,如果出现hash值相同的key,此时有两种情况如果key相同,则覆盖原始值如果key不同(出现冲突),则将当前的key-value放入链......
  • HashMap常见面试题
    简介HashMap最早出现在JDK1.2中,底层基于散列算法实现。HashMap允许null键和null值,是非线程安全类,在多线程环境下可能会存在问题。1.8版本的HashMap数据结构:为什么有的是链表有的是红黑树?默认链表长度大于8时转为树结构Node是HhaspMap中的一个静态内部类://Node是单向链表,实现......
  • HashMap常见面试题
    简介HashMap最早出现在JDK1.2中,底层基于散列算法实现。HashMap允许null键和null值,是非线程安全类,在多线程环境下可能会存在问题。1.8版本的HashMap数据结构:为什么有的是链表有的是红黑树?默认链表长度大于8时转为树结构Node是HhaspMap中的一个静态内部类://Node......
  • 说说Hashtable 与 HashMap 的区别
    1.出生的版本不一样,Hashtable出生于Java发布的第一版本JDK1.0,HashMap出生于JDK1.2。2.都实现了Map、Cloneable、Serializable(当前JDK版本1.8)。3.HashMap继承的是AbstractMap,并且AbstractMap也实现了Map接口。Hashtable继承Dictionary。4.Hashtable中大部......
  • 求一元二次方程的根
    #include<stdio.h>#include<math.h>intmain(){inta,b,c;scanf("%d%d%d",&a,&b,&c);intd=pow(b,2)-4*a*c;//pow是开根号,要引用math头文件if(d>=0){ intx1; intx2; intx; if(d==0) { x=-b/2*a; pri......
  • 【Android面试】2023最新大厂面试专题一:关于HashMap那些事儿
    1、 请说一说HashMap,SparseArrary原理,SparseArrary相比HashMap的优点、ConcurrentHashMap如何实现线程安全?这道题想考察什么?1、HashMap,SparseArrary基础原理?2、SparseArrary相比HashMap的优点是什么?3、ConcurrentHashMap如何实现线程安全?考察的知识点HashMap,SparseArrary、Concurre......
  • P1024 [NOIP2001 提高组] 一元三次方程求解
    因为精度要求很低,所以有一个暴力的想法就是枚举区间内相差很小的两个数然后判断。保留两位小数后记得判重。考虑优化。发现根与根差的绝对值大于等于\(1\)这个条件没有利用。有了这个条件我们发现相邻两个整数之间(不包含端点)最多有一个根。于是可以先判掉整数然后在区间内有根......
  • hashmap
    (1)HashMap的底层数据结构是什么?haashMap最早是在jdk1.2中开始出现的,一直到jdk1.7一直没有太大的变化。但是到了jdk1.8突然进行了一个很大的改动。其中一个最显著的改动就是:之前jdk1.7的存储结构是数组+链表,到了jdk1.8变成了数组+链表+红黑树。在jdk1.7之中把元素放在一个个数组里......