Java面试-集合-基础

• ArrayList 扩容：默认长度为 10，每次至少扩容 1.5 倍
• LinkedList 根据 index 查找元素时，会自动判断从左还是从右查找比较快：if (index < (size >> 1)) 即 index 小于长度的一半，从左 else 从右
• LinkedList 添加元素：
  1. a ⇆ b(last)
  2. a ⇆ b(last, l) ← c
  3. a ⇆ b(l) ← c(last)
  4. a ⇆ b(l) ⇆ c(last)
• transient 关键字：属性变量不被序列化
  • ArrayList 里的 elementData 不总是满的，每次都序列化，会浪费时间和空间，并且重写了 writeObject，保证存在的元素都会被序列化
  • LinkedList中将first和last修饰成 transient，是为了避免递归的进行序列化导致栈溢出
• ArrayList在循环过程中删除的问题
  • 增强for循环删除，使用ArrayList的remove()方法删除，产生并发修改异常 ConcurrentModificationException
  • 迭代器，使用ArrayList的remove()方法删除，产生并发修改异常 ConcurrentModificationExceptio
  • 迭代器，使用迭代器的remove()方法删除，是一种安全的删除元素的方式
    • 迭代器的时候，会使用next(), 将指针移向下一个位置，不会发生报错，而调用remove()会删除最后一次调用next()时返回的元素
• HashMap 为什么使用红黑树，而不是其他的树？
  • 二叉排序树在添加元素的时候，极端情况下会出现线性结构
  • 红黑树不追求”完全平衡“。它能保证在最坏的情况下，基本动态集合操作时间为O(logn)，所以不使用平衡二叉树
• HashMap#put(k,v)
  1. Node(k,v)
  2. index = k.hashCode(), 如果没有元素，就把Node添加到这个位置上
  3. 如果有链表，就将k和链表上每个节点的k进行equals：如果都返回 false，则新节点添加到链表的末尾；否则节点的 value 将被覆盖
• HashMap#get(k)
  1. index = k.hashCode()，什么都没有，则返回null
  2. 如果有链表，就将K和链表上每一个节点的K进行equals：如果都返回false，则返回null；否则返回对应的 value
• HashMap 扩容：默认容量为 16，默认加载因子为 0.75，请将初始化容量设为 2 的倍数
  • JDK8之后，如果哈希表单向链表中元素超过8个，那么单向链表这种数据结构会变成红黑树数据结构。当红黑树上的节点数量小于6个，会重新把红黑树变成单向链表数据结构
    • 首先和hashcode碰撞次数的泊松分布有关，主要是为了寻找一种时间和空间的平衡。在负载因子0.75（HashMap默认）的情况下，单个hash槽内元素个数为8的概率小于百万分之一。
    • 红黑树转链表的阈值为6，主要是因为，如果也将该阈值设置于8，那么当hash碰撞在8时，会发生链表和红黑树的不停相互转换，白白浪费资源。
  • HashMap扩容大小为什么是2的幂?
    • 2的幂可以保证数组的长度是一个偶数，这样可以避免一些奇偶性的问题。
    • 2的幂可以让HashMap的散列函数更简单高效，只需要用hash值和数组长度减一做按位与运算，就可以得到元素在数组中的位置。这样可以减少乘法和取模的开销，提高性能。
    • 2的幂可以让HashMap的扩容更方便，只需要将数组长度乘以2，就可以得到新的容量。这样可以保证元素在扩容后的位置要么不变，要么在原来的基础上加上数组的旧长度。这样可以减少元素的重新散列，提高效率。
• Hash 计算
  • 使高16位也参与到hash的运算能减少冲突：(h = key.hashCode()) ^ (h >>> 16)
  • 索引：(n - 1) & hash
    • n永远是2的次幂，所以 n-1 通过 二进制表示，永远都是尾端以连续1的形式表示
    • 当(n - 1) 和 hash 做与运算时，会保留hash中 后 x 位的 1
• HashMap在 jdk1.7 和 jdk1.8 的区别
  • 1.7采用数组+单链表，1.8在单链表超过一定长度后改成红黑树存储
  • 1.7插入元素到单链表中采用头插入法，1.8采用的是尾插入法。
    • 在jdk1.7中采用头插入法，扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题。而在jdk1.8中采用尾插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。
  • 1.7扩容时需要重新计算哈希值和索引位置，消耗性能，而且多线程环境下会造成死锁。1.8并不重新计算哈希值，巧妙地采用hash和扩容后容量减一进行&操作来计算新的索引位置。
    • 索引是 (n - 1) & hash, 当数组长度扩大一倍时，相当于在最高位加了一个0，那么原来的hash值和新的数组长度减一做按位与运算，结果要么和原来一样，要么多了一个旧容量的值。
    • 比如旧容量：n=0100; 新容量：n=1000；则旧(n - 1) = 0011；新(n - 1) = 0111
      • 如果Key的 hash 是 0011, 则0011 & 0011 == 0011 & 0111, 位置不变
      • 如果Key的 hash 是 1111, 则1111 & 0011 != 1111 & 0111
        • 新位置增加了0100,相当于旧数组的长度
• HashMap 多线程问题
  • 程序经常占了100%的CPU。CPU利用率过高，查看堆栈，你会发现程序都Hang在了HashMap.get()这个方法上了 （jdk1.7）
    • 因为多线程情况下，对同一个HashMap做put操作可能导致两个或以上线程同时做rehash动作，就可能导致循环链表出现，一旦出现线程将无法终止，持续占用CPU，导致CPU使用率居高不下
    • Hash表这个容器当有数据要插入时，都会检查容量有没有超过设定的thredhold，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的元素都需要被重算一遍。这叫rehash
  • 多线程put的时候可能导致元素丢失
    • 主要问题出在addEntry方法的new Entry (hash, key, value, e)，如果两个线程都同时取得了e,则他们下一个元素都是e，然后赋值给table元素的时候有一个成功有一个丢失。
  • 解决方案:
    1. Hashtable替换HashMap
    2. Collections.synchronizedMap将HashMap包装起来
    3. ConcurrentHashMap替换HashMap
• ConcurrentHashMap：在默认理想状态下，可以支持 16 个线程执行并发写操作及任意数量线程的读操作
  • 底层数据结构
    • <jdk1.7> ：使用 Segment数组 + HashEntry数组 + 链表
    • <jdk1.8> ：使用 Node数组 + 链表 + 红黑树
  • 效率
    • <jdk1.7>：ConcurrentHashMap 使用的分段锁，如果一个线程占用一段，别的线程可以操作别的部分
    • <jdk1.8>：简化结构，put和get不用二次哈希，一把锁只锁住一个链表或者一棵树，并发效率更加提升
  • 线程安全
    • <JDK1.7>: 分段锁, 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率
    • <jdk1.8>: 使用的是 synchronized 关键字（优化后效率很高）同步代码块和 cas(乐观锁)操作了维护并发
• <jdk1.7> CouncurrentHashMap
  • 底层一个Segments数组，存储一个Segments对象，（其实就相当于一段一段的）一个Segments中储存一个Entry数组，存储的每个Entry对象又是一个链表头结点。
  • 相当于HashMap嵌套HashMap，只不过第一层是加锁的，分段锁思想，所以需要两次Hash计算才能确定位置
  • Segment内部类，继承ReentrantLock
  • get
    1. 第一次哈希找到对应的Segment段，调用Segment中的get方法
    2. 再次哈希找到对应的链表
    3. 最后在链表中查找
  • put
    1. 首先确定段的位置
    2. 调用Segment中的put方法
       1. 加锁 lock();
       2. 检查当前Segment数组中包含的HashEntry节点的个数，如果超过阈值就重新hash(扩容)
          • 只是对 Segments对象中的Hashentry数组进行重哈希
       3. 然后再次hash确定放的链表。
       4. 在对应的链表中查找是否相同节点，如果有直接覆盖，如果没有将其放置链表尾部
• <jdk1.8> CouncurrentHashMap
  • putVal
    1. 如果数组”空”，进行数组初始化
    2. 找该 hash 值对应的数组下标，得到第一个节点 f
       • 如果数组该位置为空，用一次 CAS 操作将新new出来的 Node节点放入数组i下标位置
       • 如果不为空。用 synchronized 修饰
• Collections工具类
  • Collections.synchronizedXxx: 同步集合
  • emptyXxx: 空不可变
  • singletonXxx: 单元素不可变
  • unmodifiableXxx: 不可变
  • addAll: 将所有指定元素添加到指定 collection 中
  • reverse: 反转指定列表List中元素的顺序。
  • shuffle: 集合元素进行随机排序，类似洗牌
  • replaceAll: 使用新值替换 List 对象的所有旧值
• 集合去重：需要重写比较对象的HashCode与equal方法
  • Stream流式去重: distinct
  • HashSet：通过调用元素内部的hashCode和equals方法实现去重
    • 首先调用hashCode方法，比较两个元素的哈希值，如果哈希值不同，直接认为是两个对象，停止比较。
    • 如果哈希值相同，再去调用equals方法，返回true，认为是一个对象。返回false，认为是两个对象。