Map中的那些事

Map中的那些事 拓展时间复杂度

其实所谓的时间复杂度，空间复杂度都是数据结构的复杂度，反应程序执行时间随着输入规模的增大而增大的量级，很大程度上反应出算法性能的好坏，这个量级用大写的O加()表示

O(1):常数级

最低复杂程度，使用时间或使用空间与输入数据大小没有关系，无论输入数据多大，使用时间或者使用空间不变，哈希算法就是典型的常数级算法

O(logn):对数级

使用时间或空间随着输入数据增大，复杂度增大为log n倍，log n倍是n为2的几次方的上标值，二分查找就是对数级别算法

O(n):线性级

输入数据增大几倍，时间或空间增大几倍

大部分遍历就是线性级算法

O(nlog n):线性对数级

使用时间或空间随着输入数据增大，复杂度增大为nlogn倍,nlog n倍是n为2的几次方的上标值乘以n二分查找就是对数级算法

O(n²):平方级

输入数据增大几倍，时间或空间增大几的平方倍

冒泡排序就是平方级算法，不过复杂度是从O(n)->O(n²),冒泡排序在数据错位数量很小时适用

O(n³):立方级

输入数据增大几倍，时间或空间增大几的立方倍

O(2的n次方):指数级

输入数据增大几倍，时间或空间增大2的几次方倍

我们都知道，要查找一个元素，如果是顺序查找，那么时间复杂度会达到O(n)，比如：顺序表。也有可能达到O(logn),如：平衡树。那么要想更快，我们就可以考虑另外一种数据结构，他可以达到时间复杂度为O(1)。如

❓：什么是？

是一个key-value模型，具有映射关系，通过key值可以找到value值。并允许使用null值和null键，不保证映射的顺序。

基本知识 哈希冲突的定义

如果两个不同的元素，通过哈希函数得出的实际存储地址相同该如何❓

也就是我们对某个元素进行哈希运算，得到一个存储地址后，然后进行插入的时候，发现该位置已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。由此可见哈希函数的设计至关重要，好的哈希函数会尽可能地保证计算简单和散列地址分布均匀，但是我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突

那么如何解决哈希冲突呢❓

哈希冲突的解决方案有多种：开放地址法(当发生冲突时，继续寻找下一块未被占用的存储地址，然后再放入元素即可)，再散列函数法，链地址法，而即是采用了链地址法，也就是数组+链表的方式。

的实现原理

的主干是一个Entry数组。Entry是的基本组成单元，每个Entry包含一个key-value键值对。

?：的总体结构如下：

简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表(当前entry的next指向null)，那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表。对于添加操作，其时间复杂度为O(n),首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现的越少，性能才会越好。

有四个构造器

其他构造器如果用户没有传入和这两个参数，会使用默认值：默认为16，默认为0.75

具体问题 的内部数据结构

数组+链表/红黑树

允许空键空值吗

最多只允许一个键为Null(多条会覆盖)，但允许多个值为Null

影响性能的重要参数

初始容量：创建哈希表时桶的数量(数组的大小)，默认为16

负载因子：哈希表在其容量扩容之前可以达到一种尺度，默认为0.75

的工作原理

是基于的原理，我们使用put(key,value)存储对象到中，使用get(key)从中获取对象

中put()的工作原理

的底层数组长度为何总是2的n次方

⛵️这里可以使用逆向思维来解释这个问题，我们计算桶的位置完全可以使用h%，如果这个是随便设定值的话当然也可以，但是如果对它进行研究，设计一个合理的值的话，那么将对的性能发生翻天覆地的变化

从上面的图表中我们可以看到，当 为15时总共发生了8次碰撞，同时发现空间浪费非常大，因为在 1、3、5、7、9、11、13、15 这八处没有存放数据。

这是因为hash值在与14（即 1110）进行&运算时，得到的结果最后一位永远都是0，那么最后一位为1的位置即 0001、0011、0101、0111、1001、1011、1101、1111位置处是不可能存储数据的。这样，空间的减少会导致碰撞几率的进一步增加，从而就会导致查询速度慢。

而当为16时， – 1 = 15， 即 1111，那么，在进行低位&运算时，值总是与原来hash值相同，而进行高位运算时，其值等于其低位值。所以，当 =2^n 时，不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询速度也较快。

如果上面这句话大家还看不明白的话，可以多试一些数，就可以发现规律。当为奇数时，-1为偶数，而偶数二进制的最后一位永远为0，那么与其进行 & 运算，得到的二进制数最后一位永远为0，那么结果一定是偶数，那么就会导致下标为奇数的桶永远不会放置数据，这就不符合我们均匀放置，减少冲突的要求了。

JDK1.8中做了哪些优化? 线程安全方面会出现什么问题 线程安全方面会出现什么问题 为什么1.8改用红黑树

比如某些人通过找到你的hash碰撞值，来让你的不断地产生碰撞，那么相同key位置的链表就会不断增长，当你需要对这个的相应位置进行查询的时候，就会去循环遍历这个超级大的链表，性能及其地下。java8使用红黑树来替代超过8个节点数的链表后，查询方式性能得到了很好的提升，从原来的是O(n)到O(logn)。

负载因子

的默认负载因子为0.75，如果超过0.75，会重新一个原来长度两倍的,并且重新调用hash方法，对原来的数据进行重新的hash。

负载因子=存储的元素个数/数组的长度

中的()和()的都有什么作用？

通过key.()进行，并计算下标(n-1&hash),从而获得的位置。如果产生碰撞，则利用key.()方法去链表或树中去查找对应的节点，另外也是为了保持数据一致性

和的区别有哪些？ 使用场景

在包java.util.下，和不同的是专门处理，但是在很多地方是类似的，比如底层都是数组+链表+红黑树、数组大小都是2的幂次方等…

CAS算法

CAS可以看做是乐观锁的一种实现方式，Java原子类中的递增操作就是通过CAS自旋实现的

CAS全称 and Swap(比较与交换)，是一种无锁算法。在不使用锁（没有线程被阻塞）的情况下实现多线程之间的变量同步。

CAS涉及到三个属性：

CAS具体执行时，当且仅当预期值A符合内存地址V中存储的值时，就用新值U替换掉旧值，并写入到内存地址V中。否则不做更新。

源码实现

CAS在JDK中是基于类实现的，它是个跟底层硬件CPU指令通讯的复制工具类，源码如下：

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

在JDK中使用CAS比较多的应该是相关的类，我们以原子整型类为例，分析CAS底层实现机制：

AtomicInteger atomicInteger = new AtomicInteger();
atomicInteger.incrementAndGet();

是类中的方法，它以原子方式对当前值加1，源码如下：

//以原子方式对当前值加1，返回的是更新后的值
 public final int incrementAndGet() {
        return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
 }

Ps:最后还要+1是因为方法返回的是更新的值，而我们要的是更新后的值

==内存偏移量就是用来获取value的，==如下所示：

//获取unfase对象
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;
private volatile int value;//实际变量的值
    static {
        try {// 获得value在AtomicInteger中的偏移量
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

value是有关键字修饰的，为了保证在多线程下内存可见性。

从代码块可以看到在类加载时就已经进行初始化了。

//var1-对象、var2-内存偏移量、var4-增加的值
public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;//期望值
        do {
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
        
        return var5;
    }
//根据偏移量获取value    
public native int getIntVolatile(Object var1, long var2);
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

源码也不是很复杂，主要搞懂各个参数的意思，方法获取到期望值value后调用方法，失败则进行重试。

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

对于上面的参数可以换个理解方式

unsafe.compareAndSwapInt(this, valueOffset, expect, update)

如果原子变量中的value值等于，则使用值更新该值并返回true，否则返回false。

ABA

CAS也不是万能的，它也存在着一些问题，比如ABA，我们来看看什么是ABA？

A–>B—>A 问题，假设有一个变量 A ，修改为B，然后又修改为了 A，实际已经修改过了，但 CAS 可能无法感知，造成了不合理的值修改操作。

为了解决这个 ABA 的问题，我们可以引入版本控制，例如，每次有线程修改了引用的值，就会进行版本的更新，虽然两个线程持有相同的引用，但他们的版本不同，这样，我们就可以预防 ABA 问题了。Java 中提供了 ce 这个类，就可以进行版本控制了。

开销

CAS算法需要不断地自旋来读取最新的内存值，当长时间读取不到就会造成不必要的CPU开销。

Java 8推出了一个新的类，他就是尝试使用分段CAS以及自动分段迁移的方式来大幅度提升多线程高并发执行CAS操作的性能！

简单来说就是如果发现并发更新的线程数量过多，就会开始施行分段CAS的机制，也就是内部会搞一个Cell数组，每个数组是一个数值分段。这时，让大量的线程分别去对不同Cell内部的value值进行CAS累加操作，这样就把CAS计算压力分散到了不同的Cell分段数值中了！