[数据结构与算法]面试题知识点全纪录---容器

注意：该博客仅是本人对掌握知识的测试，具体内容请移步guide哥网站！！！

https://snailclimb.gitee.io/javaguide
链接

**

JAVA集合框架

**

https://www.javatpoint.com/collections-in-java

1.List，Set，Map三者区别？

-List: 存储的元素是有序的、可重复的。

-Set: 存储的元素无序且独一无二。

-Map：使用（key-value）存储，key是无序的、不可重复的，value是无序的，可重复的，每个键值对最多映射一个值。

2.集合框架底层数据结构总结

1. List
   Arraylist：Object[] 数组
   Vector：Object[] 数组
   LinkedList：双向链表

2. Set
   HashSet：基于HashMap实现。
   LinkedHashSet：LinkedHashMap
   TreeSet：红黑树

3. Map
   HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

   LinkedHashMap：继承HashMap，底层是基于拉链式散列结构即由数组和链表或红黑树组成。增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。

   Hashtable：数组+链表组成，数组是Hashtable的主体，链表则是主要为了解决哈希冲突而存在的。

   TreeMap：红黑树（自平衡的排序二叉树）

3.Collection子接口List

ArrayList和Vector的区别？
ArrayList是List的主要实现类，底层使用Object[]存储，适用于频繁的查找工作，线程不安全。
Vector是Lsit的古老实现类，底层使用Object[]存储，线程安全。

ArrayList和LinkedList区别？

1.都不保证线程安全
2.ArrayList底层object[]数组；LinkedList底层双向链表。
3.内存空间占用： ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间
双向链表与双向循环链表


ensureCapacity方法
最好在 add 大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        list = new ArrayList<Object>();
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(N);
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法后："+(endTime1 - startTime1));
    }
}

4.Collection 子接口之 Set

1.comparable 和 Comparator 的区别?
comparable接口实际上出自java.lang包，它有compareTo(Object obj)方法用来排序。
comparator接口出自java.util包,他有compare(Object obj1,Object obj2)方法用来排序。

2.无序性和不可重复性的含义是什么？
无序性不等于随机性，指存储的数据在底层数组并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
不可重复性指添加的元素按照equals()判断时，返回false，需要同时重写equals(）和 hashcode（）方法。

3.HashSet，LinkedHashSet,TreeSet异同？
HashSet为Set接口的主要实现类，底层是HashMap,线程不安全，可存null值。
LinkedHashSet是HashSet子类，能够按照添加顺序遍历。
TreeSet底层红黑树，能按照添加顺序遍历，排序方式分为自然排序、定制排序。

5.Map接口

1. HashMap 和 HashSet 区别？

2. HashMap 和 TreeMap 区别？

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。
实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

实现SortMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。

3.HashSet 如何检查重复？

当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

hashCode()与 equals() 的相关规定：

如果两个对象相等，则 hashcode 一定也是相同的
两个对象相等,对两个 equals() 方法返回 true
两个对象有相同的 hashcode 值，它们也不一定是相等的
综上，equals() 方法被覆盖过，则 hashCode() 方法也必须被覆盖
hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

==与 equals 的区别

对于基本类型来说，== 比较的是值是否相等；

对于引用类型来说，== 比较的是两个引用是否指向同一个对象地址（两者在内存中存放的地址（堆内存地址）是否指向同一个地方）；

对于引用类型（包括包装类型）来说，equals 如果没有被重写，对比它们的地址是否相等；如果 equals()方法被重写（例如 String），则比较的是地址里的内容。

4.HashMap 的底层实现?

jdk1.8之前，hashMap底层是数组和链表，也就是链表散列。
HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

5.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，竞争会越来越激烈效率越低。

HashTable:

JDK1.7 的 ConcurrentHashMap：

JDK1.8 的 ConcurrentHashMap：

JDK1.8 的 ConcurrentHashMap 不在是 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。当冲突链表达到一定长度时，链表会转换成红黑树。

6.Collections 工具类

同步控制:

Collections 提供了多个synchronizedXxx()方法·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。

我们知道 HashSet，TreeSet，ArrayList,LinkedList,HashMap,TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合。

需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。