Set

set集合作用：去重，不能存放重复的元素

TreeSet

底层用红黑树实现
支持有序性操作，可以把存入其中的元素自然排序（从小到大或从大到小），要求元素必须具备可比较性
如果元素本身可比较，则需要实现Comparable接口，重写compareTo()方法
如果元素本身无法比较，则需要实现Comparator接口，重写compare()方法，重新定义比较规则
查找效率不如HashSet，时间复杂度为O(logn)

HashSet

底层用哈希表实现、
不支持有序性操作，但是查找效率极高，时间复杂度可以控制在O(1)，但插入顺序不能确定

LinkedHashSet

底层用哈希表和双向链表实现
具有HashSet的查找效率，且用双向链表维护了元素的插入顺序

Map

Map是映射，存储的是<K,V>键值对

TreeMap

TreeMap的Key集合就是TreeSet，基于红黑树实现

HashMap

HashMap的Key集合就是HashSet，基于哈希表实现

HashTable

和HashMap类似，但它是线程安全的。HashTable可以使得多个线程同时操作哈希表，并且不会导致数据不一致
但这是一个遗留类，我们不应该去使用它。
现在可以使用ConcurrentHashMap来支持线程安全，因为引入了分段锁，所以效率会更高

LinkedHashMap

在HashMap的内部使用了双向链表，可以维护元素的插入顺序

简述集合主要有哪些类和接口，各自的特点

集合的接口有Collection和Map，其中Collection包括List，Set，Queue

List是有序的，主要包括：ArrayList，LinkedList，Vector
ArrayList底层用数组实现，线程不安全，Vector是线程安全的ArrayList，但效率较低
LinkedList底层用双向链表实现，与ArrayList相比增删快查询慢

Set是无重复元素集合，主要包括：TreeSet，HashSet，LinkedHashSet
HashSet底层就是HashMap，利用key来保证元素的唯一性，LinkedHashSet可以按key的操作顺序排序
TreeSet可按默认规则排序或自定义规则排序

Queue是队列结构，主要有：PriorityQueue优先级队列，ArrayBlockingQueue，LinkedBlockingQueue等

Map以key-value键值对的形式存储元素，主要包括HashMap，LinkedHashMap，TreeMap
HashMap底层用数组+链表/红黑树实现，LinkedHashMap可以按照对key的操作顺序对集合排序
TreeMap可以按照默认排序规则或指定比较规则对集合排序

List，Set，Map有什么区别

List是有序，可重复，有索引的集合，继承了Collection接口的所有功能，可以用索引遍历
Set是无序，不可重复的集合，Set的实现类LinkedHashSet，TreeSet是有序的，LinkedHashSet可以按照元素插入顺序排序
也可以按元素操作的时间顺序排序，TreeSet可以按默认规则或自定义规则排序
Map是无序，以key-value的键值对形式存储数据的集合，键不可重复，值没有要求，重复的键对应的值会覆盖之前的值

HashSet去重原理

1.对基本类型的包装类，可以直接按值进行比较
2.对于引用类型，会先比较hashCode()是否相同，不同表示不是同一个对象，如果相同则用equals()判断是否同一个对象
3.如果只希望内容相同的对象就表示对象相同，除了重写equals()方法，也要重写hashCode()方法
因为内容相同的对象会因为内存地址的不同而获取的哈希码值不同

HashMap和HashSet是怎么实现的

JDK1.8之前，HashMap的底层是用数组加链表实现的，数组中的每个元素都是一条单链表，链表中的每个元素都是Entry实
现类Node的一个实例，包括key，value，hash，next四个属性。
HashMap在查找数据时，可以通过hash值快速定位到数组下标，然后对链表进行遍历查找，复杂度O(n)
JDK1.8进行了优化，当链表元素超过8个时，将链表转换为红黑树来提高查询效率，时间复杂度为O(logn)

HashSet底层是基于HashMap实现的，HashSet的元素只是存放在底层的HashMap的key上，而value用一个static final的
Object对象，因此HashSet的实现都是底层直接调用HashMap的相关方法实现的

Collection和Collections区别

Collection是一个集合接口，定义了相关集合应该实现的方法，包括List，Set，Queue等
Collections是一个集合工具类，为Collection类型的集合提供很多便捷的方法，例如addAll()可以批量添加元素，
sort()可以对List集合进行排序，shuffle()可以随机打乱List集合中的元素

什么是迭代器

迭代器实现了Iterator接口，是用于遍历Collection集合的第一个指针
主要有三个方法：
1.iterator()：获取集合的迭代器
2.hasNext()：判断集合中是否还有元素，有返回true，反之返回false。初始时迭代器位于第一个元素之前
3.next()：用于获取集合的下一个元素，并将迭代器向后移动一个元素的单位

使用foreach循环遍历集合元素时能否添加或者删除元素

不能。
foreach实际上就是用Iterator迭代器实现的，如果进行添加或删除会抛出ConcurrentModificationException异常。
因为添加或删除元素会改变modCount的值，这个值是成员变量，代表集合的修改次数，当这个值与预期的修改次数不一致
就会抛出异常

Queue接口中的add()/offer()、remove()/poll()、element()/peek()方法有什么区别

add()和offer()都是向队列尾部插入一个元素，区别是超出队列界限时，add()抛出异常，offer()返回false
remove()和poll()都是移除队头元素并返回，队列为空时remove()抛出异常，poll()则是返回null值
element()和peek()都是获取队头元素，队列为空时element()抛出异常，peek()则是返回null值

有哪些线程安全的集合类

1.Vector：是线程安全的ArrayList，底层用数组实现，用synchronized修饰方法保证线程安全
2.HashTable：线程安全的HashMap，继承自Dictionary，通过synchronized修饰方法保证线程安全，性能差
3.ConcurrentHashMap：线程安全的HashMap，通过分段锁实现线程安全，性能较好