Java 的集合体系

 Java集合可分为两大体系：Collection 和 Map

1.常见的Java集合如下：

Collection接口：单列数据，定义了存取一组对象的方法的集合

• List：元素有序(指的是存取时，与存放顺序保持一致)、可重复的集合
• Set：元素无序、不可重复的集合

Map接口：双列数据，保存具有映射关系“key-value对”的集合，根据元素的key访问value

2.集合中线程安全的集合和线程不安全的集合

线程安全的：

• Hashtable：比HashMap多了个线程安全。
• ConcurrentHashMap:是一种高效但是线程安全的集合。
• Vector：比Arraylist多了个同步化机制。
• Stack：栈，也是线程安全的，继承于Vector。

线性不安全的：

• HashMap – 数组 + 链表 + 红黑树
• Arraylist – 数组
• LinkedList – 双向循环链表
• HashSet – HashjMap
• TreeSet – 二叉树
• TreeMap – 红黑树

3. Arraylist与 LinkedList 异同点？

• 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
• 底层数据结构： Arraylist 底层使用的是Object数组；LinkedList 底层使用的是双向循环链表数据结构；
• 插入和删除是否受元素位置的影响： ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
• 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而ArrayList 实现了RandmoAccess 接口，所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
• 内存空间占用： ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

4. ArrayList 与 Vector 区别？

• Vector是线程安全的，ArrayList不是线程安全的。其中，Vector在关键性的方法前面都加了synchronized关键字，来保证线程的安全性。如果有多个线程会访问到集合，那最好是使用 Vector，因为不需要我们自己再去考虑和编写线程安全的代码。
• ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍，这样ArrayList就有利于节约内存空间。

5. Collection子接口：Set 接口

• Set接口描述

• Set接口是Collection的子接口，set接口没有提供额外的方法。
• Set 集合存取元素同样是无序的。
• Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个Set 集合中，则添加操作失败。
• Set 判断两个对象是否相同不是使用 == 运算符，而是根据 equals() 方法。
• Set 实现类之一：HashSet
  • HashSet 是 Set 接口的典型实现，大多数时候使用 Set 集合时都使用这个实现类。HashSet的底层其实就是HashMap，只不过我们HashSet是实现了Set接口并且把数据作为K值，而V值一直使用一个相同的虚值来保存。
  • HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。
  • HashSet 具有以下特点：不能保证元素的排列顺序、HashSet 不是线程安全的、集合元素可以是 null
  • HashSet 集合判断两个元素相等的标准：两个对象通过 hashCode() 方法比较相等，并且两个对象的 equals() 方法返回值也相等。
  • 对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode(Object obj)方法，以实现对象相等规则。即：“相等的对象必须具有相等的散列码”。

• Set实现类之二：LinkedHashSet
• LinkedHashSet 是 HashSet 的子类
• LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。
• LinkedHashSet插入性能略低于 HashSet，但在迭代访问 Set 里的全部元素时有很好的性能。
• LinkedHashSet 不允许集合元素重复。
• Set实现类之三：TreeSet

• TreeSet 是 SortedSet 接口的实现类，TreeSet 可以确保集合元素处于排序状态。

• TreeSet底层使用红黑树结构存储数据
• TreeSet 两种排序方法：自然排序和定制排序。默认情况下，TreeSet 采用自然排序。

6. Map接口

• Map接口概述
  • Map与Collection并列存在。用于保存具有映射关系的数据:key-value
  • Map 中的 key 和 value 都可以是任何引用类型的数据
  • Map 中的 key 用Set方法来存放，不允许重复，即同一个 Map 对象所对应的类，须重写 hashCode()和equals() 方法
  • 常用String类作为Map的“键”
  • key值唯一，但可以为null
  • key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value
  • Map接口的常用实现类：HashMap、TreeMap、LinkedHashMap和Properties。其中，HashMap是 Map 接口使用频率最高的实现类

 7. Map实现类之一：HashMap

• HashMap是 Map 接口使用频率最高的实现类。
• 允许使用null键和null值，与HashSet一样，不保证映射的顺序。
• 所有的key构成的集合是Set:无序的、不可重复的。所以，key所在的类要重写：equals()和hashCode()
• 所有的value构成的集合是Collection:无序的、可以重复的。所以，value所在的类要重写：equals()
• 一个key-value构成一个entry
• 所有的entry构成的集合是无序的、不可重复的
• HashMap 判断两个 key 相等的标准是：两个 key 通过 equals() 方法返回 true，hashCode 值也相等。
• HashMap 判断两个 value相等的标准是：两个 value 通过 equals() 方法返回 true。
• 扩容负载因子是0.75，扩容倍数：2

8. HashMap 的 底层数据结构是什么？

在JDK1.7 和JDK1.8 中有所差别：

在JDK1.7 中，由“数组+链表”组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。

在JDK1.8 中，由“数组+链表+红黑树”组成。当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O(logn)，而链表是糟糕的 O(n)。因此，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：

• 当链表超过 8 且数据总量超过 64 才会转红黑树。

• 将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。

9. 解决hash冲突的办法有哪些？HashMap用的哪种？

解决Hash冲突方法有:开放定址法、再哈希法、链地址法（拉链法）、建立公共溢出区。HashMap中采用的是 链地址法 。

• 开放定址法也称为再散列法，基本思想就是，如果p=H(key)出现冲突时，则以p为基础，再次hash，p1=H(p),如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址pi。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除的节点上做标记，而不能真正删除节点。
• 再哈希法(双重散列，多重散列)，提供多个不同的hash函数，当R1=H1(key1)发生冲突时，再计算R2=H2(key1)，直到没有冲突为止。 这样做虽然不易产生堆集，但增加了计算的时间。
• 链地址法(拉链法)，将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
• 建立公共溢出区，将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

Collections工具类

• Collections 是一个操作 Set、List 和 Map 等集合的工具类

• Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，
  还提供了对集合对象设置不可变、对集合对象实现同步控制等方法
• 排序操作：（均为static方法）
  • reverse(List)：反转 List 中元素的顺序
  • shuffle(List)：对 List 集合元素进行随机排序
  • sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
  • sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
  • swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换

• Collections常用方法（查找、替换）

  • Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
  • Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
  • Object min(Collection)
  • Object min(Collection，Comparator)
  • int frequency(Collection，Object)：返回指定集合中指定元素的出现次数
  • void copy(List dest,List src)：将src中的内容复制到dest中 boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换List 对象的所有旧值