1.ArrayList/LinkedList/Vector的异同？

  • ArrayList和LinkedList的异同

    • 二者都是线程不安全的，Vector相对安全，执行效率高。
    • ArrayList是基于动态数组的，LinkedList是基于链表数据结构。
    • 对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
    • 对于插入和删除操作，LinkedList比较占优势，因为ArrayList要移动数据。
    • ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

  • ArrayList和Vector的区别

    • Vector和ArrayList几乎是完全相同，唯一的区别是Vector是同步类，是线程安全的，因此开销大，访问慢，效率低。
    • Vector每次扩容时扩容现有大小的2倍空间。
    • ArrayList每次扩容1.5倍空间。

2.HashMap的底层实现原理？

  • JDK7 底层实现是数组 + 链表，

  • JDK8 改为数组 + 链表+红黑树，节点类型从Entry 变更为 Node。

  • 主要成员变量包括存储数据的 table 数组、元素数量 size、加载因子 loadFactor。

  • table 数组记录 HashMap 的数据，每个下标对应一条链表，所有哈希冲突的数据都会被存放到同一条链表。

  • Node/Entry 节点包含四个成员变量：key、value、next 指针和 hash 值。

  • HashMap 中数据以键值对的形式存在，键对应的 hash 值用来计算数组下标，如果两个元素 key 的 hash 值一样，就会发生哈希冲突，被放到同一个链表上，当底层数组的某一个索引位置上的元素以链表形式存在的数据个数大于8 ，且当前数组的长度大于64时，此时这个索引位置上的数据改为使用红黑树存储。为使查询效率尽可能高，键的 hash 值要尽可能分散。

  • 当添加数据超出临界值(且数据要存放的位置非空)时，需要对数组扩容。默认的扩容方式：扩容为原来容量的2倍，并将原来的数据复制过来。

3.负载因子值的大小对HashMap有什么影响？

  • 负载因子也叫扩容因子或加载因子，用来判断什么时候进行扩容的，假如加载因子是 0.5，HashMap 的初始化容量是 16，那么当 HashMap 中有 16*0.5=8 个元素时，HashMap 就会进行扩容。

  • 负载因子的大小决定了HashMap的数据密度。

  • 负载因子越大数据密度越大，发生碰撞的几率越高，数组中的链表越容易长，造成查询或者插入的次数会增多，性能会下降。

  • 负载因子越小数据密度越小，发生碰撞的几率越低，数组中的链表也就越短，造成查询或者插入的次数也就越少，性能会更高。数据密度小就会容易触发扩容，会浪费一定的内存空间，并且经常扩容也会影响性能。

4.HashMap和Hashtable的区别 ？

  • 相同点：

    • 两者都实现了Map接口

  • 不同点：

    • 同步性：
      • Hashtable的方法是Synchronized，线程安全；
      • HashMap的方法没有加synchronized的，是线程不安全的
      • 所以只有一个线程的时候使用HashMap效率要高
    • 值：
      • HashMap对象的key、value均可以为null
      • HashTable对象的key、value均不可以为null
    • 容量：
      • HashMap的初始容量为16
      • HashTable的初始容量为11
      • 两者的填充因子默认都是0.75
    • 扩容：
      • HashMap扩容时是当前容量翻倍
      • HashTable扩容时是当前容量翻倍加一

5.HashSet 和 HashMap 区别？

  1. HashSet底层就是基于HashMap实现的，只不过HashSet里面的所有的value都是同一个Object而已，所以HashSet也是非线程安全的。
  2. HashMap使用键来计算Hashcode，HashSet使用成员对象来计算hashcode的值，对于两个对象来说，hashcode可能相同，所以使用equals方法来判断对象的相等性。

6.HashSet如何检查重复？

  • 当把对象加入HashSet的时候，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会把该对象的hashCode值和其他已经在集合中的对象的hashCode值进行比较，如果没有相符的hashCode，HashSet会默认对象没有重复出现。
  • 但是如果发现有相同hashCode值的对象，这时会调用equals方法来检查hashCode相等的对象是否真的相同。
  • 如果两者相同，HashSet就不会让该对象加入成功的。

7.ConcurrentHashMap和Hashtable的区别

两者的主要区别是在实现线程安全的方式上不同。

  • 底层数据结构：

    • JDK1.7的ConcurrentHashMap底层采用的是分段的数组+链表实现的
    • JDK1.8采用的数据结构是数组+链表/红黑树。
    • 数组是HashMap的主体，链表主要是为了解决哈希冲突而存在的。

  • 实现线程安全的方式（重要）

    • 在JDK1.7的时候，ConcurrentHashMap对整个数组进行了分割分段，分成了若干Segment，每一把锁只锁段中的内容，多线程访问容器里的数据段的数据，就不会存在锁竞争，提高了并发访问率。
    • JDK1.8的时候摒弃了Segment的概念，而是直接采用Node数组+ 链表+红黑树的数据结构来实现，并发控制使用synchronized和CAS来操作。
    • 而HashTable中只有一把锁，使用synchronized来保证线程安全，效率非常低下。