1、集合框架 image.png

2、HashMap的数据结构 image.png

2.1 put过程

public V put(K key, V value) {
    // 当插入第一个元素的时候，需要先初始化数组大小
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 如果 key 为 null，感兴趣的可以往里看，最终会将这个 entry 放到 table[0] 中
    if (key == null)
        return putForNullKey(value);
    // 1. 求 key 的 hash 值
    int hash = hash(key);
    // 2. 找到对应的数组下标
    int i = indexFor(hash, table.length);
    // 3. 遍历一下对应下标处的链表，看是否有重复的 key 已经存在，
    //    如果有，直接覆盖，put 方法返回旧值就结束了
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
 
    modCount++;
    // 4. 不存在重复的 key，将此 entry 添加到链表中，细节后面说
    addEntry(hash, key, value, i);
    return null;
}

步骤：
（1）判断当前桶是否为空，空的就需要初始化（resize 中会判断是否进行初始化）。
（2）根据 hash(key.hashcode)%len 定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。
（3）如果当前桶有值（ Hash 冲突），那么就要比较当前桶中的 key与写入的 key 是否相等（equals方法），相等就赋值给 e,在第 8 步的时候会统一进行赋值及返回。
（4）如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
（5）如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面（形成链表）。
（6）接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。
（7）如果在遍历过程中找到 key 相同时直接退出遍历。
（8）如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。
（9）最后判断是否需要进行扩容。

2.2 HashMap何时扩容

• 存放新值的时候当前已有元素的个数必须大于等于阈值，LoadFactor的默认值为0.75，数组大小为16那么当HashMap中元素个数超过16*0.75即12的时候就把数组扩容。
• 存放新值的时候当前存放数据发生hash碰撞（当前key计算的hash值换算出来的数组下标位置已经存在值）

2.3 HashMap为啥初始化容量为2的次幂

static final int hash(Object key) {
  if (key == null){
    return 0;
  }
  int h;
  h = key.hashCode()；返回散列值也就是hashcode
  return (n-1)&(h ^ (h >>> 16));
}

image.png

高16 bit 不变，低16 bit 和高16 bit 做了一个异或（得到的 hashcode 转化为32位二进制，前16位和后16位低16 bit和高16 bit做了一个异或）(n·1) & hash = -> 得到下标
H为插入元素的hashcode,length为map的容量大小。如果length为2的次幂，则length-1转化为二进制为11111…的形式，在与h的二进制与操作效率会非常快，而且不浪费空间；如果length不是2的次幂比如length为15，则length-1为14，对应的二进制为1110在与h与操作最后一位都为0，而0001,0011这样的位置都永远不会存放元素了，造成空间的浪费，更糟的是数组使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率。

2.4 HashMap在高并发下如果没有处理线程安全会有怎样的安全隐患？

• 扩容后可能会形成循环链表导致get无限循环，具体表现为CPU使用率100%
  原因：在向HashMap put元素时，会检查HashMap的容量是否足够，如果不足，则会新建一个比原来容量大两倍的Hash表，然后把数组从老的Hash表中迁移到新的Hash表中，迁移的过程就是一个rehash()的过程，在调整大小的过程中，存储在链表中的元素的次序会反过来。因为移动到新的 bucket 位置的时候，HashMap 并不会将元素放在链表的尾部，而是放在头部。这是为了避免尾部遍历（tail traversing）。多个线程同时操作就有可能会形成循环链表（jdk8已修复），所以在使用get()时，就会出现Infinite Loop的情况；
• 多线程put时可能导致元素丢失
  原因：当多个线程同时执行addEntry(hash,key ,value,i)时，如果产生哈希碰撞，导致两个线程得到同样的bucketIndex去存储，就可能会发生元素覆盖丢失的情况

2.5 image.png

JDK8中，当同一个hash值的节点数不小于8时，将不再以单链表的形式存储了，会被调整成一颗红黑树（上图中null节点没画）。

3、ConcurrentHashmap image.png

ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承重入锁 ReentrantLock来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。 ConcurrentHashMap 有 16 个 Segments，所以理论上，这个时候，最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。 这里根据 initialCapacity 计算 Segment 数组中每个位置可以分到的大小,如 initialCapacity 为 64，那么每个 Segment 或称之为"槽"可以分到 4 个.

• ConcurrentHashMap 支持 CurrencyLevel（Segment 数组数量）的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment
• 核心数据如 value，以及链表都是 volatile 修饰的，保证了获取时的可见性
• 虽然 HashEntry 中的 value 是用 volatile 关键词修饰的，但是并不能保证并发的原子性，所以 put 操作时仍然需要加锁处理
• 首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。尝试自旋获取锁如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。最后解除当前 Segment 的锁
• CocurrentHashMap（JDK 1.8）抛弃了原有的 Segment 分段锁，采用了CAS + synchronized 来保证并发安全性。其中的 val next 都用了 volatile 修饰，保证了可见性。最大特点是引入了 CAS

4、Map遍历

for (Map.Entry<String, Object> m : map.entrySet()) {}

Iterator<Entry<String, Object>> it = map.entrySet().iterator();
while(it.hasNext()){
    Entry<String, Object> entry = it.next();
}

for (String key : map.keySet()) {
  map.get(key); 
}

5、有什么方法可以减少哈希冲突

• 扰动函数可以减少碰撞
  原理是如果两个不相等的对象返回不同的 hashcode 的话，那么碰撞的几率就会小些。这就意味着存链表结构减小，这样取值的话就不会频繁调用 equal 方法，从而提高 HashMap 的性能（扰动即 Hash 方法内部的算法实现，目的是让不同对象返回不同hashcode）。

• 开放定址法
  当冲突发生时，使用某种探查技术在散列表中形成一个探查（测）序列。沿此序列逐个单元地查找，直到找到给定的地址。按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
  下面给一个线性探查法的例子：
  问题：已知一组关键字为 (26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。
  解答：为了减少冲突，通常令装填因子 α 由除余法因子是13的散列函数计算出的上述关键字序列的散列地址为 (0，10，2，12，5，2，3，12，6，12)。
  前5个关键字插入时，其相应的地址均为开放地址，故将它们直接插入 T[0]、T[10)、T[2]、T[12] 和 T[5] 中。
  当插入第6个关键字15时，其散列地址2（即 h(15)=15％13=2）已被关键字 41（15和41互为同义词）占用。故探查 h1=(2+1)％13=3，此地址开放，所以将 15 放入 T[3] 中。
  当插入第7个关键字68时，其散列地址3已被非同义词15先占用，故将其插入到T[4]中。
  当插入第8个关键字12时，散列地址12已被同义词38占用，故探查 hl=(12+1)％13=0，而 T[0] 亦被26占用，再探查 h2=(12+2)％13=1，此地址开放，可将12插入其中。
  类似地，第9个关键字06直接插入 T[6] 中；而最后一个关键字51插人时，因探查的地址 12，0，1，…，6 均非空，故51插入 T[7] 中。

• 使用不可变的、声明 final 的对象作key值，并且采用合适的 equals() 和 hashCode() 方法，将会减少碰撞的发生
  不可变性使得能够缓存不同键的 hashcode，这将提高整个获取对象的速度，使用 String、Integer 这样的 wrapper 类作为键是非常好的选择。
  为什么 String、Integer 这样的 wrapper 类适合作为键？
  因为 String 是 final，而且已经重写了 equals() 和 hashCode() 方法了。不可变性是必要的，因为为了要计算 hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的 hashcode 的话，那么就不能从 HashMap 中找到你想要的对象。

6、拉链法导致的链表过深，为什么不用二叉查找树代替而选择红黑树？为什么不一直使用红黑树？

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

7、Stream API

Java 8 中的 Stream 是对集合（Collection）对象功能的增强，它专注于对集合对象进行各种非常便利、高效的聚合操作（aggregate operation），或者大批量数据操作 (bulk data operation)。Stream API 借助于同样新出现的 Lambda 表达式，极大的提高编程效率和程序可读性。同时它提供串行和并行两种模式进行汇聚操作，并发模式能够充分利用多核处理器的优势，使用 fork/join 并行方式来拆分任务和加速处理过程。通常编写并行代码很难而且容易出错, 但使用 Stream API 无需编写一行多线程的代码，就可以很方便地写出高性能的并发程序。
当我们使用一个流的时候，通常包括三个基本步骤：
获取一个数据源（source）→ 数据转换→执行操作获取想要的结果，每次转换原有 Stream 对象不改变，返回一个新的 Stream 对象（可以有多次转换），这就允许对其操作可以像链条一样排列，变成一个管道。
流的操作类型：

• Intermediate：一个流可以后面跟随零个或多个 intermediate 操作。其目的主要是打开流，做出某种程度的数据映射/过滤，然后返回一个新的流，交给下一个操作使用。这类操作都是惰性化的（lazy），就是说，仅仅调用到这类方法，并没有真正开始流的遍历。常见操作：map (mapToInt, flatMap 等)、 filter、 distinct、 sorted、 peek、 limit、 skip、 parallel、 sequential、 unordered。
• Terminal：一个流只能有一个 terminal 操作，当这个操作执行后，流就被使用“光”了，无法再被操作。所以这必定是流的最后一个操作。Terminal 操作的执行，才会真正开始流的遍历，并且会生成一个结果，或者一个 side effect。常见操作：forEach、 forEachOrdered、 toArray、 reduce、 collect、 min、 max、 count、 anyMatch、 allMatch、 noneMatch、 findFirst、 findAny、 iterator。
• short-circuiting：对于一个 intermediate 操作，如果它接受的是一个无限大（infinite/unbounded）的 Stream，但返回一个有限的新 Stream。对于一个 terminal 操作，如果它接受的是一个无限大的 Stream，但能在有限的时间计算出结果。常见操作：anyMatch、 allMatch、 noneMatch、 findFirst、 findAny、 limit。