集合概述

首先，我们来对学过的集合知识进行一个回顾，集合：分为单列结合和双列集合。

单列集合

双列集合

HashTable

① Hashtable 是线程安全的,因为Hashtable 内部的方法基本都经过synchronized 修饰。
② 效率：因为线程安全的问题，HashMap 要比 Hashtable 效率高一点，在开发中基本不用。
③Hashtable 不允许有 null 键和 null 值，否则会抛出NullPointerException
④初始容量大小和每次扩充容量：①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。
创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的
大小，而 HashMap 会将其扩充为2 的幂次方大小（HashMap 中的
tableSizeFor()方法保证。
⑤底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）（将链表转换成红黑树前会判断，如果当前数组的长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。 Hashtable 没有这样的机制。

HashMap和HashTable有什么区别?
①、HashMap是线程不安全的,HashTable是线程安全的;
②、由于线程安全,所以HashTable的效率比不上HashMap;
③、HashMap最多只允许一条记录的键为null,允许多条记录的值为null,而HashTable不允许;
④、HashMap默认初始化数组的大小为16,HashTable为11,前者扩容时,扩大两倍,后者扩大两倍+1;
⑤、HashMap需要重新计算hash值,而HashTable直接使用对象的hashCode;

Properties

读取.properties配置文件

 //使用反射，解开Demo03类和Student类的耦合//1.读取配置文件my.propertiesProperties pro = new Properties();  //声明try (FileReader in = new FileReader("my.properties")) {pro.load(in);  // 方法} catch (FileNotFoundException e) {e.printStackTrace();} catch (IOException e) {e.printStackTrace();}//2.反射Class aClass = Class.forName(pro.getProperty("className")); //取值Object obj = aClass.getConstructor().newInstance();//以上2步相当于：Student stu = new Student();Method methodName = aClass.getMethod(pro.getProperty("methodName"));  //取值methodName.invoke(obj);//以上2步相当于：stu.show()

HashMap底层数据结构

我们都知道在JDK1.8之中HashMap的底层数据结构是哈希表也就是
数组+链表/红黑树，那么什么是链表，什么是红黑树呢？

哈希表

哈希表，也叫散列表，是一种通过映射函数将数据元素的关键字映射为存储地址的的数据结构。映射函数叫做散列函数，存放记录的数组叫做散列表。

那么问题来了，如果不同的关键字映射到同一个地址怎么办？这也是我们接下来讲解的哈希冲突！

哈希冲突

通过散列函数确定的位置已经存放了其它的元素，则说其发生了哈希冲突，解决方案呢？常见的有两种拉链法和开放地址法，源码采用的是第一种，拉链法。

拉链法

开放定址法

红黑树

红黑树定义

没有子节点的节点叫做外部节点或叶节点

红黑树

非红黑树

红黑树的插入

链表和红黑树在HashMap中的体现

这里显示了HashMap中的链表实现方式和红黑树的方式，大家可以看出上面有一些说明，在什么情况下使用红黑树，在什么情况下使用链表，这就是我们要说的下一个问题，HashMap的扩容机制

9.拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?为什么不一直使用红黑树?

之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持"平衡"是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。

HashMap的扩容机制

HashMap初始化

在定义HashMap时，可以指定其初始容量的大小，也就是数组的长度，不指定 数组的长度默认为16 ， 负载因子为(0.75)，也就是默认情况下在第一次初始化完成后，当元素数量达到12时哈希表就会进行扩容，扩容为2N也就是原来的2倍。

HashMap扩容

看完上面的内容你心中是否也有这样的疑问？没关系，一个一个来看!

先添元素后扩容

在jdk1.8中，在元素进行插入操作时，会把元素先插入插入到链表中，然后再判断是否达到扩容的条件，也就是是否大于负载因子，如果大于就进行扩容。

什么情况下扩容

一种就是大于负载因子
一种就是链表元素大于8而数组长度小于64

怎么扩容

当达到以上的扩容条件时，数组的容量为变为原来的2倍。
HashMap的扩容是什么

进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。

HashMap在进行扩容时，使用的rehash方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n-1)&hash的结果相比，只是多了一个bit位，所以结点要么就在原来的位置，要么就被分配到"原位置+旧容量"这个位置。

为什么是扩容是2N

JDK源码作者就发现了
第一：当length为2的N次方的时候，h & (length-1) = h % length
为什么&效率更高呢？因为位运算直接对内存数据进行操作，不需要转成十进制，所以位运算要比取模运算的效率更高
第二：当length为2的N次方的时候，数据分布均匀，减少冲突

位运算比%运算要快，也正好解释了为什么 HashMap 的数组长度要取 2 的整数幂。

扩容流程（2N重新计算Hash值）

数组变为原来的2倍，hash地址也要重现结算，但是计算是比较方便的，扩容后的元素地址要么为原来的原地址，要么为原地址+原数组长度。

计算 k 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标index。

扩容的时候为什么 1.8 不用重新 hash 就可以直接定位原节点在新数据的位置呢?

这是由于扩容是扩大为原数组大小的 2 倍，用于计算数组位置的掩码仅仅只是高位多了一个 1，怎么理解呢？ 扩容前长度为
16，用于计算(n-1) & hash 的二进制 n-1 为 0000 1111，扩容为 32 后的二进制就高位多了 1，为 0001
1111。 因为是& 运算，1 和任何数 & 都是它本身，那就分二种情况，如下图：原数据 hashcode 高位第 4 位为 0 和高位为
1 的情况； 第四位高位为 0，重新 hash 数值不变，第四位为 1，重新 hash 数值比原来大 16（旧数组的容量）

怎么保证初始化时表长度为2的N次幂

在初始化时会调用tableSizeFor方法进行一个计算，保证初始化时的容量为2的n次幂。

static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;  //位或运算法  将其转化为2进制进行或运算n |= n >>> 2;  //无符号右移n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; // ③ 判断是否超过最大容量
}

将n-1得到的值转成2进制之后，从1的最高位开始将低16位的数全部转化为1，再加1之后就可以得到一个2^n的数，这个我做了一个实验就是16时会怎样16个数0-15，16的话会变为31的结果+1return就是32。
扩容阈值threshold的最大值就是Integer.MAX_VALUE=2^31-1;
4个字节，32位，高16位和低16位

红黑树转换

在链表中的节点数大于（阈值）8时，会有链表转换为红黑树的倾向，但是需要先判断一下数组的容量是否>=64,如果数组的长度小于64，会先进行扩容，数组的容量为变为原来的2倍。当然，如果红黑树的节点变<6时，桶的数据结构也会退化为链表，主要是为了保证一个效率问题。
那么问题又来了，

为什么变为红黑树是8而退化为链表时又是6呢？

在前面，我们已经介绍过，之所以要转化为红黑树，是因为红黑树的查询效率比链表高，是O（logn），而链表的是O（n），
两者对比效率怎么样
举个相对比较直观的例子，查找一个1-100的随机数，O（Logn）的查找次数是7次，而o（n）是这个（1+100）* 100 /2*1/100。

再有就是，相关研究经过计算，在 hash 函数设计合理的情况下，发生 hash 碰撞 8 次的几率为百万分之 6，概率说话。因为 8
够用了，至于为什么转回来是 6，因为如果 hash 碰撞次数在 8 附近徘徊，会一直发生链表和红黑树的转化，为了预防这种情况的发生。

HashMap中的哈希函数

hash 函数是先拿到通过 key 的 hashcode，是 32 位的 int 值，然后让
hashcode 的高 16 位和低 16 位进行异或操作。

异或运算 ： 相同为0，不同为1.

为什么要用异或运算符?
保证了对象的hashCode的32位值只要有一位发生改变,整个hash()返回值就会改变。尽可能的减少碰撞。

为什么这么设计

这个也叫扰动函数，这么设计有二点原因：

一定要尽可能降低 hash 碰撞，越分散越好；
算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；

为什么采用 hashcode 的高 16 位和低 16 位异或能降低 hash 碰撞？hash 函数能不能直接用 key 的 hashcode？

因为 key.hashCode()函数调用的是 key 键值类型自带的哈希函数，返回 int 型散列值。int 值范围为-2147483648~2147483647，前后加起来大概 40 亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。你想，如果 HashMap 数组的初始大小才 16，用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。(来自知乎-胖君)

源码中模运算就是把散列值和数组长度-1 做一个"与"操作，位运算比%运算要快。

bucketIndex = indexFor(hash, table.length);static int indexFor(int h, int length) {return h & (length-1);
}

这也正好解释了为什么 HashMap 的数组长度要取 2 的整数幂。因为这样（数组长度-1）正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度 16 为例，16-1=15。2 进制表示是 00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。

  11000100 00100101
& 00000000 00001111
----------------------------------00000000 00000101    //高位全部归零，只保留末四位

但这时候问题就来了，这样就算我的散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，如果正好让最后几个低位呈现规律性重复，碰撞也会很严重。

右位移 16 位，正好是 32bit 的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

最后我们来看一下 Peter Lawley 的一篇专栏文章《An introduction to optimising a hashing strategy》里的的一个实验：他随机选取了 352 个字符串，在他们散列值完全没有冲突的前提下，对它们做低位掩码，取数组下标。
结果显示，当 HashMap 数组长度为 512 的时候（2929），也就是用掩码取低 9 位的时候，在没有扰动函数的情况下，发生了 103 次碰撞，接近 30%。而在使用了扰动函数之后只有 92 次碰撞。碰撞减少了将近 10%。看来扰动函数确实还是有功效的。
另外 Java1.8 相比 1.7 做了调整，1.7 做了四次移位和四次异或，但明显 Java 8 觉得扰动做一次就够了，做 4 次的话，多了可能边际效用也不大，所谓为了效率考虑就改成一次了。

面试题

今天看一个关于HashMap的性能问题：如果HashMap只装载100个元素，new HashMap(int
x)中x的最佳值是多少，为什么？

答案：256。

解析：题意是令加载因子取默认值0.75，此时HashMap的初始容量可以设为100/0.75 = 133.33，向上取整为134。
无论你的HashMap(int
x)中的x设置为多少，HashMap的大小都是2n，而且2n是大于x的第一个数，故大于134的第一个2^n无疑是256。

put方法的执行流程

流程图

HashMap是采用的懒加载机制，也就是说在执行new HashMap()的时候，构造方法并没有在构造出HashMap实例的同时也把HashMap实例里所需的数组给初始化。那么，什么时候才去初始化里面的数组呢？答案是在第一次用到数组的时候才会去初始化它，就是在向HashMap里面添加元素的时候。而初始化数组时，它的容量是怎么确定的呢？有两种情况：
第一种是调无参构造函数初始化实例。此时默认的数组初始化长度就是16，在后续添加元素时，进行数组初始化。
第二种是调用带数组容量参数的构造函数。

ConCurrentHashMap线程安全的HashMap

HashMap是线程不安全的，最常见的一个问题就是数据覆盖，假如说，现在有2个线程，线程A准备向哈希表中插入一个数据，判断该位置上为空，CPU轮询，B线程也正好准备插入操作，计算出在表中的位置，正好是A线程刚才计算的位置，由于A只是判断了还未进行插入，这时候B判断该位置上也为空，成功插入，CPU轮询，A线程直接插入，B数据被覆盖。

ConCurrentHashMap线程安全原理

Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以实现线程安全的 Map。

解决线程同步的三个方案：

1.同步代码块

//锁对象：必须是一个唯一的对象（同一个地址）
synchronized(锁对象){  //...访问共享数据的代码...}

// 小明 小红线程同时过来的
public void drawMoney(double money) {// 先搞清楚是谁来取钱？String name = Thread.currentThread().getName();// 1、判断余额是否足够// this正好代表共享资源！synchronized (this) {if(this.money >= money){System.out.println(name + "来取钱" + money + "成功！");this.money -= money;System.out.println(name + "来取钱后，余额剩余：" + this.money);}else {System.out.println(name + "来取钱：余额不足~");}}
}

如何选择锁对象：
1.建议把共享资源作为锁对象, 不要将随便无关的对象当做锁对象
2.对于实例方法，建议使用this作为锁对象
3.对于静态方法，建议把类的字节码(类名.class)当做锁对象

2.同步方法

// 同步方法
public synchronized void drawMoney(double money) {// 先搞清楚是谁来取钱？String name = Thread.currentThread().getName();// 1、判断余额是否足够if(this.money >= money){System.out.println(name + "来取钱" + money + "成功！");this.money -= money;System.out.println(name + "来取钱后，余额剩余：" + this.money);}else {System.out.println(name + "来取钱：余额不足~");}
}

同步方法也是有锁对象，只不过这个锁对象没有显示的写出来而已。
1.对于实例方法，锁对象其实是this（也就是方法的调用者）
2.对于静态方法，锁对象时类的字节码对象（类名.class）

3.Lock锁
Lock锁是JDK5版本专门提供的一种锁对象，通过这个锁对象的方法来达到加锁，和释放锁的目的，使用起来更加灵活。

1.首先在成员变量位子，需要创建一个Lock接口的实现类对象（这个对象就是锁对象）private final Lock lk = new ReentrantLock();
2.在需要上锁的地方加入下面的代码lk.lock(); // 加锁//...中间是被锁住的代码...lk.unlock(); // 解锁

// 创建了一个锁对象
private final Lock lk = new ReentrantLock();public void drawMoney(double money) {// 先搞清楚是谁来取钱？String name = Thread.currentThread().getName();try {lk.lock(); // 加锁// 1、判断余额是否足够if(this.money >= money){System.out.println(name + "来取钱" + money + "成功！");this.money -= money;System.out.println(name + "来取钱后，余额剩余：" + this.money);}else {System.out.println(name + "来取钱：余额不足~");}} catch (Exception e) {e.printStackTrace();} finally {lk.unlock(); // 解锁}}
}

几种线程安全的Map集合

HashTable 是直接在操作方法上加 synchronized 关键字，锁住整个数组，粒度比较大，Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；ConcurrentHashMap 使用分段锁，降低了锁粒度，让并发度大大提高。

粒度，就是锁的范围

Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。
当一个线程访问同步方法时，其他线 程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素， 另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激 烈效率越低。

ConcurrentHashMap 的分段锁的实现原理

ConcurrentHashMap 成员变量使用 volatile 修饰，免除了指令重排序，同时保证内存可见性，另外使用 CAS 操作和 synchronized 结合实现赋值操作，多线程操作只会锁住当前操作索引的节点。

分段锁(Segment)设计

ConcurrentHashMap将哈希表分成多个小的哈希表（Segment），每个Segment都是一个独立的哈希表，可以独立地进行添加、删除操作等，每个Segment都有自己的锁，所以操作不同的Segment时互不干扰。这种设计方式实现了锁的细粒度控制，避免了锁的大力度竞争，提高了并发度。

CAS：
CAS是英文单词Compare and Swap的缩写，翻译过来就是比较并替换。

CAS机制中使用了3个基本操作数：内存地址V，旧的预期值A，要修改的新值B。

更新一个变量的时候，只有当变量的预期值A和内存地址V当中的实际值相同时，才会将内存地址V对应的值修改为B。

举例：

1. 在内存地址V当中，存储着值为10的变量。
   

2. 此时线程1想把变量的值增加1.对线程1来说，旧的预期值A=10，要修改的新值B=11.

3. 在线程1要提交更新之前，另一个线程2抢先一步，把内存地址V中的变量值率先更新成了11。

4. 线程1开始提交更新，首先进行A和地址V的实际值比较（就是将旧的地址值10和内存地址V中的进行比较），发现A不等于V的实际值，提交失败。

5. 线程1 重新获取内存地址V的当前值，并重新计算想要修改的值。此时对线程1来说，A=11，B=12。这个重新尝试的过程被称为自旋。

6. 这一次比较幸运，没有其他线程改变地址V的值。线程1进行比较，发现A和地址V的实际值是相等的。

7. 线程1进行交换，把地址V的值替换为B，也就是12.

Volatile关键字：
当一个共享变量被volatile修饰时，它会保证修改的值会立即被更新到主内存，当有其他线程需要读取时，它会去内存中读取新值。

从思想上来说，synchronized属于悲观锁，悲观的认为程序中的并发情况严重，所以严防死守，CAS属于乐观锁，乐观地认为程序中的并发情况不那么严重，所以让线程不断去重试更新。

在java中除了上面提到的Atomic系列类，以及Lock系列类夺得底层实现，甚至在JAVA1.6以上版本，synchronized转变为重量级锁之前，也会采用CAS机制。

CAS的缺点：

1） CPU开销过大

在并发量比较高的情况下，如果许多线程反复尝试更新某一个变量，却又一直更新不成功，循环往复，会给CPU带来很到的压力。

2） 不能保证代码块的原子性

CAS机制所保证的只是一个变量的原子性操作，而不能保证整个代码块的原子性。比如需要保证3个变量共同进行原子性的更新，就不得不使用synchronized了。
————————————————
版权声明：本文为CSDN博主「MXin5」的原创文章，遵循CC 4.0 BY-SA
原文链接：https://blog.csdn.net/m0_64210833/article/details/126294540

HashMap和ConcurrentHashMap的区别总结

（1）HashMap不是线程安全的，而ConcurrentHashMap是线程安全的。

（2）ConcurrentHashMap采用锁分段技术，将整个数组进行了分段segment，也就是将这个大的数组分成了几个小的片段segment（部分），而且每个小的片段segment上面都有锁存在，那么在插入元素的时候就需要先找到应该插入到哪一个片段segment，然后再在这个片段上面进行插入，而且这里还需要获取segment锁。

（3）ConcurrentHashMap让锁的粒度更精细一些（不会对整个数组进行加锁），并发性能更好。

JDK1.8中的优化以及和JDK1.7的区别

环链 1.7扩容源码

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);e.next = newTable[i]; //A 线程如果执行到这一行挂起，B 线程开始进行扩容newTable[i] = e;e = next;}}}

这个过程为，先将A复制到新的hash表中，然后接着复制B到链头（A的前边：B.next=A），本来B.next=null，到此也就结束了（跟线程二一样的过程），但是，由于线程二扩容的原因，将B.next=A，所以，这里继续复制A，让A.next=B，由此，环形链表出现：B.next=A; A.next=B

1.8 还有三点主要的优化：
数组+链表改成了数组+链表或红黑树；
链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后；
扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，位置不变或索引+旧容量大小；
在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；
为什么要做这几点优化；

在java1.8中,如果链表的长度超过了8,那么链表将转换为红黑树。(桶的数量必须大于64,小于64的时候只会扩容)

发生hash碰撞时,java1.7会在链表的头部插入,而java1.8会在链表的尾部插入

在java1.8中,Entry被Node替代(换了一个马甲)。

参考文章链接：
https://blog.csdn.net/xiaoanzi123/article/details/106896571
https://blog.csdn.net/citywu123/article/details/122125093
https://blog.csdn.net/QGhurt/article/details/107323702