HashMap相关问题

以下内容来自余胜军课堂

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冲突的问题
两个对象的值Equals比较相等的情况下，则两个对象的Hashcode值一定相等；
== 比较两个对象的内存地址是否相同、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

JDK1.8ConcurrentHashMap源码解读

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

源码解读

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++的次数

目录CONTENT

HashMap相关问题

HashMap相关问题

HashMap与HashTable之间的区别

时间复杂度O(n)、(O(1))、(O(logn))

为什么重写equals还要重写hashcode方法

异或运算^无符号右移>>>&与运算

HashMap底层是有序存放的吗

LinkedHashMap实现缓存淘汰框架

HashMap如何降低Hash冲突概率

modCount的作用

HashMap加载因子为什么是0.75而不是1或者0.5

HashMap8扩容底层原理

HashMap如何存放1万条key效率最高

JDK1.8ConcurrentHashMap源码解读

评论区