Java集合

好东西就得大伙一起看
,

关于Java集合的面试题。

List，Set，Map三者的区别？

  • List（顺序）：List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象。
  • Set（独一无二）：不允许重复的集合。不会有多个元素引用相同的对象。
  • Map（键值对）:两个Key可以引用相同的对象，但Key不能重复。

ArrayList和LinkedList的区别？

  • 是否线程安全：ArrayList和LinkedList都是不同步的，也就是不保证线程安全。
  • 底层数据结构：ArrayList底层使用的是Object数组；LinkedList底层使用的是双向链表
  • 插入和删除是否受元素位置的影响：数组插入指定位置（中间）要移位。链表插入到指定位置（中间）要移动指针。
  • 是否支持快速随机访问：链表不支持，数组支持（get(int index)）。
  • 内存空间占用：数组会在列表的末尾预留很多空位（数组一次分配）。双向链表，每个元素要保存直接前驱指针、直接后继指针、还有数据，所以每个元素空间占用比数组要大。
  • ArrayList实现了RandomAccess接口，而LinkedList并没有。并且RandomAccess接口只是标识。
  • 实现了RandomAccess接口的list优先选择for循环，然后是foreach。未实现优先使用iterator遍历（foreach底层就是iterator）。

ArrayList与Vector区别？为什么用ArrayList取代Vector？

Vector类的所有方法都是同步的。两个线程池安全地访问一个Vector对象、但是一个线程访问Vector要在同步操作上花费大量时间。
ArrayList不是同步的，所以在不需要线程安全的情况下，使用ArrayList。

ArrayList的扩容机制？

初始为10，如果超过容量会增加1.5倍，新建的数组会将原来的数组复制过去。

HashMap和Hashtable的区别？

  • 是否线程安全？HashMap是非线程安全的，Hashtable是线程安全的。Hashtable内部的方法基本都经过synchronized修饰。可以用ConcurrentHashMap来保证线程安全。
  • 效率：因为没有线程安全，HashMap比Hashtable效率要高一点。另外Hashtable基本被淘汰了，不要在代码中使用他。
  • 对Null key和Null value的支持：HashMap中，null可以作为键，这样的键只有一个，但是可以有多个键对应的值为null。但是在HashTable中put进的键值只要有一个null，直接抛出NullPointException。
  • 初始容量大小和每次扩充的容量不同：
    • 如果创建时不指定容量初始值，Hashtable默认的初始大小为11，之后每次扩容，容量变为原来的2n+1。HashMap默认的初始化大小为16，之后每次扩容是原来的2倍。
    • 如果创建时指定容量初始值，Hashtable默认的初始大小就是设置的，而HashMap会将其扩充为2的幂次方大小。也就是HashMap总是使用2的幂次方来作为哈希表的大小。
  • 底层数据结构：JDK1.8之后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable没有这样的机制。

红黑树

是一种自平衡二叉查找树。

  • 节点是红色或黑色。
  • 根是黑色。
  • 所有叶子都是黑色（叶子是NIL节点）。
  • 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
  • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

HashMap与HashSet区别？

HashSet底层就是使用HashMap实现的。

HashMap HashSet
实现了Map接口 实现了Set接口
存储键值对 仅存储对象
调用put()向map中添加元素 调用add()方法向set中添加元素
HashMap使用键（Key）计算HashCode HashSet使用成员对象来计算HashCode，对于两个对象来说HashCode可能相同，所以用equals()方法来判断对象的相等性

HashSet如何检查重复？

当你把对象加入HashSet时，HashSet会计算对象的HashCode值来判断对象加入的位置，同时也会与其他加入的对象的HashCode值作比较，如果没有相符的HashCode，HashSet会假设对象没有重复出现。但如果发现有相同的HashCode值的对象，这时会调用equals()来检查HashCode相等的对象是否真的相同。如果两者相同，则不会让加入操作成功。

hashCode()与equals()的相关规定

  • 如果两个对象相等，那么他们的hashCode一定也是相同的
  • 如果两个对象相等，对两个equals方法返回true
  • 两个对象有相同的hashCode值，他们也不一定是相等的
  • 综上，如果equals()被覆盖，那么hashCode()也必须被覆盖
  • hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）

== 与 equals 的区别

  • == 是判断两个变量或实例是不是指向同一个内存空间，equals是判断两个变量或实例所指向的内存空间的值是不是相同的
  • == 是指内存地址进行比较 equals()是对字符串的内容进行比较
  • == 指引用的是否相同 equals指的是值是否相同

HashMap的底层实现

JDK1.8之前

JDK1.8之前HashMap底层是数组和链表结合在一起使用就是链表散列。HashMap通过Key的hasCode经过扰动函数处理过得到hash值，然后通过(n-1)&hash判断当前元素存放的位置（这里的n指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的hash值以及key是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

HashMap的长度为什么是2的幂次方？

为了能让HashMap存取高效，尽量减小碰撞，也就是要尽量把数据分配均匀。但是由于Hash值的范围太大了，内存存不下。所以要将散列值取余，而将散列值对数组长度取余，等价于其除数减一的与（&）操作，相比于取余能提高运算效率。

hash % length == hash & (length - 1)，前提length是2的n次方

HashMap多线程操作导致死循环问题？

主要原因是在于并发情况下的Rehash会造成元素之间形成一个循环链表（jdk1.8已修复）。但是在多线程下，使用HashMap还会导致其他问题比如数据丢失。并发情况下推荐使用ConcurrentHashMap。

ConcurrentHashMap与Hashtable的区别？

主要区别体现在实现线程安全的方法上不同。

  • 底层数据结构：JDK1.7中的ConcurrentHashMap底层采用分段的数组加链表实现，JDK1.8采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable和JDK1.8之前的HashMap的底层数据结构类似，都是采用数组+链表的形式，数组是HashMap的主体，链表则是主要为了解决哈希表冲突而存在；
  • 实现线程安全的方式（重要）：
    • 在JDK1.7的时候，ConcurrentHashMap（分段锁），对整个桶数组进行了分割分段（Segment），每把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会产生锁竞争，提高并发访问率。到了JDK1.8时，已经摒弃了Segment的概念，而是直接使用Node数组+链表+红黑树的数据结构来实现，并发控制使用synchronized和CAS来操作。（JDK1.6以后，对synchronized锁做了很多优化）
    • Hashtable（同一把锁，全表锁）：使用synchronized来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能进入阻塞或轮询状态，如使用put添加元素，另一个线程就不能使用put添加元素，也不能使用get，竞争或越来越激烈，效率越来越低。

ConcurrentHashMap线程安全的具体实现方式和底层实现

  • JDK1.7 首先将数据分为了一段一段的存储，然后给每一段的数据搭配一把锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问。
  • ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。
    Segment实现了ReenrantLock，所以Segment是一种可重入锁，扮演锁的角色。HashEntry用于存储键值对数据。
    static class Segment<K,V> extends ReentrantLock implements Serializable {

}
  • JDK1.8 ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8结构相似，数组+链表/红黑二叉树。Java 8在链表长度超过一定阈值（8）时，将离岸边转换为红黑树。synchronized只锁当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。

comparable和comparator的区别。

  • comparable接口实际上是出自java.lang包，它有一个compareTo(Object obj)方法来排序。
  • comparator接口实际上是出自java.util包，它有一个compare(Object obj1,Object obj2)方法用来排序。
    一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo()方法或compare()方法，当我们需要对某一个集合实现两种排序方式，比如一个song对象中的歌名和歌手分别采用一种排序方法的话，我们就可以重写compareTo()方法和使用自制的comparator方法或者以两个comparator来实现歌名排序和歌手名排序，第二种只能使用两个参数版的Collection.sort();

总结

  • Collection
    • List
      • ArrayList：Object数组
      • Vector：Object数组
      • LinkedList：双向链表
    • Set
      • HashSet（无序，唯一）：基于HashMap实现的，底层采用HashMap来保存元素。
      • LinkedHashSet:LinKedHashSet继承与HashSet，并且内部是通过LinkedHashMap来实现的。
      • TreeSet（有序，唯一）：红黑树（自平衡的排序二叉树）
    • Map
      • HashMap：JDK1.8之前HashMap是由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8之后，在解决哈希冲突时有了较大的变化，当链表长度大于阈值（8）时，会将链表转换成红黑树，以减少搜索时间。
      • LinkedHashMap：LinkHashMap继承自HashMap，所以它的底层仍然是基于拉链式散列结构即数组和链表或红黑树组成。另外，LinkedHashMap在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
      • Hashtable：数组+链表组成，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。
      • TreeMap：红黑树（自平衡的排序二叉树）

来源

Guide哥 | JavaGuide面试突击版