集合 - 简书

一、常用集合的分类

Collection 接口的接口对象的集合（单列集合）
├——-List 接口：元素按进入先后有序保存，可重复
│—————-├ LinkedList 接口实现类，链表，插入删除，没有同步，线程不安全
│—————-├ ArrayList 接口实现类，数组，随机访问，没有同步，线程不安全
│—————-└ Vector 接口实现类数组，同步，线程安全
│ ———————-└ Stack 是Vector类的实现类
└——-Set 接口：仅接收一次，不可重复，并做内部排序
├—————-└HashSet 使用hash表（数组）存储元素
│————————└ LinkedHashSet 链表维护元素的插入次序
└ —————-TreeSet 底层实现为二叉树，元素排好序

Map 接口键值对的集合（双列集合）
├———Hashtable 接口实现类，同步，线程安全
├———HashMap 接口实现类，没有同步，线程不安全-
│—————–├ LinkedHashMap 双向链表和哈希表实现
│—————–└ WeakHashMap
├ ——–TreeMap 红黑树对所有的key进行排序
└———IdentifyHashMap

数据结构：
ArrayXxx:底层数据结构是数组，查询快，增删慢
LinkedXxx:底层数据结构是链表，查询慢，增删快
HashXxx:底层数据结构是哈希表。依赖两个方法：hashCode()和equals()
TreeXxx:底层数据结构是二叉树。两种方式排序：自然排序和比较器排序

二、使用场景

三、Collection 和 Collection 的区别

java.util.Collection 是一个集合接口（集合类的一个顶级接口）

Collections则是集合类的一个工具类/帮助类
它提供了一系列的静态方法实现对各种集合的搜索、排序、线程安全化等操作。

四、集合遍历问题

1. Map（3 种遍历方式）

>>通过keySet 获取key，再通过key来遍历
     for(String k : map.keySet()){
         //通过key 获取value 值  
         String str = map.get(k);
         System.out.print(" "+k);
     }

>>通过value 值来遍历，使用map.values() 方法
     for(String v : map.values()){
         System.out.println("value:"+v);
     }

>>HashMap  底层是通过数组链表来实现的，key-value 作为一个entry 存储
     entrySet() 获取数组中的每个key-value
     Iterator it = map.entrySet().iterator();
     while(it.hasNext()){
         //获取每个entity
         System.out.println(it.next());
     }

2. List（3 种方式）

2.1 普通for 循环
2.2 增强型for 循环
2.3 Iterator

3. Set（2种方式）

Iterator it = set.iteratro();
while(it.hasNext()){
     System.out.println(it.next() +" ");
}

for(Object obj : set){
     System.out.println(obj);
}

补充内容:RandomAccess接口：

public interface RandomAccess {
}
RandomAccess 接口只是一个标识。 标识实现这个接口的类具有随机访问功能。
比如数组天然支持随机访问，时间复杂度为 O（1）。

list 的遍历方式选择：

实现了RandomAccess 接口的list，优先选择普通for 循环，其次是foreach。
未实现RandomAccess 接口的list，优先选择iterator（foreach 遍历底层也是通过iterator 实现的），大size 的数据千万不要使用普通for 循环。

四、HashSet如何检查重复

当把对象加入HashSet 集合，集合会计算对象的hashcode 值来判断对象加入的位置，同时也会也其它对象进行hashcode 值比较，如果没有相同的hashcode 默认为没有重复出现。如发现有相同的hashcode 值出现，这时会调用对象的equals() 方法来检测hashcode 值相同的对象是否真的相同。
hashcode() 与equals() 的相关规定：

hashcode 值相同的两个对象不一定相等；
相等的两个对象hashcode 值一定相等；
两个对象相等，对两个equals 方法返回true.
综合：重写equals() 方法，hashcode() 方法也必须覆盖。

五、HashMap的底层实现

jdk8 以前，HashMap 底层是数组+链表的方式实现。HashMap 通过key 的hashCode 经过扰动函数处理后得到hash值，然后通过( n-1 ) & hash 判断当前元素存放的位置（n 值指的是数组的长度），如果当前位置存在元素，则判断元素的hash 值及key 是否与要存入的元素相同，如果相同则直接覆盖，不同就通过链表解决。

jdk8 之后，在解决hash 冲突时有了较大的变化，当链表的长度大于阈值（默认是8）时，将链表转换成红黑树，以减少搜索时间。

六、ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

HashTable是线程安全的。但是get/put所有相关操作都是synchronized的，相当于将所有的操作串行化。HashTable性能差主要是由于所有操作需要竞争同一把锁。

ConcurrentHashMap采用了非常精妙的"分段锁"策略，ConcurrentHashMap的主干是个Segment数组。Segment里维护了一个HashEntry数组，对于同一个Segment的操作才需考虑线程同步，不同的Segment则无需考虑。
# ConcurrentHashMap实现原理及源码分析

集合