Java基础知识第三讲：深入集合类（常用的集合类有哪些？比如List如何排序？集合的安全？）

1、collections框架（包括列表list，queue队列，set集合，stack栈，map键值对）

提供排序，查找，反转，替换，复制，取最小，最大元素等功能

从下面的集合框架图可以看到，Java集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection接口又有3种子类型，List、Set和Queue，再下面是一些抽象类，最后是具体实现类，常用的有ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap等等

1.1、set 元素不能重复，使用equals确保对象一致性—>实现类hashset treeset（有序）

只能通过迭代器（Iterator）来遍历元素

方法：add、contains、remove、clear

1、ArrayList list = new ArrayList(); list.add(300); list.add(120);

2、new TreeSet().addAll(list);

1.1.1、set元素不能重复，使用equals确保对象一致性------实现类hashset treeset（有序）

Set接口扩展自Collection，它与List的不同之处在于，规定Set的实例不包含重复的元素。AbstractSet是一个实现Set接口的抽象类，Set接口有三个具体实现类，分别是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet。只能通过迭代器（Iterator）来遍历元素。方法：add、contains、remove、clear

1.1.2、散列集HashSet：是Set接口的一个子类，无序集合，采用hash存储，所以没有顺序，依赖HashMap来实现，可null

可以使用它的无参构造方法来创建空的散列集，也可以由一个现有的集合创建散列集。在散列集中，有两个名词需要关注，初始容量和客座率。实际上HashSet就是基于后面介绍的HashMap而实现的，客座率是确定在增加规则集之前，该规则集的饱满程度，当元素个数超过了容量与客座率的乘积时，容量就会自动翻倍，HashSet的数据存储在HashMap的map中，对应于map中的key

1.1.3、链式散列集LinkedHashSet

LinkedHashSet是继承自HashSet的，支持对规则集内的元素排序。HashSet中的元素是没有被排序的，而 LinkedHashSet 中的元素可以按照它们插入规则集的顺序提取。性能低于HashSet，因为需要维护链表的开销

1.1.4、树形集TreeSet

TreeSet实现 SortedSet 接口，有序集合；依赖TreeMap来实现//插入一个子集，在实例化TreeSet时，我们可以给TreeSet指定一个比较器Comparator来指定树形集中的元素顺序，默认升序；不可null

例子

public class TestSet {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(1111);
        set.add(2222);
        set.add(3333);
        set.add(4444);
        set.add(5555);
        System.out.println(set.first()); // 输出第一个元素
        System.out.println(set.lower(3333)); //小于3333的最大元素
        System.out.println(set.higher(2222)); //大于2222的最大元素
        System.out.println(set.floor(3333)); //不大于3333的最大元素
        System.out.println(set.ceiling(3333)); //不小于3333的最大元素
        System.out.println(set.pollFirst()); //删除第一个元素
        System.out.println(set.pollLast()); //删除最后一个元素
        System.out.println(set);
    }
}

1、ArrayList<Integer> list = new ArrayList<Integer>(); 
list.add(300);   
list.add(120);
2、new TreeSet<Integer>().addAll(list);

1.2、list 有序 按进入的顺序存储，元素可以重复

List接口扩展自Collection，它可以定义一个允许重复的有序集合，从List接口中的方法来看，List 接口主要是增加了面向位置的操作，允许在指定位置上操作元素，同时增加了一个能够双向遍历线性表的新列表迭代器ListIterator。AbstractList类提供了List接口的部分实现，AbstractSequentialList扩展自AbstractList，主要是提供对链表的支持。

实现类

• 1、linkedlist（双向链表，查找慢，增删快，不安全）
• 2、ArrayList（基于数组实现，查找快，增删慢，线程不安全）
• 3、Stack 类: Stack继承自Vector，实现一个后进先出的堆栈（基于数组，安全）

可以看到 ArrayList、Vector、LinkedList 集合类继承了 AbstractList 抽象类，而 AbstractList 实现了 List 接口，同时也继承了 AbstractCollection 抽象类。ArrayList、Vector、LinkedList 又根据自我定位，分别实现了各自的功能。ArrayList 和 Vector 使用了数组实现，这两者的实现原理差不多，LinkedList 使用了双向链表实现

Q1：关于ArrayyList的三道面试题？（20191004补充）

Q2：ArrayList和LinkedList内部的实现大致是怎样的？他们之间的区别和优缺点？看过源码！！！（掌握到源码级别，蚂蚁**）

1.2.1、Arraylist 解析

它是用数组存储元素的，这个数组可以动态创建，如果元素个数超过了数组的容量，那么就创建一个更大的新数组，并将当前数组中的所有元素都复制到新数组中。基于动态数组的数据结构，查找快，插入慢，每次增删元素顺序都会操作每个元素，线程不安全 初始10，扩容步长0.5，数组的复制）

分别分析 ArrayList 的构造、add、remove、clear 方法的实现原理

• 数据结构

// 默认初始化容量

private static final int DEFAULT_CAPACITY = 10;

// 对象数组

transient Object[] elementData;

// 数组长度

private int size;

1. 构造函数

• 空参构造：array是一个Object[]类型，当我们new一个空参ArrayList的时候，系统内部使用了一个new Object[0]数组。
• 带参构造1：该构造函数传入一个int值，该值作为数组的长度值
• 带参构造2：调用构造函数的时候传入了一个Collection的子类

//用来存放数据元素的数组
transient Object[] elementData;
//当前存储元素的个数
private int size;

• add方法 （两个重载：一种是直接将元素加到数组的末尾，另外一种是添加元素到任意位置）

1、首先将成员变量array赋值给局部变量a，将成员变量size赋值给局部变量s。

2、判断集合的长度s是否等于数组的长度，重新分配数组的时候需要计算新分配内存的空间大小

3、将新添加的object对象作为数组的a[s]个元素

4、修改集合长度size为s+1

5、modCotun++

6、return true

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  //扩容处理
    elementData[size++] = e;//添加元素
    return true;
}
//此方法主要是确定将要创建的数组大小。
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//确定了添加元素后的大小之后将元素复制到新数组中
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容后的容量增加一半
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
       newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

• remove方法（两个重载）

1、先将成员变量array和size赋值给局部变量a和s

2、判断形参index是否大于等于集合的长度，如果成了则抛出运行时异常

3、获取数组中脚标为index的对象result，该对象作为方法的返回值

4、调用System的arraycopy函数，集合整体向前移动了一位

5、最后一个元素设置为null

6、重新给成员变量array和size赋值

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0) // 删除某个元素时需要移动其它数组元素
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

• clear方法

如果集合长度不等于0，则将所有数组的值都设置为null，然后将成员变量size 设置为0即可，最后让修改记录数加1

1.2.2、LinkedList 基于双向链表实现，增删快，查询慢，线程不安全

LinkedList是在一个链表中存储元素，LinkedList的元素添加和删除其实就对应着链表节点的添加和移除。基于双向链表的数据结构，有一个内部类作为存放元素的单元，里面有三个属性，用来存放元素本身以及前后2个单元的引用，查找慢，会遍历大量元素，插入快，不安全）

• 数据结构（LinkedList 定义了一个 Node 结构，Node 结构中包含了 3 个部分：元素内容 item、前指针 prev 以及后指针 next）

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;
        }
    }

• LinkedList 实现类

LinkedList 类实现了 List 接口、Deque 接口，同时继承了 AbstractSequentialList抽象类, LinkedList 既实现了 List 类型又有 Queue 类型的特点 ；LinkedList 也实现了 Cloneable 和 Serializable 接口，同 ArrayList 一样，可以实现克隆和序列化

• LinkedList 属性(可以看到这三个属性都被 transient 修饰了，原因很简单，我们在序列化的时候不会只对头尾进行序列化，所以 LinkedList 也是自行实现 readObject 和 writeObject 进行序列化与反序列化)

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

1. 构造函数

//存储的元素个数
transient int size = 0;
//头节点
transient Node<E> first;
//尾节点
transient Node<E> last;

2. 添加元素

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++;
}

3. 删除元素

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {// 当前节点为头节点，重置头节点
        first = next;
    } else {//当前节点非头节点，将前驱节点和后继节点连接
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {//当前节点为尾节点，重置尾节点
        last = prev;
    } else {// 当前节点非尾节点
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}

4. LinkedList 遍历元素
   LinkedList 的获取元素操作实现跟 LinkedList 的删除元素操作基本类似，通过分前后半段来循环查找到对应的元素。但是通过这种方式来查询元素是非常低效的，特别是在 for 循环遍历的情况下，每一次循环都会去遍历半个 List。所以在 LinkedList 循环遍历时，我们可以使用 iterator 方式迭代循环，直接拿到我们的元素，而不需要通过循环查找 List。

1.2.3、ArrayList 和 LinkedList 性能测试结论

• 1、当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；
  
• 2、当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了
  

1.2.5、数组和 ArrayList 的区别，如何正确的将数组转换为ArrayList?

数组和 ArrayList 的区别

• 1、数组可以包含基本类型和对象类型，arraylist只能包含对象类型
• 2、数组大小固定，arraylist大小可以动态变化

如何正确的将数组转换为ArrayList

//1. 最简便的方法(推荐)
List list = new ArrayList<>(Arrays.asList("a", "b", "c"))
//2. 使用 Java8 的Stream(推荐)
Integer [] myArray = { 1, 2, 3 };
List myList = Arrays.stream(myArray).collect(Collectors.toList());
//基本类型也可以实现转换（依赖boxed的装箱操作）
int [] myArray2 = { 1, 2, 3 };
List myList = Arrays.stream(myArray2).boxed().collect(Collectors.toList());
//3. 使用 Guava(推荐)
对于不可变集合，你可以使用ImmutableList类及其of()与copyOf()工厂方法：（参数不能为空）
List<String> il = ImmutableList.of("string", "elements");  // from var args
List<String> il = ImmutableList.copyOf(aStringArray);      // from array
//对于可变集合，你可以使用Lists类及其newArrayList()工厂方法：
List<String> l1 = Lists.newArrayList(anotherListOrCollection);    // from collection
List<String> l2 = Lists.newArrayList(aStringArray);               // from array
List<String> l3 = Lists.newArrayList("or", "string", "elements"); // from var args
//4. 使用 Apache Commons Collections
List<String> list = new ArrayList<String>();
CollectionUtils.addAll(list, str);

1.2.6、 ArrayList和LinkedList内部的实现大致是怎样的？他们之间的区别和优缺点？看过源码！！！（掌握到源码级别，蚂蚁）

先说结论：

• Arraylist优点：基于动态数组的数据结构,因为地址连续，查询操作效率会比较高 缺点：插入和删除操作效率比较低
• LinkedList优点：基于链表的数据结构,地址是任意的，新增和删除操作占优势，适用于要头尾操作或插入指定位置 缺点：查询操作性能比较低

具体数据结构见上文

再来分析性能：

• 1．对 ArrayList 和 LinkedList 而言，在列表末尾增加一个元素所花的开销都是固定的。

对ArrayList 而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；

对LinkedList 而言，这个开销是统一的，分配一个内部Entry对象

• 2、在 ArrayList 的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList 的中间插入或删除一个元素的开销是固定的；
  
• 3、LinkedList 不支持高效的随机元素访问；
  
• 4、ArrayList 的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
  

使用建议：

1、当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；

2、当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了

1.2.7、Vector 基于数组实现、增删慢、查询快、线程安全

Vector数据结构和ArrayList一样，都是基于数组实现的，不同的是Vector支持线程同步，即统一时刻只允许一个线程对Vector进行写操作，以保证多线程环境下的数据一致性，但需要频繁对Vector实例进行加锁和释放锁操作，因此，Vector的读写效率整体上比ArrayList低。

1.7.8、线程安全集合

Lis list = Collections.synchronizedLis(new ArrayLis());

它的实现，基本就是将每个基本方法，比如get、set、add之类，都通过synchronizd添加基本的同步支持，非常简单粗暴，但也非常实用,当发生意外的并发修改时，尽早抛出ConcurrentModifcationException异常，以避免不可预计的行为

1.3、map 键值对 键唯一，值可重复。

Map，图，是一种存储键值对映射的容器类，在Map中键可以是任意类型的对象，但不能有重复的键，每个键都对应一个值，真正存储在图中的是键值构成的条目

1.3.1、hashmap详解（基于散列表，使用对象的hash值可以快速查询，允许空键值，containskey，containsvalue不安全 默认16 *1.5 Iterator） 美团面试题

HashMap实现原理，如何保证HashMap的线程安全？

JDK 1.7:位桶(Hash表)+链表的方式

JDK8:位桶(Hash表)+链表/红黑树

• HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当链表中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间

从 HashMap 的源码中，我们可以发现，HashMap 是由一个 Node 数组构成，每个 Node 包含了一个 key-value 键值对。 (20191004补充)

transient Node<K,V>[] table;

Node 类作为 HashMap 中的一个内部类，除了 key、value 两个属性外，还定义了一个 next 指针。当有哈希冲突时，HashMap 会用之前数组当中相同哈希值对应存储的 Node 对象，通过指针指向新增的相同哈希值的 Node 对象的引用。

static class Node<K,V> implements Map.Entry<K,V> {
     final int hash;
     final K key;
     V value;
     Node<K,V> next;
     Node(int hash, K key, V value, Node<K,V> next) {
         this.hash = hash;
         this.key = key;
         this.value = value;
         this.next = next;
     }
}

HashMap 还有两个重要的属性：加载因子（loadFactor）和边界值（threshold）。在初始化 HashMap 时，就会涉及到这两个关键初始化参数。LoadFactor 属性是用来间接设置 Entry 数组（哈希表）的内存空间大小，在初始 HashMap 不设置参数的情况下，默认 LoadFactor 值为 0.75

int threshold;
final float loadFactor;

1、初始容量表示哈希表的长度，初始是16

2、哈希表中的条目数超出了加载因子0.75与当前容量的乘积时，则要对该哈希表进行 resize 操作

3、加入键值对时，先判断当前已用数组长度是否大于等于阀值，如果大于等于，则进行扩容，容量扩为原容量2倍

hashmap的数据结构？

• hashmap的特点？

1、HashMap处理hash冲突时，会首先存放在链表中去，链表的长度达到阀值8，链表就将转换成红黑树；小于6，转链表，优化存储速度。O(lgn)

2、HashMap底层维护一个数组，数组中的存储Entry对象组成的链表

3、Map中的key，value则以Entry的形式存放在数组中，通过key的hashCode计算

4、map m = collections.synchronizedMap（new hashmap（）），返回同步的map，有hashmap所有的方法

5、concurrenthashmap 系统自带的线程安全的HashMap

• ConcurrentHashMap和synchronizedMap两者区别：

1、ConcurrentHashMap的实现更加精细，在性能以及安全性方面更优

同步操作精确控制到node，其他线程，仍然可以对node执行某些操作

多个读操作几乎总可以并发地执行

例如：在遍历map时，其他线程试图对map进行数据修改，不会抛出ConcurrentModificationException***

2.synchronizedMap()可以接收任意Map实例，实现Map的同步，如TreeMap实现排序，Map<String, Object> map2 = Collections.synchronizedMap(new TreeMap<String, Object>());

而ConcurrentHashMap只能是HashMap

1.3.2、讲一下hashmap中put方法过程？

HashMap 添加元素优化:初始化完成后，HashMap 就可以使用 put() 方法添加键值对了。从下面源码可以看出，当程序将一个 key-value 对添加到 HashMap 中，程序首先会根据该 key 的 hashCode() 返回值，再通过 hash() 方法计算出 hash 值，再通过 putVal 方法中的 (n - 1) & hash 决定该 Node 的存储位置。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash函数是怎么实现的？ ****

1、散列算法 hash&(length-1)

2、hash的高16bit和低16bit做了一个异或

3、（n-1）&hash 得到下标

4、使用&代替取模，实现了均匀的散列，但效率要高很多，与运算比取模的效率高（由于计算机组成原理）

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
    // 通过 putVal 方法中的 (n - 1) & hash 决定该 Node 的存储位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

1、对key求hash值，然后再计算下标

2、如果没有碰撞，直接放入桶中；（key相同，替换value值）

3、如果碰撞了，以链表的方式链接到后面（key不同，用链表存）

4、如果链表长度超过阈值8，就把链表转成红黑树

5、如果节点已经存在就替换旧值；

6、如果桶满了（容量*加载因子），就需要resize

• HashMap中put操作的源码 Demo

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab;
    Node<K,V> p;
    int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
    //1、判断当table为null或者tab的长度为0时，即table尚未初始化，此时通过 resize() 方法得到初始化的 table
    n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
    //1.1、此处通过（n - 1） & hash 计算出的值作为 tab 的下标 i，并另 p 表示 tab[i]，也就是该链表第一个节点的位置。并判断 p 是否为 null
      tab[i] = newNode(hash, key, value, null);
      //1.1.1、当 p 为 null 时，表明 tab[i] 上没有任何元素，那么接下来就 new 第一个 Node 节点，调用 newNode 方法返回新节点赋值给 tab[i]
    else {
    //2.1 下面进入 p 不为 null 的情况，有三种情况：p 为链表节点；p 为红黑树节点；p 是链表节点但长度为临界长度 TREEIFY_THRESHOLD，再插入任何元素就要变成红黑树了。
        Node<K,V> e;
        K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    //2.1.1HashMap 中判断 key 相同的条件是 key 的 hash 相同，并且符合 equals 方法。这里判断了 p.key 是否和插入的 key 相等，如果相等，则将 p 的引用赋给 e
            e = p;
        else if (p instanceof TreeNode)
      //2.1.2 现在开始了第一种情况，p 是红黑树节点，那么肯定插入后仍然是红黑树节点，所以我们直接强制转型 p 后调用 TreeNode.putTreeVal 方法，返回的引用赋给 e
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
      //2.1.3 接下里就是 p 为链表节点的情形，也就是上述说的另外两类情况：插入后还是链表 / 插入后转红黑树。另外，上行转型代码也说明了 TreeNode 是 Node 的一个子类
            for (int binCount = 0; ; ++binCount) {
        // 我们需要一个计数器来计算当前链表的元素个数，并遍历链表，binCount 就是这个计数器
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
            // 插入成功后，要判断是否需要转换为红黑树，因为插入后链表长度加 1，而 binCount 并不包含新节点，所以判断时要将临界阈值减 1
                        treeifyBin(tab, hash);
          // 当新长度满足转换条件时，调用 treeifyBin 方法，将该链表转换为红黑树
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

1.3.3、为什么哈希表的容量一定要是2的整数次幂?

第二种问法：实际应用中，我们设置初始容量，一般得是 2 的整数次幂。你知道原因吗？（面试题：2的幂次方减1后每一位都是1，让数组每一个位置都能添加到元素。减少哈希冲突，均匀分布元素）

h&(length-1)，散列的均匀、空间利用充足

1、2的整数次幂为偶数，length-1为奇数，最后一位是1，保证h&(length-1)的最后一位可能为0或1，保证散列的均匀性，且空间利用充足

2、length为奇数的话，length-1为偶数，最后一位是0，h&(length-1)的最后一位为0，浪费了近一半的空间

3、h是key的hashcode的高16位和低16位的异或运算，之所以异或，是因为生成0/1的概率相等

1.3.4、hashmap怎样解决冲突、讲一下扩容过程，假设一个值在原数组中，现在移动了新数组，位置肯定变了，那么怎么定位到这个值在新数组中的位置？ 重点

新建一个HashMap的底层数组，而后调用transfer方法，将就HashMap的全部元素添加到新HashMap

要重新计算元素在新的数组中的索引位置

• 首次 put 时， 先会触发扩容（ 算是初始化） ， 然后存入数据， 然后判断是否需要扩容；
• 不是首次 put， 则不再初始化， 直接存入数据， 然后判断是否需要扩容；

1.3.5、子类：

• 1、LinkedHashMap维护了插入的先后顺序【FIFO】，适合LRU算法做缓存（最近最少使用）(在项目中被用到过)
  Demo如下所示：

LinkedHashMap<Long, String> unchecked = new LinkedHashMap<Long, String >(20, .75F, true) {
     @Override
     protected boolean removeEldestEntry(Map.Entry<Long, String> eldest){
         //什么时候执行LRU操作
         return this.size() > 20;
     }
 };

• 2、WeakHashMap是改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收

1.3.6、hash冲突如何解决？

方式有很多，比如，开放定址法、再哈希函数法和链地址法

1.3.7、get操作：

对key进行null检查：如果key是null，返回table[0]位置元素

key的hashcode()方法被调用，然后计算hash值

indexFor(hash,table.length)用来计算要获取的Entry对象在table数组中的精确的位置

遍历链表，调用equals()方法检查key相等性，如果equals()方法返回true，get方法返回Entry对象的value，否则，返回null

性能上：在链表长度过长的情况下，性能将明显降低，红黑树的使用很好地解决了这个问题，使得查询的平均复杂度降低到了 O(log(n))，链表越长，使用黑红树替换后的查询效率提升就越明显。

1.3.8、hashmap从1.7到1.8,新元素为什么要从头部调整到尾部呢？

1.3.9、hashmap的put和get的时间复杂度算多少啊?

hashmap的最优时间复杂度是O（1），而最坏时间复杂度是O(n)。

在没有产生hash冲突的情况下，查询和插入的时间复杂度是O(1)；

而产生hash冲突的情况下，如果是最终插入到链表，链表的插入时间复杂度为O(1)，而查询的时候，时间复杂度为O(n)；

在产生hash冲突的情况下，如果最终插入的是红黑树，插入和查询的平均时间复杂度是O（logn)。

1.3.10、hashtable（安全 enumeration 默认11 *2+1）treemap（使用红黑树实现，按序排序）

• 同步的，线程安全，效率低。添加数据使用put(key, value)，取出数据使用get(key)

1.3.11、TreeMap实现了SortedMap接口，默认根据key值进行升序排序，基于红黑树；不可null

TreeMap基于红黑树数据结构的实现，键值可以使用 Comparable 或 Comparator 接口来排序。TreeMap继承自AbstractMap，同时实现了接口 NavigableMap，而接口 NavigableMap 则继承自 SortedMap。SortedMap 是Map的子接口，使用它可以确保图中的条目是排好序的。

在实际使用中，如果更新图时不需要保持Map中元素的顺序，就使用HashMap，如果需要保持图中元素的插入顺序或者访问顺序，就使用LinkedHashMap，如果需要使图按照键值排序，就使用TreeMap

1.3.12、synchronizedMap()

一个静态内部类，实现了Map接口，通过synchronized关键字对map实现同步控制；传递任意map类型

1.3.13、对比Hashtable、HashMap、TreeMap有什么不同？

考点分析：Map相关可以扩展的问题很多，从各种数据结构、典型应用场景，到程序设计实现的技术考量，尤其是在Java8里，HashMap本身发生了非常大的变化，这些都是经常考察的方面

三者均实现了Map接口，存储的内容是基于key-value的键值对映射，一个映射不能有重复的键，一个键最多只能映射一个值。

一段话HashMap

HashMap基于哈希思想，实现对数据的读写。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，然后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。当两个不同的键对象的hashcode相同时，它们会储存在同一个bucket位置的链表中，可通过键对象的equals()方法用来找到键值对。如果链表大小超过阈值（TREEIFY_THRESHOLD, 8），链表就会被改造为树形结构。

1.3.13、HashSet 的 contains 方法判断元素是否在 HashSet 中，同样是 Set 的 TreeSet 其 contains 方法和 HashSet 有什么区别吗？

• HashSet 本质上就是 HashMap 的 key 组成的不重复的元素集合，contains 方法其实就是根据hashcode 和 equals 去判断相等的
• TreeSet 本质 TreeMap 的key组成的，数据结构是红黑树，是自带排序功能的，可以在放入元素的时候指定comparator（比较器），或者是放入的元素要实现 Comparable 接口后元素自己实现 compareTo方法，contains方法是根据比较器或者 compareTo去判断相等

1.4、Java Array、List、Set互相转化

todo

1.5、Queue

队列是一种先进先出的数据结构，元素在队列末尾添加，在队列头部删除。Queue接口扩展自Collection，并提供插入、提取、检验等操作。

• 方法offer表示向队列添加一个元素，poll()与remove()方法都是移除队列头部的元素，两者的区别在于如果队列为空，那么poll()返回的是null，而remove()会抛出一个异常。方法element()与peek()主要是获取头部元素，不删除
• 接口Deque，是一个扩展自Queue的双端队列，它支持在两端插入和删除元素，因为LinkedList类实现了Deque接口，所以通常我们可以使用LinkedList来创建一个队列。PriorityQueue类实现了一个优先队列，优先队列中元素被赋予优先级，拥有高优先级的先被删除

Queue是队列结构，Java中的常用队列如下：

• ArrayBlockingQueue

1.6、同步容器（强一致性）

同步容器指的是Vector、Stack、HashTable及Collections类中提供的静态工厂方法创建的类

• Vector：实现了List接口，Vector实际上就是一个数组，和ArrayList类似，但是Vector中的方法都是synchronized方法，即进行了同步措施；
• Stack：也是一个同步容器，它的方法也用synchronized进行了同步，它实际上是继承于Vector类
• HashTable：实现了Map接口，它和HashMap很相似，但是HashTable进行了同步处理，而HashMap没有
• Collections是一个工具提供类，提供一系列静态方法实现集合的查找/排序/线程同步（与Collection不同，是集合包顶层的接口）

1、比如List如何排序？

使用集合工具包的collections.sort（）方法排序，可以重写里面的compare方法

2、collections同步容器

Collections工具类提供了相关的API

Collections.synchronizedList(list）

Collections.synchronizedCollection( c)

Collections.synchronizedMap(m) Collections.synchronizedSortedMap(m)

Collections.synchronizedSet(s) Collections.synchronizedSortedSet(s)

1.7、HashMap排序

• 有一个<Integer,User>集合，User有name(String)和 age(int)属性。请写一个方法实现对HashMap 的排序功能，该方法接收HashMap<Integer,User>为形参，返回类型为 HashMap<Integer,User>，要求对HashMap中的User的age倒序进行排序。排序时key=value键值对不得拆散。
• 思路：使用LinkedHashMap

public class HashMapTest {
    public static void main(String[] args) { 
       HashMap<Integer, User> users = new HashMap<>();
     users.put(1, new User("张三", 25)); 
     users.put(3, new User("李四", 22)); 
     users.put(2, new User("王五", 28)); 
       System.out.println(users); 
       HashMap<Integer,User> sortHashMap = sortHashMap(users); 
       System.out.println(sortHashMap); 
     /** 11.    * 控制台输出内容 12.    * {1=User [name=张三, age=25], 2=User [name=王五, age=28], 
     3=User [name=李四, age=22]} 13.    {2=User [name=王五, age=28], 1=User [name=张三, age=25], 3=User [name=李四, age=22]} 14.    */ 
     } 
     public static HashMap<Integer, User> sortHashMap(HashMap<Integer, User> map) {
         // 首先拿到 map 的键值对集合 
         Set<Entry<Integer, User>> entrySet = map.entrySet();        
         // 将 set 集合转为 List 集合，为什么，为了使用工具类的排序方法
         List<Entry<Integer, User>> list = new ArrayList<Entry<Integer, User>>(entrySet); 
         // 使用 Collections 集合工具类对 list 进行排序，排序规则使用匿名内部类来实现 
         Collections.sort(list, new Comparator<Entry<Integer, User>>() { 
           @Override 
           public int compare(Entry<Integer, User> o1, Entry<Integer, User> o2) { 
             //按照要求根据 User 的 age 的倒序进行排
              return o2.getValue().getAge()-o1.getValue().getAge(); 
            } 
           }); 
          //创建一个新的有序的 HashMap 子类的集合 
          LinkedHashMap<Integer, User> linkedHashMap = new LinkedHashMap<Integer, User>(); 
          //将 List 中的数据存储在 LinkedHashMap 中 
          for(Entry<Integer, User> entry : list){ 
          linkedHashMap.put(entry.getKey(), entry.getValue());
      //返回结果 
      return linkedHashMap;

1.8、如何实现一个Hashtable？你的设计如何考虑Hash冲突？如何优化？

待补充

1.9、LinkingBlockingQueue与ArrayBlockingQueue的区别，他们的适用场景？

LinkingBlockQueue 链表实现的阻塞队列，适合一个一个放，一个一个取。

ArrayBlocakingQueue数组实现的阻塞队列，适合多个放，只适合多个取，不适合单个取。

2、Iterator：遍历集合

next方法返回第一个元素，hasNext判断容器是否还有元素，remove删除元素，遍历时对容器进行增加，删除操作会导致并发修改异常，

解决方法：把要删除的对象保存到一个集合中，遍历结束调用removeAll方法，或是Iterator.remove方法。

多线程中：并发异常如何避免：concurrenthashmap，copyonwritearraylist，线程安全；或是迭代器遍历时，放在synchronized代码块中，性能有影响。

子类 listIterator：继承自Iterator，可以双向遍历，支持元素的修改

3、collection集合接口 实现接口的类list和set

4、collections包装类，提供一系列静态方法实现集合的搜索，排序，线程安全化。

4.1、比如List如何排序？

使用集合工具包的collections.sort（）方法排序，可以重写里面的compare方法

4.2、集合的安全？(在并发编程中常用)

Collections工具类提供了相关的API

Collections.synchronizedList(list);
Collections.synchronizedCollection(c));
Collections.synchronizedMap(m);

5、 容器中的设计模式？

5.1、迭代器模式

Collection实现了Iterable接口，其中的iterator()方法能够产生一个Iterator对象，通过这个对象就可以迭代遍历Collection中的元素
从JDK1.5之后可以使用foreach方法来遍历实现了Iterable接口的聚合对象

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for(String item:list){syso(item);}

5.2、适配器模式

java.util.Arrays#asList()可以把数组类型转换为List类型

• 应该注意的是asList()的参数为泛型的变长参数，不能使用基本类型数组作为参数，只能使用相应的包装类型数组

Integer[] arr = {1, 2, 3}; List list = Arrays.asList(arr);//数组转为list
List list= Arrays.asList(1,2,3);

6、集合类实战

6.1、对null字段安全的集合排序方法 20210408补

• 需求：对updatedAt字段倒序排列，如果updatedAt字段为null，放在排序的末尾

public static void main(String[] args) {
        List<AgChannelGoodDTO> channelGoodDTOS = Lists.newArrayList();
        AgChannelGoodDTO dto1 = new AgChannelGoodDTO();
        dto1.setUpdatedAt(new Date(1617815417000L));
        dto1.setItemId(20L);
        AgChannelGoodDTO dto2 = new AgChannelGoodDTO();
        dto2.setUpdatedAt(new Date(1617854689000L));
        dto2.setItemId(21L);
        AgChannelGoodDTO dto3 = new AgChannelGoodDTO();
//        dto3.setUpdatedAt(new Date(1617815418000L));
        dto3.setItemId(22L);
        channelGoodDTOS.add(dto1);
        channelGoodDTOS.add(dto2);
        channelGoodDTOS.add(dto3);
        channelGoodDTOS.sort(Comparator.comparing(AgChannelGoodDTO::getUpdatedAt, Comparator.nullsLast(Comparator.reverseOrder())));
        System.out.println(channelGoodDTOS);
    }

6.2、应用场景：比如你需要实现一个云计算任务调度系统，希望可以保证VIP客户的任务被优先处理，你可以利用哪些数据结构或者标准的集合类型呢？更进一步讲，类似场景大多是基于什么数据结构呢？

利用PriorityBlockingQueue或Disruptor可实现基于任务优先级为调度策略的执行调度系统

Action1、关于hashCode和equals的处理，遵循如下规则：

• 1）只要重写equals，就必须重写hashCode。 equals判断是否相等，hashcode判断是否处于同一链条上
• 2）因为Set存储的是不重复的对象，依据hashCode和equals进行判断，所以Set存储的对象必须重写这两个方法
• 3）如果自定义对象作为Map的键，那么必须重写hashCode和equals。

• String重写了这两方法，所以我们可以非常与快递使用String对象作为key来使用

Action2、ArrayList的subList结果不可强转为ArrayList，否则会抛出 ClassCastException异常。即java.util.RandomAccessSubList cannot be cast to java.util.ArrayList

• 说明：sublist返回的是ArrayList 的内部类Sublist，并不是ArrayList而是ArrayList的一个视图，对于SubList子列表的所有操作最终会反映到原列表上

Action3、在subList场景中，高度注意对原集合的增加和删除，均会导致子列表的遍历、增加、删除产生ConcurrentModificationException异常。

• 说明： 抽查表明， 90% 的程序员对此知识点都有错误的认知。

Action4、使用集合转数组的方法，必须使用集合的toArray(T[] array),传入的是类型完全一样的数组，大小就是list.size().

• 说明：使用toArray带参方法，入参分配的数组空间不够大时，toArray方法内部将重新分配内存空间，并返回新数组地址；如果数组元素个数大于实际所需，下标为[list.size()]的数组元素将被置为null，其他数组元素保持原值，因此最好将方法入参数组大小定义与集合元素个数一致。
  
• 正例：

List<String> list = new ArrayList<String>(2);
list.add("guan");
list.add("bao");
String[] array = list.toArray(new String[0]);

• 说明： 使用 toArray 带参方法， 数组空间大小的 length：

• 1） 等于 0， 动态创建与 size 相同的数组， 性能最好。
• 2） 大于 0 但小于 size， 重新创建大小等于 size 的数组， 增加 GC 负担。
• 3） 等于 size， 在高并发情况下， 数组创建完成之后， size 正在变大的情况下， 负面影响与 2 相同。
• 4） 大于 size， 空间浪费， 且在 size 处插入 null 值， 存在 NPE 隐患。

• 反例：直接使用toArray无参方法存在问题，此方法返回值只能是Object[]类，若强转其他类型数组将出现ClassCastException 错误。
  

Action5、使用工具类 Arrays.asList() 把数组转换成集合时，不能使用其修改集合相关的方法，它的add/remove/clear 方法会抛出UnsupportedOperationException 异常。

• 说明：asList 的返回对象是一个 Arrays 内部类，并没有实现集合的修改方法。Arrays.asList 体现的是适配器模式，只是转换接口，后台的数据仍是数组。

String[] str = new String[] {"you","wu"};
List list = Arrays.asList(str);

• 第一种情况：list.add("yangguanbao"); 运行时异常
  
• 第二种情况：str[0] = "gujun"; 那么list.get(0) 也会随之修改。
  

Action6、泛型通配符<? extends T> 来接收返回的数据，此写法的泛型集合不能使用add 方法，而<? super T> 不能使用 get方法，作为接口调用赋值时易出错。

• 说明：扩展说一下 PECS （product extends consumer super）原则：第一、频繁往外读取内容的，适合<? extends T> 。第二、经常往里面插入的，适合用<? super T>

Action7、不要在foreach 循环里进行元素的remove/add 操作。remove元素请使用 Iterator方式，如果并发操作，需要对 Iterator 对象加锁。

• 正例

List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()) {
    String item = iterator,next();
    if (删除元素的操作) {
        iterator.remove();
    }
}

• 反例

for (String item : list) {
    if ("1".equals(item)) {
        list.remove(item);
    }
}

• 说明：以上代码的执行结果肯定会出乎大家的意料，那么试一下把“1”换成“2”，会是同样的结果吗？

• 不是，换成2，能正常遍历

Action8、在JDK7版本及以上，Comparator 实现类要满足如下三个条件，不然 Arrays.sort，Collections.sort 会报 illegalArgumentException 异常

• 说明：三个条件如下
  
• 1、x,y 的比较结果和 y,x 的比较结果相反
  
• 2、x > y, y > z, 则 x > z;
  
• 3、x =y， 则 x, z 比较结果和 y，z 比较结果相同
  
• 反例：下例中没有处理相等的情况，实际使用中可能会出现异常：

new Comparator <Student>() {
    @override
    public int compare(Student o1, Student o2) {
        return o1.getId() > o2.getId() ? 1 : -1;
    }
};

Action9、集合泛型定义时，在JDK7及以上，使用diamand 语法或全省略

• 说明：菱形泛型，即diamond，直接使用 <> 来指代前边已经指定的类型
  
• 正例：

// <> diamond 方式
HashMap<String, String> userCache = new HashMap<>(16);
// 全省略方式
ArrayList<User> = new ArrayList(10);

Action10、集合初始化时，制定集合初始化大小。

• 说明：HashMap 使用 HashMap(int initialCapacity) 初始化，如果暂时无法确定集合大小， 那么指定默认值（16）即可
• 正例：initialCapacity = (需要存储的元素个数 / 负载因子) + 1。注意负载因子(即 loader factor) 默认为 0.75，如果暂时无法确定初始值大小，请设置为16(即默认值)。
• 反例：HasMap 需要放置 1024 个元素，由于没有设置容量初始大小，随着元素增加而被迫不断扩容， resize() 方法
  总共会调用 8 次， 反复重建哈希表和数据迁移。当放置的集合元素个数达千万级时会影响程序性能。

Action11、使用 entrySet 遍历 Map 类集合 KV，而不是 keySet方式进行遍历

• 说明：keySet 其实是遍历了2次，一次是转为 Iterator 对象，另一次是从 hashMap 中取出 key 所对应的value。而 entrySet 只是遍历了一次就把 key 和value 都放到了entry 中，效率更高，如果是JDK8，使用Map.foreach 方法。
• 正例：values() 返回的是 V 值集合，是一个 list集合对象：keySet() 返回的是 K值集合，是一个Set 集合对象，entrySet() 返回的是 K-V值组合的 Set 集合。

Action12、高度注意Map类集合 K/V 能不能存储null 值的情况，如下表格

• 反例：由于HashMap的干扰，很多人认为 ConcurrentHashMap 是可以置入 null 值，而事实上，存储 null 值时会抛出npe异常。

Action13、合理利用好集合的有序性和稳定性，避免集合的无序性和不稳定性带来的负面影响。

• 说明：有序性是指遍历的结果是按某种比较规则依次排列的。稳定性指集合每次遍历的元素次序是一定的。如：ArrayList是 order/unsort; hashMap是 unordet/unsort; TreeSet 是 order/sort。

Action14、利用Set 元素唯一的特性，可以快速对一个集合进行去重操作，避免使用List的contains方法进行遍历、比对、去重操作。

Action15、判断所有集合内部的元素是否为空， 使用 isEmpty() 方法， 而不是 size() == 0 的方式。

说明： 在某些集合中， 前者的时间复杂度为 O(1)， 而且可读性更好。

正例：

Map<String, Object> map = new HashMap<>(16);
if (map.isEmpty()) {
  System.out.println("no element in this map.");
}

Action16、在使用 java.util.stream.Collectors 类的 toMap() 方法转为 Map 集合时， 一定要使用参数类型为 BinaryOperator， 参数名为 mergeFunction 的方法， 否则当出现相同 key 时会抛出 IllegalStateException 异常。

说明： 参数 mergeFunction 的作用是当出现 key 重复时， 自定义对 value 的处理策略。

正例：

List<Pair<String, Double>> pairArrayList = new ArrayList<>(3);
pairArrayList.add(new Pair<>("version", 12.10));
pairArrayList.add(new Pair<>("version", 12.19));
pairArrayList.add(new Pair<>("version", 6.28));
// 生成的 map 集合中只有一个键值对： {version=6.28}
Map<String, Double> map = pairArrayList.stream()
  .collect(Collectors.toMap(Pair::getKey, Pair::getValue, (v1, v2) -> v2));

反例：

String[] departments = new String[]{"RDC", "RDC", "KKB"};
// 抛出 IllegalStateException 异常
Map<Integer, String> map = Arrays.stream(departments)
  .collect(Collectors.toMap(String::hashCode, str -> str));

• 这个坑踩过几次

Action17、在使用 java.util.stream.Collectors 类的 toMap() 方法转为 Map 集合时， 一定要注意当 value为 null 时会抛 NPE 异常。

说明： 在 java.util.HashMap 的 merge 方法里会进行如下的判断：

if (value == null || remappingFunction == null)
  throw new NullPointerException();

反例：

List<Pair<String, Double>> pairArrayList = new ArrayList<>(2);
pairArrayList.add(new Pair<>("version1", 8.3));
pairArrayList.add(new Pair<>("version2", null));
// 抛出 NullPointerException 异常
Map<String, Double> map = pairArrayList.stream()
  .collect(Collectors.toMap(Pair::getKey, Pair::getValue, (v1, v2) -> v2));

• 踩过这个坑

Action18、使用 Map 的方法 keySet() / values() / entrySet() 返回集合对象时， 不可以对其进行添加元素操作， 否则会抛出 UnsupportedOperationException 异常。

Action19、Collections 类返回的对象， 如： emptyList() / singletonList() 等都是 immutable list， 不可对其进行添加或者删除元素的操作。

• 反例： 如果查询无结果， 返回 Collections.emptyList() 空集合对象， 调用方一旦在返回的集合中进行了添加元素的操
  作， 就会触发 UnsupportedOperationException 异常。

Action20、使用 Collection 接口任何实现类的 addAll() 方法时， 要对输入的集合参数进行 NPE 判断。

• 说明： 在 ArrayList#addAll 方法的第一行代码即 Object[] a = c.toArray()； 其中 c 为输入集合参数， 如果为 null，
  则直接抛出异常
• 踩过这个坑

Action21、在无泛型限制定义的集合赋值给泛型限制的集合时， 在使用集合元素时， 需要进行 instanceof 判断， 避免抛出 ClassCastException 异常。

说明： 毕竟泛型是在 JDK5 后才出现， 考虑到向前兼容， 编译器是允许非泛型集合与泛型集合互相赋值。

反例：

List<String> generics = null;
List notGenerics = new ArrayList(10);
notGenerics.add(new Object());
notGenerics.add(new Integer(1));
generics = notGenerics;
// 此处抛出 ClassCastException 异常
String string = generics.get(0);