Map

• 扩容机制:三者均是在插入元素后判断是否需要扩容
• 迭代机制:均使用fail-safe迭代器
  • ConcurrentHashMap和Hashtable是基于容器的克隆进行迭代，不会抛出ConcurrentModificationException异常，但是也不能反映出容器的最新状态；HashMap使用了fail-fast迭代器，它直接对容器进行迭代，因此如果在迭代过程中有其他线程修改了容器结构（增加或删除元素），就会抛出ConcurrentModificationException异常。

HashMap

• HashMap的hash算法：HashMap使用了一个自定义的hash函数，它将key的hashCode值的高16位和低16位进行异或运算，然后再与数组长度减一进行按位与运算，得到数组下标。这样做的目的是为了增加hash值的随机性，减少哈希冲突的概率。
• HashMap的扩容机制：HashMap在插入元素后，会判断当前元素个数是否超过了数组长度乘以负载因子（默认为0.75）的阈值，如果超过了，就会触发扩容操作。扩容操作会将数组长度翻倍，并重新计算每个元素的位置，然后重新插入到新的数组中。这个过程是比较耗时的，所以建议在创建HashMap时，尽量预估容量，避免频繁扩容。
• HashMap的链表转红黑树：HashMap在JDK1.8中引入了一种优化措施，当某个数组位置上的链表长度超过了8（TREEIFY_THRESHOLD），并且数组长度大于等于64（MIN_TREEIFY_CAPACITY）时，就会将链表转换为红黑树。这样可以提高查找效率，因为红黑树是一种平衡二叉树，它的查找时间复杂度是O(logn)，而链表的查找时间复杂度是O(n)。反之，如果某个数组位置上的红黑树节点个数小于等于6（UNTREEIFY_THRESHOLD），就会将红黑树退化为链表。
• HashMap的线程不安全问题：HashMap是线程不安全的，如果在多线程环境下对它进行并发修改，可能会导致一些问题，比如死循环、数据丢失、数据不一致等。这是因为多线程同时修改HashMap时，可能会造成hash冲突、扩容竞争、链表环形等情况。为了解决这个问题，可以使用同步包装类Collections.synchronizedMap()或者并发类ConcurrentHashMap来代替HashMap。
• HashMap和Hashtable的区别：Hashtable是一个早期的散列表实现类，它和HashMap有很多相似之处，但也有一些区别。主要区别有：Hashtable是线程安全的，而HashMap是线程不安全的；Hashtable不允许使用null作为键或值，而HashMap允许；Hashtable使用Enumeration接口作为迭代器，而HashMap使用Iterator接口作为迭代器；Hashtable的初始容量是11，扩容后是原来的2倍加1，而HashMap的初始容量是16，扩容后是原来的2倍。

HashMap线程不安全的问题:

数据丢失：当多个线程同时对同一个HashMap进行put操作时，如果其中一个线程触发了扩容，那么其他线程可能会看到一个不一致的状态，导致某些元素没有被正确复制到新的数组中，或者被其他线程覆盖掉。
死循环：当多个线程同时对同一个HashMap进行put操作时，如果其中一个线程触发了链表转换为红黑树的操作，那么其他线程可能会看到一个不完整的树结构，导致在遍历或者插入时陷入无限循环。

HashMap的死锁:

HashMap的put操作是这样导致死锁的：当HashMap的容量达到阈值时，它会进行扩容，即重新分配一个更大的数组，并将原来的元素重新计算哈希值并插入到新的数组中。这个过程中，它使用了头插法，即将新的元素插入到链表的头部。如果在多线程环境下，两个线程同时对同一个链表进行扩容操作，可能会导致链表的循环或者断裂。例如，假设有两个线程A和B，它们同时对一个链表进行扩容操作，如下图所示1：

1. 线程A先执行transfer方法，将原来的链表分成两部分，一部分是1->2->3->null，另一部分是4->null。
2. 线程A将1->2->3->null插入到新的数组中，此时新数组的第一个位置是3->2->1->null。
3. 线程B开始执行transfer方法，由于它还没有看到线程A的修改，它仍然认为原来的链表是1->2->3->4->null。
4. 线程B将1->2->3->4->null插入到新的数组中，此时新数组的第一个位置是4->3->2->1->null。
5. 线程A继续执行transfer方法，将4->null插入到新的数组中，由于它使用了头插法，它将4插入到了3的前面，此时新数组的第一个位置是4->4->3->2->1->null。注意这里出现了两个4，并且形成了一个循环链表。
6. 当其他线程对这个位置进行get操作时，就会陷入死循环1。

ConcurrentHashMap

ConcurrentHashMap是Java5中支持高并发,高吞吐量的线程安全的HashMap实现

• 其由Segment数据结构和HashEntry数组构成
• egment结构与HashMap类似,是一个数组和链表结构
• 一个Segment包含一个HashEntry数组,每个HashEntry是一个链表,HashEntry用于存储键值对数据
• Segment在ConcurrentHashMap中扮演锁的角色,当修改HashEntry数据时都需要获取对应Segment的锁
• 个别方法是需要锁整个map,比如size(),containsValue(),实现上按顺序锁所有桶,操作之后按顺序释放所有桶

ConcurrentHashMap为什么不支持key或者value为null?

ConcurrentHashMap不支持key或者value为null的原因是为了避免二义性和保证线程安全。

• 如果get方法返回null，无法判断是没有找到对应的key还是存储的值就是null。

• 在多线程环境下，使用null作为key或者value可能会导致空指针异常或者数据不一致。

• ConcurrentHashMap的设计者Doug Lea不喜欢null

  • 理由:如果map.get(key)返回null，你无法判断是key映射到null还是key不存在。在非并发的map中，你可以通过map.contains(key)来检查，但是在并发的map中，map可能在两次调用之间发生了变化。

Hashtable

其所有方法都是同步的,因此是线程安全的,每次操作数据锁的范围是整个map

• 拉链法实现的hash表,其通过数据+链表的方式存储的数据
• 内部refresh方法来扩容,当键值对数量超过阈值时调用
• 扩容阈值:默认为键值对数量 > Entry数组长度 * 0.75,默认大小11
• 扩容大小:newCapacity = oldCapacity * 2 + 1

扩展

异或运算

异或运算是一种二进制运算，它的特点是：

• 异或运算符号是“^”或“⊕”，英文是exclusive OR，缩写为XOR。
• 异或运算的结果是：如果两个输入位不同，输出为1；如果两个输入位相同，输出为0。
• 异或运算具有以下性质：
  • 归零律：x ^ x = 0
  • 恒等律：x ^ 0 = x
  • 交换律：x ^ y = y ^ x
  • 结合律：x ^ (y ^ z) = (x ^ y) ^ z
  • 自反性：x ^ y ^ y = x

异或运算的使用场景有：

• 简化计算：多个值的异或运算可以根据运算性质进行简化，例如 a ^ b ^ c ^ a ^ b = c。
• 交换值：两个变量连续进行三次异或运算，可以互相交换值，例如 x = x ^ y; y = y ^ x; x = x ^ y; 就可以实现 x 和 y 的交换，不需要额外的空间。
• 加密解密：异或运算可以用于加密解密，因为异或运算具有自反性，即明文与密钥进行两次异或运算，就可以还原成明文。例如 text ^ key = cipherText; cipherText ^ key = text。
• 数据备份：异或运算可以用于数据备份，因为异或运算具有归零律和恒等律。例如 x ^ y = z; 则 x ^ z = y; y ^ z = x。这样就可以利用一个备份文件 z 来恢复任意一个损坏的文件 x 或 y。
• 算法题目：异或运算可以用于一些面试的算法题目，例如找出数组中缺失的数字、重复的数字、只出现一次的数字等。