• 作者:老汪软件技巧
  • 发表时间:2024-01-13 06:00
  • 浏览量:

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键值对。

?:的总体结构如下:

Map中的那些事

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

有四个构造器

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

具体问题 的内部数据结构

数组+链表/红黑树

允许空键空值吗

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

影响性能的重要参数

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

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

的工作原理

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

中put()的工作原理

Map中的那些事

的底层数组长度为何总是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中。否则不做更新。

Map中的那些事

源码实现

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分段数值中了!