集合层次结构

Java中集合主要分为两种：Collection和Map。Collection是List和Set接口的父接口；ArrayList和LinkedList是List的实现类；HashSet和TreeSet是Set的实现类；LinkedHashSet是HashSet的子类。HashMap和TreeMap是Map的实现类；LinkedHashMap是HashMap的子类。
collection.png

List，Set，Map各有什么特点

答:List 接口存储一组不唯一，有序（插入顺序）的对象。
Set 接口存储一组唯一，无序的对象。
Map接口存储一组键值对象，提供key到value的映射。key无序，唯一。value不要求有序，允许重复。（如果只使用key存储，而不使用value，那就是Set）。

Arraylist与 LinkedList 异同

  1. Arraylist 底层使用的是Object数组；LinkedList 底层使用的是双向循环链表数据结构；
  2. ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。插入末尾还好，如果是中间，则（add(int index, E element)）接近O（n）；LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
  3. LinkedList 不支持高效的随机元素访问，而ArrayList 实现了RandmoAccess 接口，所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。所以ArrayList随机访问快，插入慢；LinkedList随机访问慢，插入快。
  4. ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

    hashMap线程不安全

    1、哪些不安全：
    在插入元素的时候，多线程环境会发生覆盖现象，例如多线程插入10000个数据，最后出来的数据应该是少于10000个的，因为当线程A和线程B的运算的值的hash值一致时候，在当线程A找好位置准备插入的时候，线程B也找到了和A一样的位置，那么就会发生后插入的值覆盖了前插入的值。

JDK 1.7 链表扩容会形成环形链表的情况，因为当hashmap中存放的数据超过容量（默认16）*加载因子（默认0.75）的时候，就会发生扩容现象，数组长度会扩大一倍，扩容会调用resize()方法和rehash()方法，在多线程情况下调用resize方法后，将数组扩容，然后rehash方法将原有的entry重新计算hash值，再插入到新数组中，在这个插入新数组中的过程中，两个线程同时操作，就会使链表形成一个环，然后，如果get()操作，刚好到了此链表上，就会发生死循环。

2、如何保证安全
可以采用concurrent包下的map
ConcurrentHashMap<Integer, Integer> m = new ConcurrentHashMap<>();

集合类封装
Map<Integer, Integer> m = Collections.synchronizedMap(new HashMap<>());

Map的实现类

Map的实现类有HashMap,LinkedHashMap,TreeMap

  • HashMap是有无序的，LinkedHashMap和TreeMap都是有序的（LinkedHashMap记录了添加数据的顺序；TreeMap默认是自然升序）
  • LinkedHashMap底层存储结构是哈希表+链表，链表记录了添加数据的顺序
  • TreeMap底层存储结构是二叉树，二叉树的中序遍历保证了数据的有序性
  • LinkedHashMap有序性能比较高，因为底层数据存储结构采用的哈希表

    HashSet与HashMap的区别

    1、HashSet底层是采用HashMap实现的。HashSet 的实现比较简单，HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的，因此 HashSet 和 HashMap 两个集合在实现本质上是相同的。
    2、HashMap的key就是放进HashSet中对象，value是Object类型的。
    3、当调用HashSet的add方法时，实际上是向HashMap中增加了一行(key-value对)，该行的key就是向HashSet增加的那个对象，该行的value就是一个Object类型的常量

    HashMap和Hashtable的区别

    相同点： 都是实现来Map接口（hashTable还实现了Dictionary 抽象类）。
    不同点：
  1. 历史原因:Hashtable 是基于陈旧的 Dictionary 类的，HashMap 是 Java 1.2 引进的 Map 接口 的一个实现，HashMap把Hashtable 的contains方法去掉了，改成containsvalue 和containsKey。因为contains方法容易让人引起误解。
  2. 同步性:Hashtable 的方法是 Synchronized 的，线程安全；而 HashMap 是线程不安全的，不是同步的。所以只有一个线程的时候使用hashMap效率要高。
  3. 值：HashMap对象的key、value值均可为null。HahTable对象的key、value值均不可为null。
  4. 容量：HashMap的初始容量为16，Hashtable初始容量为11，两者的填充因子默认都是0.75。
  5. HashMap扩容时是当前容量翻倍即:capacity 2，Hashtable扩容时是容量翻倍+1 即:capacity 2+1。

    ConcurrentHashMap和Hashtable的区别

    JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类 似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
    ① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；
    ② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。