面试中集合常问知识点总结

本文正在参与【[ 一起秋招吧 ] 】 征文活动，一起来聊聊校招的那些事吧，牛客周边和百元京东卡等你来领~

大家好，我是小羽，专注于后端开发相关知识的分享。今天将给大家带来的是关于后端面试关于集合的介绍。

面试中集合常问知识点总结

1）集合类：List 和 Set 比较，各自的子类比较（ArrayList，Vector，LinkedList；HashSet，TreeSet）；

ArrayList，LinkedList，Vector都属于List

List：元素是有顺序的，元素可以重复因为每个元素有自己的角标（索引）
  |-- ArrayList:底层的数据结构是数组结构，特点是：查询很快，增 删 稍微慢点，线程不同步

  |-- LinkedList：底层使用的是链表数据结构，特点是：增 删很快，查询慢。

  |--Vector:底层是数组数据结构，线程同步，被ArrayList代替了，现在用的只有他的枚举。


Set：元素是无序的，且不可以重复（存入和取出的顺序不一定一致），线程不同步。

  |--HashSet：底层是哈希表数据结构。根据hashCode和equals方法来确定元素的唯一性

  |--TreeSet：可以对Set集合中的元素进行排序（自然循序），底层的数据结构是二叉树，
    也可以自己写个类实现Comparable 或者 Comparator 接口，定义自己的比较器，将其作为参数传递给TreeSet的构造函数。

Map：这个集合是存储键值对的，一对一对往里存，而且要确保键的唯一性（01，张三）这样的形式打印出来就是  01=张三
   |--HashTable：底层是哈希表数据结构，不可以存入null键和null值，该集合线程是同步的，效率比较低。出现于JDK1.0

   |--HashMap：底层是哈希表数据结构，可以存入null键和null值，线程不同步，效率较高，代替了HashTable，出现于JDK 1.2

   |--TreeMap:底层是二叉树数据结构，线程不同步，可以用于个map集合中的键进行排序

2）HashMap 的底层实现，之后会问 ConcurrentHashMap 的底层实现；

在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。
HashMap实际上是一个“链表的数组”的数据结构，每个元素存放链表头结点的数组，即数组和链表的结合体。HashMap底层就是一个数组，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock，在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键值对数据。
一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构， 一个Segment里包含一个HashEntry数组，
每个HashEntry是一个链表结构的元素， 每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁

3）如何实现 HashMap 顺序存储：可以参考 LinkedHashMap 的底层实现；

方法一： 维护一张表，存储数据插入的顺序，可以使用vector。但是如果删除数据呢，首先得在vector里面找到那个数据，再删除，而删除又要移动大量数据。性能效率很低。
使用list，移动问题可以解决，但是查找数据的O(n)时间消耗，如果删除m次，那查找数据的性能就是0（n*m)，那总体性能也是 O(n2)。性能还是没法接受。

方法二：
可以在hashmap里面维护插入顺序的id, 在value建一个字段存储id值，再维护一张表vector，并且id对应vector里面的值。
插入的时候，id＋＝1， hashmap.insert，vector.push_back.
删除的时候，先hashmap.find(key), 得到value, 并从value中得到id,  通过id把对应vector值置为无效。
更新：删除＋插入。
维护工作OK了，输出的时候直接输出vector里面的值就可以了， 无效的就continue。
算法复杂度为O(n)

方法三：
Java里面有个容器LinkedHashMap, 它能实现按照插入的顺序输出结果。
它的原理也是维护一张表，但它是链表，并且hashmap中维护指向链表的指针，这样可以快速定位链表中的元素进行删除。
它的时间复杂度也是O(n), 空间上要比上面少些

4）HashTable 和 ConcurrentHashMap 的区别；

HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。
因为当一个线程访问HashTable的同步方法时，其他线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。
如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈效率越低
ConcurrentHashMap使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问