java集合

List:

List可以一遍遍历一边修改元素吗?

fail-fast 机制决定了“结构修改”会抛异常，因此 **ArrayList** 等集合
不允许在遍历过程中绕开迭代器去增删元素；
但允许通过迭代器自身提供的 **set/add/remove** 安全地修改内容。

ArrayList和LinkedList有什么区别:

ArrayList 是基于数组实现的，LinkedList 是基于链表实现的。

多数情况下，ArrayList 更利于查找，LinkedList 更利于增删。

ArrayList的扩容机制?

计算新容量

创建新数组，将原有数据复制

更新引用

Map:

HashMap的底层数据结构:

数组+链表+红黑树

hash函数:

HashMap的hash函数怎么设计的?

static final int hash(Object key) {
    int h;
    // 如果 key 为 null，返回 0；否则，使用 hashCode 并进行扰动
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

为什么能减少hash冲突?

快速回答：哈希表的索引是通过 h & (n-1) 计算的，n 是底层数组的容量；n-1 和某个哈希值做 & 运算，相当于截取了最低的四位。如果数组的容量很小，只取 h 的低位很容易导致哈希冲突。

通过异或操作将 h 的高位引入低位，可以增加哈希值的随机性，从而减少哈希冲突。

解决hash冲突的方法有哪些?

我知道的有 3 种，再哈希法、开放地址法和拉链法。

用拉链法如何判断Key相等:

1 2	if (e.hash == hash && ((k = e.key) == key \|\| (key != null && key.equals(k))))

put()流程:

计算hash值之后再计算索引

判断是否为空，如果不为空判断是否需要树化

插入后判断是否需要扩容

查找:

根据key值先计算hash值之后再计算索引

判断是否为空如果不为空就判断是否匹配，

如果不匹配就遍历链表或红黑树找匹配的节点

容量:

为什么容量是2的幂次方?

数组长度-1 正好相当于一个“低位掩码”——掩码的低位最好全是 1，这样 & 运算结果会在0到数组长度-1的范围内。

初始化时候传一个17的容量他会怎么处理?

HashMap 会将容量调整到大于等于 17 的最小的 2 的幂次方，也就是 32。

除非是比较大为了防止多次扩容影响效率，一般不回初始化时候传入容量

HashMap的扩容:

扩容发生在什么时候:

当键值对数量超过阈值，也就是容量 * 负载因子时。

默认的负载因子是多少？

0.75。这是个经验值

初始容量是多少？

16。

扩容机制:

扩容时，HashMap 会创建一个新的数组，其容量是原来的两倍。然后遍历旧哈希表中的元素，将其重新分配到新的哈希表中。

如果当前桶中只有一个元素，那么直接通过键的哈希值与数组大小取模锁定新的索引位置：e.hash & (newCap - 1)。

如果当前桶是红黑树，那么会调用 split() 方法分裂树节点，以保证树的平衡。

如果当前桶是链表，会通过旧键的哈希值与旧的数组大小取模 (e.hash & oldCap) == 0 来作为判断条件，如果条件为真，元素保留在原索引的位置；否则元素移动到原索引 + 旧数组大小的位置。

为什么链表转红黑树的阈值是8?

阈值为什么要选 8 呢？和统计学有关。理想情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为 8 的情况，发生概率仅为0.00000006。

至于红黑树转回链表的阈值为什么是 6，而不是 8？是因为如果这个阈值也设置成 8，假如发生碰撞，节点增减刚好在 8 附近，会发生链表和红黑树的不断转换，导致资源浪费。

线程安全问题:

①、多线程下扩容会死循环。JDK7 中的 HashMap 使用的是头插法来处理链表，在多线程环境下扩容会出现环形链表，造成死循环。在JDK8中用尾插法处理解决了这个问题

②、多线程在进行 put 元素的时候，可能会导致元素丢失。因为计算出来的位置可能会被其他线程覆盖掉，比如说一个线程 put 3 的时候，另外一个线程 put 了 7，就把 3 给弄丢了。

③、put 和 get 并发时，可能导致 get 为 null。线程 1 执行 put 时，因为元素个数超出阈值而扩容，线程 2 此时执行 get，就有可能出现这个问题。