什么是集合

集合框架：用于存储数据的容器。

集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。 任何集合框架都包含三大块内容：对外的接口、接口的实现和对集合运算的算法。

集合的特点

集合的特点主要有如下两点：

• 对象封装数据，对象多了也需要存储。集合用于存储对象。

• 对象的个数确定可以使用数组，对象的个数不确定的可以用集合。因 为集合是可变长度的。

集合和数组的区别

• 数组是固定长度的；集合可变长度的。

• 数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。

• 数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同 数据类型。

Java 集合概览

从下图可以看出，在 Java 中除了以 Map 结尾的类之外， 其他类都实现了 Collection 接⼝。并且，以 Map 结尾的类都实现了 Map 接⼝。

集合框架是一个用来代表和操纵集合的统一架构。所有的集合框架都包含如下内容：

• **接口：**是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口，是为了以不同的方式操作集合对象
• **实现（类）：**是集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。
• **算法：**是实现集合接口的对象里的方法执行的一些有用的计算，例如：搜索和排序。这些算法被称为多态，那是因为相同的方法可以在相似的接口上有着不同的实现。

List,Set,Map 三者的区别

先简单说下集合和数组的区别：

数组是大小固定的，并且同一个数组只能存放类型一样的数据（基本类型/引用类型），而JAVA集合可以存储和操作数目不固定的一组数据。所有的JAVA集合都位于java.util包中。 JAVA集合只能存放引用类型的的数据，不能存放基本数据类型。

List：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素，元素都有索引。

Set：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素， 只允许存入一个null元素，必须保证元素唯一性。

Map: 使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。

常用的集合类有哪些？

Java 容器分为 Collection 和 Map 两大类，Collection集合的子接口有Set、 List、Queue三种子接口。

• Collection接口的子接口包括：Set接口和List接口
• Map接口的实现类主要有：HashMap、TreeMap、Hashtable、 ConcurrentHashMap以及Properties等
• Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等
• List接口的实现类主要有：ArrayList、LinkedList等

常用集合数据结构

1、ArrayList

ArrayList 是最常用的 List 实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要将已经有数组的数据复制到新的存储空间中。当从 ArrayList 的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。

ArrayList可以通过构造方法在初始化的时候指定底层数组的大小。

通过无参构造方法的方式ArrayList()初始化，则赋值底层数Object[] elementData为一个默认空数组Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}，所以数组容量为0，只有真正对数据进行添加add时，才分配默认DEFAULT_CAPACITY = 10的初始容量。

transient Object[] elementData; // non-private to simplify nested class access
 
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

2、LinkedList

LinkedList 是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了 List 接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。

    transient Node<E> first;
    transient Node<E> last;

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

3、HashSet

哈希表边存放的是哈希值。HashSet 存储元素的顺序并不是按照存入时的顺序（和 List 显然不同） 而是按照哈希值来存的所以取数据也是按照哈希值取得。元素的哈希值是通过元素的hashcode 方法来获取的, HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较equals 方法 如果 equls 结果为 true ，HashSet 就视为同一个元素。如果 equals 为 false 就不是同一个元素。

哈希值相同 equals 为 false 的元素是怎么存储呢,就是在同样的哈希值下顺延（可以认为哈希值相同的元素放在一个哈希桶中）。也就是哈希一样的存一列。如图 1 表示 hashCode 值不相同的情况；图 2 表示 hashCode 值相同，但 equals 不相同的情况。

HashSet 通过 hashCode 值来确定元素在内存中的位置。一个 hashCode 位置上可以存放多个元素。

equals 和 hashCode 这两个方法都是从 object 类中继承过来的，equals 主要⽤于判断对象的内存地址引用是否是同⼀个地址；hashCode 根据定义的哈希规则将对象的内存地址转换为⼀个哈希码。HashSet 中存储的元素是不能重复的，主要通过 hashCode 与 equals 两个方法来判断存储的对象是否相同：

• 如果两个对象的 hashCode 值不同，说明两个对象不相同。
• 如果两个对象的 hashCode 值相同，接着会调用对象的 equals 方法，如果 equlas 方法的返回结果为true，那么说明两个对象相同，否则不相同。

HashSet 通过 HashMap 实现，HashMap 的 Key 即 HashSet 存储的元素，Value 系统⾃定义⼀个名为PRESENT 的 Object 类型常量。

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();


 public HashSet() {
        map = new HashMap<>();
 }
  public boolean add(E e) {
        return map.put(e, PRESENT)==null;
  }

4、TreeSet

TreeSet是通过TreeMap实现的一个有序的、不可重复的集合，底层维护的是红黑树结构。当TreeSet的泛型对象不是java的基本类型的包装类时，对象需要重写Comparable#compareTo()方法。

add()的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。

public class TreeSet<E> extends AbstractSet<E> 
    implements NavigableSet<E>, Cloneable, java.io.Serializable { 
    // 使用 NavigableMap 的 key 来保存 Set 集合的元素
    private transient NavigableMap<E,Object> m; 
    // 使用一个 PRESENT 作为 Map 集合的所有 value。
    private static final Object PRESENT = new Object(); 
    // 包访问权限的构造器，以指定的 NavigableMap 对象创建 Set 集合
    TreeSet(NavigableMap<E,Object> m) { 
        this.m = m; 
    } 
      // ①
    public TreeSet(){ 
        // 以自然排序方式创建一个新的 TreeMap，
        // 根据该 TreeSet 创建一个 TreeSet，
        // 使用该 TreeMap 的 key 来保存 Set 集合的元素
        this(new TreeMap<E,Object>()); 
    } 
      // ②
    public TreeSet(Comparator<? super E> comparator){ 
        // 以定制排序方式创建一个新的 TreeMap，
        // 根据该 TreeSet 创建一个 TreeSet，
        // 使用该 TreeMap 的 key 来保存 Set 集合的元素
        this(new TreeMap<E,Object>(comparator)); 
    } 
    public TreeSet(Collection<? extends E> c) { 
        // 调用①号构造器创建一个 TreeSet，底层以 TreeMap 保存集合元素
        this(); 
        // 向 TreeSet 中添加 Collection 集合 c 里的所有元素
        addAll(c); 
    } 
    public TreeSet(SortedSet<E> s) { 
        // 调用②号构造器创建一个 TreeSet，底层以 TreeMap 保存集合元素
        this(s.comparator()); 
        // 向 TreeSet 中添加 SortedSet 集合 s 里的所有元素
        addAll(s); 
    } 
    //TreeSet 的其他方法都只是直接调用 TreeMap 的方法来提供实现
    ... 
    public boolean addAll(Collection<? extends E> c){ 
        if (m.size() == 0 && c.size() > 0 && 
            c instanceof SortedSet && 
            m instanceof TreeMap){ 
            // 把 c 集合强制转换为 SortedSet 集合
            SortedSet<? extends E> set = (SortedSet<? extends E>) c; 
            // 把 m 集合强制转换为 TreeMap 集合
            TreeMap<E,Object> map = (TreeMap<E, Object>) m; 
            Comparator<? super E> cc = (Comparator<? super E>) set.comparator(); 
            Comparator<? super E> mc = map.comparator(); 
            // 如果 cc 和 mc 两个 Comparator 相等
            if (cc == mc || (cc != null && cc.equals(mc))){ 
                // 把 Collection 中所有元素添加成 TreeMap 集合的 key 
                map.addAllForTreeSet(set, PRESENT); 
                return true; 
            } 
        } 
        // 直接调用父类的 addAll() 方法来实现
        return super.addAll(c); 
    } 
    ... 
 } 

从上面代码可以看出，TreeSet 的 ① 号、② 号构造器的都是新建一个 TreeMap 作为实际存储 Set 元素的容器，而另外 2 个构造器则分别依赖于 ① 号和 ② 号构造器，由此可见，TreeSet 底层实际使用的存储容器就是 TreeMap。

5、HashMap

HashMap 根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap。

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

大方向上，HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。上图中，每个绿色的实体是嵌套类 Entry 的实例，Entry 包含四个属性：key, value, hash 值和用于单向链表的 next。

• capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。
• loadFactor：负载因子，默认为 0.75。
• threshold：扩容的阈值，等于 capacity * loadFactor

Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。

根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，在 Java8 中，当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

6、TreeMap

TreeMap 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。如果使用排序的映射，建议使用 TreeMap。

如何选用集合?

主要根据集合的特点来选⽤，比如我们需要根据键值获取到元素值时就选用Map 接⼝下的集合，需要排序时选择 TreeMap ,不需要排序时就选择 HashMap ,需要保证线程安全就选用ConcurrentHashMap 。

当只需要存放元素值时，就选择实现 Collection 接⼝的集合，需要保证元素唯⼀时选择实现Set 接口的集合比如 TreeSet 或 HashSet ，不需要就选择实现 List 接⼝的比如 ArrayList或 LinkedList ，然后再根据实现这些接⼝的集合的特点来选用。

有哪些集合是线程不安全的？

常用的 ArrayList, LinkedList , HashMap , HashSet , TreeSet , TreeMap 都不是线程安全的。

如果要使用线程安全的集合的话， java.util.concurrent 包中提供了很多并发容器供你使用：

• ConcurrentHashMap 对应线程不安全的 HashMap
• CopyOnWriteArrayList 写时复制容器，对应线程不安全的 ArrayList
• ConcurrentLinkedQueue 高效效的并发队列 对应线程不安全的 LinkedList
• ConcurrentSkipListSet 线程安全的有序的集合，对应线程不安全的 TreeSet

在多线程下也可以这样使用ArrayList，可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。

List<String> synchronizedList = Collections.synchronizedList(list); 

Arraylist 与 LinkedList 区别

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

ArrayList 的优缺点

ArrayList的优点如下：

ArrayList 底层以数组实现，是一种随机访问模式。ArrayList 实现了 RandomAccess 接口，因此查找的时候非常快。

ArrayList 在顺序添加一个元素的时候非常方便。

ArrayList 的缺点如下：

删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。

插入元素的时候，也需要做一次元素复制操作，缺点同上。

ArrayList 比较适合顺序添加、随机访问的场景。

HashMap是怎么解决哈希冲突的？

在解决这个问题之前，我们首先需要知道什么是哈希冲突，而在了解哈希冲突之前我们还要知道什么是哈希才行；

什么是哈希？

Hash，一般翻译为“散列”，也有直接音译为“哈希”的，这就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）；

这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。

什么是哈希冲突？

当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把 它叫做碰撞（哈希碰撞）。

HashMap的数据结构

在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是： 寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做链地址法的方式可以解决哈希冲突：

这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下，但相比于hashCode返回的int类型，我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要远小于int类型的范围，所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表， 所以我们还需要对hashCode作一定的优化 。

hash()函数

上面提到的问题，主要是因为如果使用hashCode取余，那么相当于参与运算的 只有hashCode的低位，高位是没有起到任何作用的，所以我们的思路就是让 hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分 布更平均，我们把这样的操作称为扰动，在JDK 1.8中的hash()函数如下：

static final int hash(Object key) { 

int h; 
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右 移16位进行异或运算（高低位异或）
}

JDK1.8新增红黑树

通过上面的链地址法（使用散列表）和扰动函数我们成功让我们的数据分布更平均，哈希碰撞减少，但是当我们的HashMap中存在大量数据时，加入我们某个bucket下对应的链表有n个元素，那么遍历时间复杂度就为O(n)，为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使得遍历复杂度降低至O(logn)；

HashSet 如何检查重复

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

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

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

HashSet加入的对象需要重写hashCode方法和equals方法，因为对于自定义类需要提供判断怎样才算重复元素的方法。

package com.demo.model;

import java.util.HashSet;
import java.util.Iterator;

class Student {
    private int age;
    private String name;

    public Student(int age, String name) {
        this.age = age;
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "name:" + name + "age:" + age;
    }

    //HashSet加入的对象需要重写hashCode方法和equals方法，因为对于自定义类需要提供判断怎样才算重复元素的方法。
    //本例中的hashCode方法和equals方法即是用来判断student对象是否为重复对象的标准方法。
    @Override
    public int hashCode() {
        return name.hashCode() ;
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Student)) {
            return false;
        }
        Student student = (Student) obj;
        return this.name.equals(student.name) ;
    }
}

public class HashSetTest {

    public static void main(String[] args) {
        HashSet hs = new HashSet();
        hs.add(new Student(20, "tan1"));
        hs.add(new Student(21, "tan2"));
        hs.add(new Student(22, "tan3"));
        hs.add(new Student(20, "tan1"));

        hs.add(null);//HashSet中可以添加null值

        Iterator it = hs.iterator();
        while (it.hasNext()) {
            Object obj = it.next();
            if (obj == null) {
                System.out.println(obj);
                continue;
            } else {
                Student s = (Student) obj;
                System.out.println("name:" + s.getName() + " " + "age:" + s.getAge());
            }
        }
    }
}

null name:tan3 age:22 name:tan1 age:20 name:tan2 age:21