每日十题八股-2024年12月7日

1.说说hashmap的负载因子
2.Hashmap和Hashtable有什么不一样的？Hashmap一般怎么用？
3.ConcurrentHashMap怎么实现的？
4.分段锁怎么加锁的？
5.分段锁是可重入的吗？
6.已经用了synchronized，为什么还要用CAS呢？
7.ConcurrentHashMap用了悲观锁还是乐观锁?
8.HashTable 底层实现原理是什么？
9.HashTable线程安全是怎么实现的？
10.hashtable 和concurrentHashMap有什么区别
11.说一下HashMap和Hashtable、ConcurrentMap的区别？

1.说说hashmap的负载因子？

负载因子为0.75。这是代码编写者在基于概率论和分布的知识，权衡了碰撞发生的可能性和空间浪费。负载因子太低会导致大量的空桶浪费空间，负载因子太高会导致大量的碰撞，降低性能。0.75 的负载因子在这两个因素之间取得了良好的平衡。

2.Hashmap和Hashtable有什么不一样的？Hashmap一般怎么用？

最主要的区别就是线程安全与否，hashmap是线程安全的，扩容机制（很明确了，补充一下：插入元素后如果链表长度大于阈值（默认为8），先判断数组长度是否小于64，如果小于，则扩充数组，反之将链表转化为红黑树，如果小于，则扩充数组，反之将链表转化为红黑树）

HashTable，效率低，是因为保证线程同步，对其内部方法都采用了synchronized修饰。且不可以存储null的key和value。初始容量是11，每一次扩容是2n+1，底层是数组+链表。
基本没有人用了，用ConcurrentHashMap。

3.ConcurrentHashMap怎么实现的？

1.7 大数组Segment，小数组+链表的NodeEntry。Segment 是一种可重入锁（ReentrantLock）。
1.8，进行了修改，抛弃了segment，并引入红黑树提高查找效率。对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。
一、使用volatile保证当Node中的值变化时对于其他线程是可见的
二、使用table数组的头结点作为synchronized的锁来保证写操作的安全
三、当头结点为null时，使用CAS操作来保证数据能正确的写入。

volatile V val;
volatile Node<K,V> next;

4.分段锁怎么加锁的？

Segment 本身就继承了 ReentrantLock 具备了锁的功能，在每次 put 前都会先尝试 tryLock() 加锁，如果成功则进行元素存储；如果失败，就会调用 Segment 的 scanAndLockForPut() 尝试循环加锁并扫描指定的 key。

5.分段锁是可重入的吗？

继承的时ReentrantLock。是可重入锁。
任意线程在获取到锁之后能够再次获取该锁而不会被锁阻塞，首先他需要具备两个条件：
线程再次获取锁：所需要去识别获取锁的线程是否为当前占据锁的线程，如果是，则再次获取成功
锁的最终释放：线程重复n次获取了锁，随后在第n次释放该锁后，其它线程能够获取到该锁。锁的最终释放要求锁对于获取进行计数自增，计数表示当前线程被重复获取的次数，而被释放时，计数自减，当计数为0时表示锁已经成功释放。

6.已经用了synchronized，为什么还要用CAS（Compare-And-Swap）呢？

权衡。主要是根据锁竞争程度来判断的：一些部分用到synchronized一些部分用CAS。
在putVal中，如果计算出来的hash槽没有存放元素，那么就可以直接使用CAS来进行设置值，这是因为在设置元素的时候，因为hash值经过了各种扰动后，造成hash碰撞的几率较低，那么我们可以预测使用较少的循环+CAS来完成具体的hash落槽操作。
当发生了hash碰撞的时候说明容量不够用了或者已经有大量线程访问了，当发生了hash碰撞的时候说明容量不够用了或者已经有大量线程访问了。

CAS 是乐观锁，线程执行的时候不会加锁，它会假设此时没有冲突，然后完成某项操作；如果因为冲突失败了就重试，直到成功为止。多用于“读多写少“的环境，避免频繁加锁影响性能。
synchronized是悲观锁。对于悲观锁来说，它总是认为每次访问共享资源时会发生冲突，所以必须对每次数据操作加上锁，以保证临界区的程序同一时间只能有一个线程在执行。多用于”写多读少“的环境，避免频繁失败和重试影响性能。
CAS：因为 CAS 是一种原子操作，它是一种系统原语，是一条 CPU 的原子指令，从 CPU 层面已经保证它的原子性。原本有三个元素，一个是要更新的变量，一个是预期值，一个是更新值。首先查看要更新变量是否是预期值，是的话，说明没有其他线程修改过，赋予新值。否则什么都不做。但失败的线程并不会被挂起，仅是被告知失败，并且允许再次尝试，当然也允许失败的线程放弃操作。
自旋锁。结合着锁来理解的话就是，先获取一次锁，如果获取不到锁，会不停的循环获取，直到获取到。不像普通的锁那样，如果获取不到锁就进入阻塞状态。
自旋锁等于循环+CAS。