JAVA集合和数据结构也是面试常考的点，内容也是比较多。
在看之前希望各位如果方便可以点赞收藏，给我点个关注，创作不易！
JAVA集合
11. HashMap 中 key 的存储索引是怎么计算的？
首先根据key的值计算出hashcode的值，然后根据hashcode计算出hash值，最后通过hash&（length-1）计算得到存储的位置。看看源码的实现：
// jdk1.7
方法一：
static int hash(int h) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode(); // 为第一步：取hashCode值
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
方法二：
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但实现原理一样
return h & (length-1); //第三步：取模运算
}
// jdk1.8
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
/*
h = key.hashCode() 为第一步：取hashCode值
h ^ (h >>> 16) 为第二步：高位参与运算
*/
}
这里的 Hash 算法本质上就是三步：**取key的 hashCode 值、根据 hashcode 计算出hash值、通过取模计算下标。**其中，JDK1.7和1.8的不同之处，就在于第二步。我们来看下详细过程，以JDK1.8为例，n为table的长度。
12. HashMap 的put方法流程？
简要流程如下：
首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标；
如果数组是空的，则调用 resize 进行初始化；
如果没有哈希冲突直接放在对应的数组下标里；
如果冲突了，且 key 已经存在，就覆盖掉 value；
如果冲突后，发现该节点是红黑树，就将这个节点挂在树上；
如果冲突后是链表，判断该链表是否大于 8 ，如果大于 8 并且数组容量小于 64，就进行扩容；如果链表节点大于 8 并且数组的容量大于 64，则将这个结构转换为红黑树；否则，链表插入键值对，若 key 存在，就覆盖掉 value。
13. HashMap 的扩容方式？
HashMap 在容量超过负载因子所定义的容量之后，就会扩容。Java 里的数组是无法自动扩容的，方法是将 HashMap 的大小扩大为原来数组的两倍，并将原来的对象放入新的数组中。
那扩容的具体步骤是什么？让我们看看源码。
先来看下JDK1.7 的代码：
void resize(int newCapacity) { //传入新的容量
Entry[] oldTable = table; //引用扩容前的Entry数组
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
transfer(newTable); //！！将数据转移到新的Entry数组里
table = newTable; //HashMap的table属性引用新的Entry数组
threshold = (int)(newCapacity * loadFactor);//修改阈值
}
这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了旧的Entry数组
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素
if (e != null) {
src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
e.next = newTable[i]; //标记[1]
newTable[i] = e; //将元素放在数组上
e = next; //访问下一个Entry链上的元素
} while (e != null);
}
}
}
newTable[i] 的引用赋给了 e.next ，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到 Entry 链的尾部(如果发生了 hash 冲突的话）。
14. 一般用什么作为HashMap的key?
一般用Integer、String 这种不可变类当 HashMap 当 key，而且 String 最为常用。
- 因为字符串是不可变的，所以在它创建的时候
hashcode就被缓存了，不需要重新计算。这就是HashMap中的键往往都使用字符串的原因。 - 因为获取对象的时候要用到
equals() 和 hashCode() 方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的重写了hashCode() 以及 equals()方法。
15. HashMap为什么线程不安全？
- 多线程下扩容死循环。JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
- 多线程的put可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。
- put和get并发时，可能导致get为null。线程1执行put时，因为元素个数超出threshold而导致rehash，线程2此时执行get，有可能导致这个问题。此问题在JDK 1.7和 JDK 1.8 中都存在。
16. ConcurrentHashMap 的实现原理是什么？
ConcurrentHashMap 在 JDK1.7 和 JDK1.8 的实现方式是不同的。
先来看下JDK1.7
JDK1.7中的ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成，即ConcurrentHashMap 把哈希桶切分成小数组（Segment ），每个小数组有 n 个 HashEntry 组成。
其中，Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色；HashEntry 用于存储键值对数据。
首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问，能够实现真正的并发访问。
再来看下JDK1.8
在数据结构上， JDK1.8 中的ConcurrentHashMap 选择了与 HashMap 相同的数组+链表+红黑树结构；在锁的实现上，抛弃了原有的 Segment 分段锁，采用CAS + synchronized实现更加低粒度的锁。
将锁的级别控制在了更细粒度的哈希桶元素级别，也就是说只需要锁住这个链表头结点（红黑树的根节点），就不会影响其他的哈希桶元素的读写，大大提高了并发度。
17. ConcurrentHashMap 的 put 方法执行逻辑是什么？
先来看JDK1.7
首先，会尝试获取锁，如果获取失败，利用自旋获取锁；如果自旋重试的次数超过 64 次，则改为阻塞获取锁。
获取到锁后：
- 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。 - 不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
- 释放 Segment 的锁。
再来看JDK1.8
大致可以分为以下步骤：
- 根据 key 计算出 hash值。
- 判断是否需要进行初始化。
- 定位到 Node，拿到首节点 f，判断首节点 f：
- 如果为 null ，则通过cas的方式尝试添加。
- 如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容。
- 如果都不满足 ，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入。
- 当在链表长度达到8的时候，数组扩容或者将链表转换为红黑树。
18. ConcurrentHashMap 的 get 方法是否要加锁，为什么？
get 方法不需要加锁。因为 Node 的元素 val 和指针 next 是用 volatile 修饰的，在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。
这也是它比其他并发集合比如 Hashtable、用 Collections.synchronizedMap()包装的 HashMap 安全效率高的原因之一。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
//可以看到这些都用了volatile修饰
volatile V val;
volatile Node<K,V> next;
}
19. get方法不需要加锁与volatile修饰的哈希桶有关吗？
没有关系。哈希桶table用volatile修饰主要是保证在数组扩容的时候保证可见性。
static final class Segment<K,V> extends ReentrantLock implements Serializable {
// 存放数据的桶
transient volatile HashEntry<K,V>[] table;
20. ConcurrentHashMap 不支持 key 或者 value 为 null 的原因？
我们先来说value 为什么不能为 null ，因为ConcurrentHashMap 是用于多线程的 ，如果map.get(key)得到了 null ，无法判断，是映射的value是 null ，还是没有找到对应的key而为 null ，这就有了二义性。
而用于单线程状态的HashMap却可以用containsKey(key) 去判断到底是否包含了这个 null 。
我们用反证法来推理：
假设ConcurrentHashMap 允许存放值为 null 的value，这时有A、B两个线程，线程A调用ConcurrentHashMap .get(key)方法，返回为 null ，我们不知道这个 null 是没有映射的 null ，还是存的值就是 null 。
假设此时，返回为 null 的真实情况是没有找到对应的key。那么，我们可以用ConcurrentHashMap .containsKey(key)来验证我们的假设是否成立，我们期望的结果是返回false。
但是在我们调用ConcurrentHashMap .get(key)方法之后，containsKey方法之前，线程B执行了ConcurrentHashMap .put(key, null )的操作。那么我们调用containsKey方法返回的就是true了，这就与我们的假设的真实情况不符合了，这就有了二义性。
总结：数据结构和集合这快的面试考点还是很多的，希望大家仔细看看，这只是一部分。我们分三部分来更新。
多谢大家支持！！！
如果没看过前几篇的文章的，可以点击链接去看看，如果方便可以点赞收藏，给我点个关注，创作不易！