侧边栏壁纸
博主头像
晓果冻博主等级

行动起来,活在当下

  • 累计撰写 135 篇文章
  • 累计创建 16 个标签
  • 累计收到 91 条评论

目 录CONTENT

文章目录

HashMap相关问题

Administrator
2022-04-11 / 0 评论 / 2 点赞 / 415 阅读 / 5752 字

HashMap相关问题

以下内容来自余胜军课堂

image-20220411161725993

image-20220411192849815

HashMap与HashTable之间的区别
  • HashMap实现不同步,线程不安全。 HashTable线程安全 HashMap中的key-value都是存储在Entry中的。
  • 继承不同。
    • Hashtable 继承 Dictionary 类,而 HashMap 继承 AbstractMap
    • public class Hashtable extends Dictionary implements Map
    • public class HashMap extends AbstractMap implements Map
  • Hashtable中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下,可以直接使用Hashtable,但是要使用HashMap的话就要自己增加同步处理了。
  • Hashtable 中, key 和 value 都不允许出现 null 值。 在 HashMap 中, null 可以作为键,这样的键只有一个;可以有一个或多个键所对应的值为 null 。
    • 当 get() 方法返回 null 值时,即可以表示 HashMap 中没有该键,也可以表示该键所对应的值为 null 。因此,在 HashMap 中不能由 get() 方法来判断 ,HashMap 中是否存在某个键, 而应该用 containsKey() 方法来判断。
  • 哈希值的使用不同,HashTable直接使用对象的hashCode。而HashMap重新计算hash值 。
时间复杂度O(n)、(O(1))、(O(logn))
  • 时间复杂度为O(n) 从头查询到尾部,查询多次

  • 时间复杂度为O(1) 查询一次 比如根据数组下标查询

  • 时间复杂度为O(logn) 平方查询 比如红黑树

为什么重写equals还要重写hashcode方法
  • Object 的 hashcode 方法是本地方法,也就是用 c 或 c++ 实现的,该方法直接返回对象的内存地址,让后再转换整数。

  • Equals方法:

  • 两个对象的Hashcode值相等,但是两个对象的内容值不一定相等;---Hash冲突的问题
    image-20220411181708400

  • 两个对象的值Equals比较相等的情况下,则两个对象的Hashcode值一定相等;
    image-20220411185630203
    image-20220411190645541

  • == 比较两个对象的内存地址是否相同、Equals默认的情况下比较两个对象的内存地址

  • 【强制】关于 hashCode 和 equals 的处理,遵循如下规则:

    • 只要覆写 equals,就必须覆写 hashCode。
    • 因为 Set 存储的是不重复的对象,依据 hashCode 和 equals 进行判断,所以 Set 存储的对象必须覆写这两个方法。
    • 如果自定义对象作为 Map 的键,那么必须覆写 hashCode 和 equals。说明:String 已覆写 hashCode 和 equals 方法,所以我们可以愉快地使用 String 对象作为 key 来使用。
异或运算^无符号右移>>>&与运算
1.<<(向左位移) 针对二进制,转换成二进制后向左移动2位,后面用0补齐
10的二进制1010
  0000 0000 0000 0000 0000 0000 0000 1010 ---32位
  0000 0000 0000 0000 0000 0000 0010 1000
System.out.println(10 << 2);//1010 =40
2.>>(向右位移) 针对二进制,转换成二进制后向右移动2位,操作数移除右边界的位被屏蔽 正数高位
补0 负数补1
10的二进制1010
0000 0000 0000 0000 0000 0000 0000 1010
System.out.println(10 >> 2);//10=2
3.>>>(不带符号右移) 针对二进制,转换成二进制后向右移动2位,操作数移除右边界的位被屏蔽
正数高位 补0 负数补0

异或运算^ 针对二进制,相同的为0,不同的为1
0010 --2
0011 --3
0001 --1
4.&(与运算) 针对二进制,00的0 11的1 10 的0
0010--2
0011--3
0010--2
HashMap底层是有序存放的吗
  • 无序、散列存放

  • 遍历的时候从数组0开始遍历每个链表,遍历结果存储顺序不保证一致。

  • 如果需要根据存储顺序保存,可以使用LinkedHashMap底层是基于双向链表存放

    • LinkedHashMap基于双向链表实现
    • HashMap基本单向链表实现
LinkedHashMap实现缓存淘汰框架
  • LRU(最近少使用)缓存淘汰算法
  • LFU(最不经常使用算法)缓存淘汰算法
  • ARC(自适应缓存替换算法)缓存淘汰算法
  • FIFO(先进先出算法)缓存淘汰算法
  • MRU(最近最常使用算法)缓存淘汰算法
LinkedHashMap基于双向链表实现,可以分为插入或者访问顺序两种,采用双链表的形式保证有序可以根据插入或者读取顺序

LinkedHashMap是HashMap的子类,但是内部还有一个双向链表维护键值对的顺序,每个键值对既位于哈希表中,也位于双向链表中。LinkedHashMap支持两种顺序插入顺序 、 访问顺序

插入顺序:先添加的在前面,后添加的在后面。修改操作不影响顺序
执行get/put操作后,其对应的键值对会移动到链表末尾,所以最末尾的是最近访问的,最开始的是最久没有被访问的,这就是访问顺序。
其中参数accessOrder就是用来指定是否按访问顺序,如果为true,就是访问顺序,false根据新增顺序
HashMap如何降低Hash冲突概率
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
modCount的作用
我们知道 java.util.HashMap 不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map,那么将抛出ConcurrentModificationException,这就是所谓fail-fast策略。这一策略在源码中的实现是通过 modCount 域,modCount 顾名思义就是修改次数,对HashMap 内容的修改都将增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。在迭代过程中,判断 modCount 跟 expectedModCount 是否相等,如果不相等就表示已经有其他线程修改了 Map:
HashMap加载因子为什么是0.75而不是1或者0.5
产生背景:减少Hash冲突index的概率;
查询效率与空间问题;

简单推断的情况下,提前做扩容:
1.如果加载因子越大,空间利用率比较高,有可能冲突概率越大;
2.如果加载因子越小,有可能冲突概率比较小,空间利用率不高;
空间和时间上平衡点:0.75
统计学概率:泊松分布是统计学和概率学常见的离散概率分布
HashMap8扩容底层原理
将原来的链表拆分两个链表存放; 低位还是存放原来index位置 高位存放index=j+原来长度
if ((e.hash & oldCap) == 0) { 由于oldCap原来的容量没有减去1 所以所有的hash&oldCap
为0或者1;
实例:

3&16=0
0000 0003
0001 0000
0000 0000 
4&16=0
0000 0100
0001 0000
0000 0000
16&16=16
0001 0000
0001 0000
0001 0000
17&16=16
0001 0001
0001 0000
0001 0000
HashMap如何存放1万条key效率最高
  • (需要存储的元素个数 / 负载因子) + 1
  • 10000/0.75+1=13334

img

JDK1.8ConcurrentHashMap源码解读
  • ConcurrentHashMap1.8的取出取消segment分段设计,采用对CAS + synchronized保证并发线程安全问题,将锁的粒度拆分到每个index,下标位置,实现的效率与ConcurrentHashMap1.7相同。

img

  • 源码解读
sizeCtl :默认为0,用来控制table的初始化和扩容操作,具体应用在后续会体现出来。
-1 代表table正在初始化
N 表示有N-1个线程正在进行扩容操作
其余情况:
1、如果table未初始化,表示table需要初始化的大小。 0
2、如果table初始化完成,表示table的容量,默认是table大小的0.75倍,居然用这个公式算0.75(n - (n >>> 2))。

CounterCells 记录每个线程size++的次数
2

评论区