集合_牛客博客

1、List,Set,Map三者的区别

1、List（对付顺序的好帮手）：List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象

2、Set（注重独一无二的性质）：不允许重复的集合。不会有多个元素引用相同的对象

3、Map（用Key来搜索的专家）：使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，单页可以是任何对象

hashmap 是线程不安全的，put 时在多线程情况下，会形成环从而导致死循环。

CoucurrentHashMap 是线程安全的，采用分段锁机制，减少锁的粒度。

ArrayList 采用数组实现的，查找效率比LinkedList 高

LinkedList 采用双向链表实现的，插入和删除的效率比ArrayList 要高

一直在list 的尾部添加元素，LinkedList 效率要高。

1、是否保证线程安全：ArrayList和LinkedList都是不同步的，也就是不保证线程安全

2、底层数据结构：ArrayList底层使用的是object数组；LinkedList底层使用的是双向链表数据结构

3、插入和删除是否受元素位置影响：

ArrayList采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响
LinkedList采用链表存储，所以对于add(E e)方法的插入、删除元素，时间复杂度不受元素位置的影响，近似O（1）。如果要在指定位置i插入和删除元素的话（add(int index, E element)）时间复杂度近似为O（n），因为需要先移动到指定位置再插入

4、是否支持快速随机访问：LinkedList不支持高效的随机元素访问，而ArrayList支持

5、内存空间占用：ArrayList的空间浪费主要体现在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费体现在它的每一个元素都需要消耗比ArrayList更多的空间，因为要存放直接后继和直接前驱以及数据

ArrayList并发add()可能出现数组下标越界异常

集合类接口指定了一组叫做元素的对象。集合类接口的每一种具体的实现类都可以选择以它自己的方式对元素进行保存和排序。有的集合类允许重复的键，有些不允许。Java 集合类提供了一套设计良好的支持对一组对象进行操作的接口和类。Java 集合类里面最基本的接口有：

Collection：代表一组对象，每一个对象都是它的子元素。

Set：不包含重复元素的Collection。

List：有顺序的collection，并且可以包含重复元素。

Map：可以把键(key)映射到值(value)的对象，键不能重复。

Iterator 提供了统一遍历操作集合元素的统一接口, Collection 接口实现Iterable 接口,每个集合都通过实现Iterable 接口中iterator()方法返回Iterator 接口的实例, 然后对集合的元素进行迭代操作.

有一点需要注意的是：在迭代元素的时候不能通过集合的方法删除元素, 否则会抛出ConcurrentModificationException异常. 但是可以通过Iterator 接口中的remove()方法进行删除.

1、Iterator 可用来遍历Set 和List 集合，但是ListIterator 只能用来遍历List。

2、Iterator 对集合只能是前向遍历，ListIterator 既可以前向也可以后向。

3、ListIterator 实现了Iterator 接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引，等等。

HashMap 和Hashtable 都实现了Map 接口，因此很多特性非常相似。但是，他们有以下不同点：

1、HashMap 允许键和值是null，而Hashtable 不允许键或者值是null。

2、Hashtable 是同步的，而HashMap 不是。因此，HashMap 更适合于单线程环境，而Hashtable 适合于多线程环境。

3、HashMap 提供了可供应用迭代的键的集合，因此，HashMap 是快速失败的。另一方面，Hashtable提供了对键的列举(Enumeration)。一般认为Hashtable 是一个遗留的类。

1、ArrayList 和Vector 都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。

2、Vector由于使用了synchronized 方法（线程安全），通常性能上较ArrayList 差，而LinkedList 使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。

3、ArrayList 和LinkedListed 都是非线程安全的，如果遇到多个线程操作同一个容器的场景，则可以通过工具类Collections 中synchronizedList 方法将其转换成线程安全的容器后再使用

最常用的集合类是List 和Map

List 的具体实现包括ArrayList 和Vector，它们是可变大小的列表，比较适合构建、存储和操作任何类型对象的元素列表。
List 适用于按数值索引访问元素的情形

Map 提供了一个更通用的元素存储方法。Map 集合类用于存储元素对（称作"键"和"值"），其中每个键映射到一个值。