集合表示一组对象，每一个对象我们都称其为元素；不同的集合有着不同的性质，比如一些集合允许重复的元素，而另一些则不允许；

集合类是为了更好地组织、管理和操作我们的数据而存在的，包括列表、集合、队列、映射等数据结构

集合跟数组一样，可以表示同样的一组元素

相同

都是容器，都能容纳一组元素

不同

数组的大小是固定的，集合的大小是可变的

数组可以存放基本数据类型，集合只能存放对象

集合根接口

ArrayList 类，祖先是Collection接口

import java.util.ArrayList;public class Main {public static void main(String[] args) {ArrayList<String> list = new ArrayList<>();list.add("789");}
}

这个接口定义了集合类的一些基本操作

public interface Collection<E> extends Iterable<E> {int size();boolean isEmpty();//查询当前集合中是否包含某个元素boolean contains(Object o);//返回当前集合的迭代器Iterator<E> iterator();//将集合转换为数组的形式Object[] toArray();//支持泛型的数据转换<T> T[] toArray(T[] a);//并不一定会添加成功boolean add(E e);//移除某个元素，移除成功返回true，不成功返回falseboolean remove(Object o);//查询当前集合是否包含给定集合中所有的元素//从数学角度来说，就是看给定集合是不是当前集合的子集boolean containsAll(Collection<?> c);//添加给定集合中所有的元素//从数学角度来说，就是将当前集合变成当前集合与给定集合的并集//添加成功返回true，否则返回falseboolean addAll(Collection<? extends E> c);//移除给定集合中出现的所有元素，如果某个元素在当前集合中不存在，那么忽略这个元素//从数学角度来说，就是求当前集合与给定集合的差集//移除成功返回true，否则falseboolean removeAll(Collection<?> c);//Java8新增方法，根据给定的Predicate条件进行元素移除操作default boolean removeIf(Predicate<? super E> filter) {Objects.requireNonNull(filter);boolean removed = false;final Iterator<E> each = iterator();   //这里用到了迭代器，我们会在后面进行介绍while (each.hasNext()) {if (filter.test(each.next())) {each.remove();removed = true;}}return removed;}//只保留当前集合中在给定集合中出现的元素，其他元素一律移除//从数学角度来说，就是求当前集合与给定集合的交集//移除成功返回true，否则falseboolean retainAll(Collection<?> c);//清空整个集合，删除所有元素void clear();//-------这些是比较以及哈希计算相关的操作----------//判断两个集合是否相等boolean equals(Object o);//计算当前整个集合对象的哈希值int hashCode();//与迭代器作用相同，但是是并行执行的，我们会在下一章多线程部分中进行介绍@Overridedefault Spliterator<E> spliterator() {return Spliterators.spliterator(this, 0);}//生成当前集合的流，我们会在后面进行讲解default Stream<E> stream() {return StreamSupport.stream(spliterator(), false);}//生成当前集合的并行流，我们会在下一章多线程部分中进行介绍default Stream<E> parallelStream() {return StreamSupport.stream(spliterator(), true);}
————————————————
版权声明：本文为CSDN博主「青空の霞光」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_25928447/article/details/127161387}

List列表（线性表）

线性表支持随机访问，相比之前的Collection接口定义，功能会更多一点，实现自List接口

底层是由数组实现的，内部维护的是一个可动态进行扩容的数组；

List是集合类型的一个分支。他的主要特性有：

1. 是一个有序的集合，插入元素是插入到尾部的，按顺序从前往后放，每个元素都有一个自己的下标位置
2. 列表中允许存在重复元素

在List接口里，定义了列表类型需要支持的全部操作，List直接继承自前面的Collection接口，很多地方重新定义了Collection接口中定义的方法，从而更加明确方法的具体功能

//List是一个有序的集合类，每个元素都有一个自己的下标位置
//List中可插入重复元素
//针对于这些特性，扩展了Collection接口中一些额外的操作
public interface List<E> extends Collection<E> {...//将给定集合中所有元素插入到当前结合的给定位置上（后面的元素就被挤到后面去了，跟我们之前顺序表的插入是一样的）boolean addAll(int index, Collection<? extends E> c);...//Java 8新增方法，可以对列表中每个元素都进行处理，并将元素替换为处理之后的结果default void replaceAll(UnaryOperator<E> operator) {Objects.requireNonNull(operator);final ListIterator<E> li = this.listIterator();  //这里同样用到了迭代器while (li.hasNext()) {li.set(operator.apply(li.next()));}}//对当前集合按照给定的规则进行排序操作，这里同样只需要一个Comparator就行了@SuppressWarnings({"unchecked", "rawtypes"})default void sort(Comparator<? super E> c) {Object[] a = this.toArray();Arrays.sort(a, (Comparator) c);ListIterator<E> i = this.listIterator();for (Object e : a) {i.next();i.set((E) e);}}...//-------- 这些是List中独特的位置直接访问操作 --------//获取对应下标位置上的元素E get(int index);//直接将对应位置上的元素替换为给定元素E set(int index, E element);//在指定位置上插入元素，就跟我们之前的顺序表插入是一样的void add(int index, E element);//移除指定位置上的元素E remove(int index);//------- 这些是List中独特的搜索操作 -------//查询某个元素在当前列表中的第一次出现的下标位置int indexOf(Object o);//查询某个元素在当前列表中的最后一次出现的下标位置int lastIndexOf(Object o);//------- 这些是List的专用迭代器 -------//迭代器我们会在下一个部分讲解ListIterator<E> listIterator();//迭代器我们会在下一个部分讲解ListIterator<E> listIterator(int index);//------- 这些是List的特殊转换 -------//返回当前集合在指定范围内的子集List<E> subList(int fromIndex, int toIndex);...
}

可以看到在List接口里，扩展了大量列表支持的操作，比如直接根据下标位置进行的增删改查操作。而在ArrayList中，底层就是采用数组实现的，跟之前顺序表的思路差不多

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{//默认的数组容量private static final int DEFAULT_CAPACITY = 10;...//存放数据的底层数组，这里的transient关键字我们会在后面I/O中介绍用途transient Object[] elementData;//记录当前数组元素数的private int size;//这是ArrayList的其中一个构造方法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);}}...public boolean add(E e) {ensureCapacityInternal(size + 1);  // 这里会判断容量是否充足，不充足需要扩容elementData[size++] = e;return true;}...//默认的列表最大长度为Integer.MAX_VALUE - 8//JVM都C++实现中，在数组的对象头中有一个_length字段，用于记录数组的长//度，所以这个8就是存了数组_length字段（这个只做了解就行）private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);   //扩容规则跟我们之前的是一样的，也是1.5倍if (newCapacity - minCapacity < 0)    //要是扩容之后的大小还没最小的大小大，那么直接扩容到最小的大小newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)   //要是扩容之后比最大的大小还大，需要进行大小限制newCapacity = hugeCapacity(minCapacity);  //调整为限制的大小elementData = Arrays.copyOf(elementData, newCapacity);   //使用copyOf快速将内容拷贝到扩容后的新数组中并设定为新的elementData底层数组}
}

如果我们要使用一个集合类，会使用接口的引用

public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("89");list.add("19");System.out.println(list);
}public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(10);   //添加Integer的值10list.remove((Integer) 10);   //注意，不能直接用10，默认情况下会认为传入的是int类型值，删除的是下标为10的元素，我们这里要删除的是刚刚传入的值为10的Integer对象System.out.println(list);   //可以看到，此时元素成功被移除
}
//集合在删除元素的时候，只会调用equals()进行判断是否为指定元素，而不是进行等号判断。所以说，如果两个对象使用equals方法相等，那么集合中就是相同的两个对象
public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(new Integer(10));   //添加的是一个对象list.remove(new Integer(10));   //删除的是另一个对象System.out.println(list);
}

ArrayList源码部分

public boolean remove(Object o) {if (o == null) {...} else {for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {   //这里只是对两个对象进行equals判断fastRemove(index);return true;  //只要判断成功，直接认为就是要删除的对象，删除就完事}}return false;
}

列表中允许存在相同元素，所以说可以添加两个一模一样的，但是使用remove()的时候，只会删除排在前面的第一个元素

public static void main(String[] args) {List<String> list = new ArrayList<>();String str = "哟唉嘛干你";list.add(str);list.add(str);System.out.println(list);
}

集合类是支持嵌套使用的，一个集合当中可以存放多个集合

public static void main(String[] args) {List<List<String>> list = new LinkedList<>();list.add(new LinkedList<>());System.out.println(list.get(0).isEmpty());
}

在Array工具类中，可以快速生成一个只读的List：

public static void main(String[] args) {List<String> list = Arrays.asList("A","B","C");System.out.println(list);
}

这个List是不能进行修改操作的，只能使用获取内容相关的方法，否则就会抛出UnsupportedOperationException异常，要生成正常使用的，可以将这个作为只读的列表作为参数传入：

public static void main(String[] args) {List<String> list = new ArrayList<>(Arrays.asList("A","B","C"));System.out.println(list);
}

也可以利用静态代码块

public static void main(String[] args) {List<String> list = new ArrayList<String>() {{   //使用匿名内部类（匿名内部类在Java8无法使用钻石运算符，但是之后的版本可以）add("A");add("B");add("C");}};System.out.println(list);
}

双向链表，同时保存两个方向

LinkedList的使用和ArrayList的使用几乎相同，各项操作的结果也是一样的，在什么使用使用ArrayList和LinkedList，我们需要结合具体的场景来决定，尽可能的扬长避短。

只不过LinkedList不仅可以当做List来使用，也可以当做双端队列使用

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{transient int size = 0;//引用首结点transient Node<E> first;//引用尾结点transient Node<E> last;//构造方法，很简单，直接创建就行了public LinkedList() {}...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;}}...
}

Queue & Deque

LInkedList除了可以直接当作列表使用之外，还可以当作其他的数据结构使用，它不仅仅实现了List接口

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable

先看看Deque的继承结构

先看看Queue接口，扩展了大量队列相关的操作

public interface Queue<E> extends Collection<E> {//队列的添加操作，是在队尾进行插入（只不过List也是一样的，默认都是尾插）//如果插入失败，会直接抛出异常boolean add(E e);//同样是添加操作，但是插入失败不会抛出异常boolean offer(E e);//移除队首元素，但是如果队列已经为空，那么会抛出异常E remove();//同样是移除队首元素，但是如果队列为空，会返回nullE poll();//仅获取队首元素，不进行出队操作，但是如果队列已经为空，那么会抛出异常E element();//同样是仅获取队首元素，但是如果队列为空，会返回nullE peek();
}

我们可以直接将LinkedList当做一个队列来使用

public static void main(String[] args) {Queue<String> queue = new LinkedList<>();   //当做队列使用，还是很方便的queue.offer("AAA");queue.offer("BBB");System.out.println(queue.poll());System.out.println(queue.poll());
}

双端队列

普通队列中，从队尾入队，队首出队；然而双端队列允许在队列的两端进行入队和出队操作；利用这种特性，双端队列既可以当作普通队列进行使用，也可以当作栈来使用

Java中的定义

//在双端队列中，所有的操作都有分别对应队首和队尾的
public interface Deque<E> extends Queue<E> {//在队首进行插入操作void addFirst(E e);//在队尾进行插入操作void addLast(E e);//不用多说了吧？boolean offerFirst(E e);boolean offerLast(E e);//在队首进行移除操作E removeFirst();//在队尾进行移除操作E removeLast();//不用多说了吧？E pollFirst();E pollLast();//获取队首元素E getFirst();//获取队尾元素E getLast();//不用多说了吧？E peekFirst();E peekLast();//从队列中删除第一个出现的指定元素boolean removeFirstOccurrence(Object o);//从队列中删除最后一个出现的指定元素boolean removeLastOccurrence(Object o);// *** 队列中继承下来的方法操作是一样的，这里就不列出了 ***...// *** 栈相关操作已经帮助我们定义好了 ***//将元素推向栈顶void push(E e);//将元素从栈顶出栈E pop();// *** 集合类中继承的方法这里也不多种介绍了 ***...//生成反向迭代器，这个迭代器也是单向的，但是是next方法是从后往前进行遍历的Iterator<E> descendingIterator();}

比如我们可以直接当作栈来使用

public static void main(String[] args) {Deque<String> deque = new LinkedList<>();deque.push("AAA");deque.push("BBB");System.out.println(deque.pop());System.out.println(deque.pop());
}

再来测试一下反向迭代器和正向迭代器：

public static void main(String[] args) {Deque<String> deque = new LinkedList<>();deque.addLast("AAA");deque.addLast("BBB");Iterator<String< descendingIterator = deque.descendingIterator();System.out.println(descendingIterator.next());Iterator<String> iterator = deque.iterator();System.out.println(iterator.next());
}

除了LinkedList实现了队列接口以外，还有其他但是不常用的实现类，做了解就行

public static void main(String[] args) {Deque<String> deque = new ArrayDeque<>();   //数组实现的栈和队列Queue<String> queue = new PriorityQueue<>();  //优先级队列
}

优先级队列

public static void main(String[] args) {Queue<Integer> queue = new PriorityQueue<>();queue.offer(10);queue.offer(4);queue.offer(5);System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());
}

只不过需要注意的是，优先级队列并不是队列中所有的元素都是按照优先级排放的，优先级队列只能保证出队顺序是按照优先级进行的，我们可以打印一下：

我们可以自定义比较，需要一个Comparator的实现：

public static void main(String[] args) {Queue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);   //按照从大到小顺序出队queue.offer(10);queue.offer(4);queue.offer(5);System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());
}

Set集合

先看定义，会发现接口中的定义方法都是Collection中直接继承的，因此，Set支持的功能其实也就和Collection中定义的差不多，除：

• 不允许出现重复元素
• 不支持随机访问

public interface Set<E> extends Collection<E> {// Set集合中基本都是从Collection直接继承过来的方法，只不过对这些方法有更加特殊的定义int size();boolean isEmpty();boolean contains(Object o);Iterator<E> iterator();Object[] toArray();<T> T[] toArray(T[] a);//添加元素只有在当前Set集合中不存在此元素时才会成功，如果插入重复元素，那么会失败boolean add(E e);//这个同样是删除指定元素boolean remove(Object o);boolean containsAll(Collection<?> c);//同样是只能插入那些不重复的元素boolean addAll(Collection<? extends E> c);boolean retainAll(Collection<?> c);boolean removeAll(Collection<?> c);void clear();boolean equals(Object o);int hashCode();//这个方法我们同样会放到多线程中进行介绍@Overridedefault Spliterator<E> spliterator() {return Spliterators.spliterator(this, Spliterator.DISTINCT);}
}

HashSet

源码

先认识下HashSet，先看底层

public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable
{private transient HashMap<E,Object> map;   //对，你没看错，底层直接用map来做事// 因为Set只需要存储Key就行了，所以说这个对象当做每一个键值对的共享Valueprivate static final Object PRESENT = new Object();//直接构造一个默认大小为16负载因子0.75的HashMappublic HashSet() {map = new HashMap<>();}...//你会发现所有的方法全是替身攻击public Iterator<E> iterator() {return map.keySet().iterator();}public int size() {return map.size();}public boolean isEmpty() {return map.isEmpty();}
}

通过观察可以发现，HashSet几乎都在操作内部维护一个HashMap，也就是说HashSet只是一个表壳，而内部的灵魂在于HashMap；所以说，HashSet利用了HashMap内部的数据结构，轻松实现Set定义的全部功能

应用

由于底层是采用哈希表实现的，可以非常高效的从HashSet当中存取元素

public static void main(String[] args) {Set<String> set = new HashSet<>();System.out.println(set.add("AAA"));   //这里我们连续插入两个同样的字符串System.out.println(set.add("AAA"));System.out.println(set);   //可以看到，最后实际上只有一个成功插入了
}

在set接口中并没有定义支持指定下标位置访问的添加和删除操作，只能简单的删除对象

public static void main(String[] args) {Set<String> set = new HashSet<>();System.out.println(set.add("AAA"));System.out.println(set.remove("AAA"));System.out.println(set);
}

由于底层采用哈希表实现，所以说无法维持插入元素的顺序

public static void main(String[] args) {Set<String> set = new HashSet<>();set.addAll(Arrays.asList("A","0","-","+"));System,out.println(set);
}

想要使用维持顺序的Set集合，可以使用LinkedHashSet，它底层维护的不再是一个HashMap。而是LinkedHashMap，它能够在插入数据的时候里用链表自动维护顺序，这样能保证插入顺序和最后的迭代顺序一致

public static void main(String[] args) {Set<String> set = new LinkedHashSet<>();set.addAll(Arrays.asList("A", "0", "-", "+"));System.out.println(set);
}

TreeSet

源码

看TreeSet的源码也可以知道，实际上我们用的是TreeMap

public class TreeSet<E> extends AbstractSet<E>implements NavigableSet<E>, Cloneable, java.io.Serializable
{//底层需要一个NavigableMap，就是自动排序的Mapprivate transient NavigableMap<E,Object> m;//不用我说了吧private static final Object PRESENT = new Object();...//直接使用TreeMap解决问题public TreeSet() {this(new TreeMap<E,Object>());}...
}

他会在插入元素的时候就进行排序

public static void main(String[] args) {TreeSet<Integer> set = new TreeSet<>();set.add(1);set.add(3);set.add(2);System.out.println(set);
}

最后得到的结果并不是我们插入顺序，而是按照数字的大小进行排列。当然，我们也可以自定义排序规则：

public static void main(String[] args) {TreeSet<Integer> set = new TreeSet<>((a, b) -> b - a);  //同样是一个Comparatorset.add(1);set.add(3);set.add(2);System.out.println(set);
}

Map映射

映射指两个元素的之间相互“对应”的关系，也就是说，我们的元素之间是两两对应的，是以键值对的形式存在

而Map就是为了实现这种数据结构而存在的，我们通过保存键值对的形式来存储映射关系，就可以轻松地通过键找到对应的映射值，比如现在我们要保存很多学生的信息，而这些学生都有自己的ID，我们可以将其以映射的形式保存，将ID作为键，学生详细信息作为值，这样我们就可以通过学生的ID快速找到对应学生的信息了

在Map中，这些映射关系被存储为键值对，先看定义操作

//Map并不是Collection体系下的接口，而是单独的一个体系，因为操作特殊
//这里需要填写两个泛型参数，其中K就是键的类型，V就是值的类型，比如上面的学生信息，ID一般是int，那么键就是Integer类型的，而值就是学生信息，所以说值是学生对象类型的
public interface Map<K,V> {//-------- 查询相关操作 --------//获取当前存储的键值对数量int size();//是否为空boolean isEmpty();//查看Map中是否包含指定的键boolean containsKey(Object key);//查看Map中是否包含指定的值boolean containsValue(Object value);//通过给定的键，返回其映射的值V get(Object key);//-------- 修改相关操作 --------//向Map中添加新的映射关系，也就是新的键值对V put(K key, V value);//根据给定的键，移除其映射关系，也就是移除对应的键值对V remove(Object key);//-------- 批量操作 --------//将另一个Map中的所有键值对添加到当前Map中void putAll(Map<? extends K, ? extends V> m);//清空整个Mapvoid clear();//-------- 其他视图操作 --------//返回Map中存放的所有键，以Set形式返回Set<K> keySet();//返回Map中存放的所有值Collection<V> values();//返回所有的键值对，这里用的是内部类Entry在表示Set<Map.Entry<K, V>> entrySet();//这个是内部接口Entry，表示一个键值对interface Entry<K,V> {//获取键值对的键K getKey();//获取键值对的值V getValue();//修改键值对的值V setValue(V value);//判断两个键值对是否相等boolean equals(Object o);//返回当前键值对的哈希值int hashCode();...}...
}

先尝试使用最常见的HashMap

public static void main(String[] args) {Map<Integer, String> map = new HashMap<>();map.put(1, "小明");   //使用put方法添加键值对，返回值我们会在后面讨论map.put(2, "小红");System.out.println(map.get(2)); //使用get方法根据键获取对应的值
}

注意，Map中无法添加相同的键，同样的键只能存在一个，即使值不同。如果出现键相同的情况，那么会覆盖掉之前的

public static void main(String[] args) {Map<Integer, String> map = new HashMap<>();map.put(1, "小明");map.put(1, "小红");   //这里的键跟之前的是一样的，这样会导致将之前的键值对覆盖掉System.out.println(map.get(1));
}

为了防止意外将之前的键值对覆盖掉，我们可以使用：

public static void main(String[] args) {Map<Integer, String> map = new HashMap<>();map.put(1, "小明");map.putIfAbsent(1, "小红");   //Java8新增操作，只有在不存在相同键的键值对时才会存放System.out.println(map.get(1));
}

我们在获取一个不存在的映射时，默认会返回null作为结果：

public static void main(String[] args) {Map<Integer, String> map = new HashMap<>();map.put(1, "小明");   //Map中只有键为1的映射System.out.println(map.get(3));  //此时获取键为3的值，那肯定是没有的，所以说返回null
}

我们也可以为这个情况添加一个预备方案，当Map中不存在，可以返回一个备选的返回值：

public static void main(String[] args) {Map<Integer, String> map = new HashMap<>();map.put(1,"xiao");System.out.println(map.getOrDefault(3,"nothing"));
}

因为HashMap底层采用哈希表实现，所以不维护顺序，我们在获取所有键和所有值时，可能是乱序的：

public static void main(String[] args) {Map<String, String> map = new HashMap<>();map.put("0", "zero");map.put("+","one");map.put("1","plus");System.out.println(map);System.out.println(map.keySet());System.out.println(map.values());
}

输出

{0=zero, 1=plus, +=one}
[0, 1, +]
[zero, plus, one]

如果要维护顺序，我们同样可以使用LinkedHashMap，它的内部对插入顺序进行了维护：

public static void main(String[] args) {Map<String, String> map = new LinkedHashMap<>();map.put("0", "zero");map.put("+","one");map.put("1","plus");System.out.println(map);System.out.println(map.keySet());System.out.println(map.values());
}

输出

{0=zero, +=one, 1=plus}
[0, +, 1]
[zero, one, plus]

Map的底层实现

HashMap

底层采用哈希表，结合之前说过的可能会出现哈希冲突，保存的元素就会出现限制，因此我们可以采用链地址法来解决

实际上这个表就是一个存放头结点的数组+若干结点，而HashMap也是这样的，先看定义

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {...static class Node<K,V> implements Map.Entry<K,V> {   //内部使用结点，实际上就是存放的映射关系final int hash;final K key;   //跟我们之前不一样，我们之前一个结点只有键，而这里的结点既存放键也存放值，当然计算哈希还是使用键V value;Node<K,V> next;...}...transient Node<K,V>[] table;   //这个就是哈希表本体了，可以看到跟我们之前的写法是一样的，也是头结点数组，只不过HashMap中没有设计头结点（相当于没有头结点的链表）final float loadFactor;   //负载因子，这个东西决定了HashMap的扩容效果public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; //当我们创建对象时，会使用默认的负载因子，值为0.75}...     
}

可以看到，实际上底层大致结构跟我们之前学习的差不多，只不过多了一些特殊的东西：

• HashMap支持自动扩容，哈希表的大小并不是一直不变的，否则太过死板
• HashMap并不是只使用简单的链地址法，当链表长度到达一定限制时，会转变为效率更高的红黑树结构

研究一下他的put方法

public V put(K key, V value) {//这里计算完键的哈希值之后，调用的另一个方法进行映射关系存放return putVal(hash(key), key, value, false, true);
}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)  //如果底层哈希表没初始化，先初始化n = (tab = resize()).length;   //通过resize方法初始化底层哈希表，初始容量为16，后续会根据情况扩容，底层哈希表的长度永远是2的n次方//因为传入的哈希值可能会很大，这里同样是进行取余操作//(n - 1) & hash 等价于 hash % n 这里的i就是最终得到的下标位置了if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);   //如果这个位置上什么都没有，那就直接放一个新的结点else {   //这种情况就是哈希冲突了Node<K,V> e; K k;if (p.hash == hash &&   //如果上来第一个结点的键的哈希值跟当前插入的键的哈希值相同，键也相同，说明已经存放了相同键的键值对了，那就执行覆盖操作((k = p.key) == key || (key != null && key.equals(k))))e = p;   //这里直接将待插入结点等于原本冲突的结点，一会直接覆盖else if (p instanceof TreeNode)   //如果第一个结点是TreeNode类型的，说明这个链表已经升级为红黑树了e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  //在红黑树中插入新的结点else {for (int binCount = 0; ; ++binCount) {  //普通链表就直接在链表尾部插入if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);  //找到尾部，直接创建新的结点连在后面if (binCount >= TREEIFY_THRESHOLD - 1) //如果当前链表的长度已经很长了，达到了阈值treeifyBin(tab, hash);			//那么就转换为红黑树来存放break;   //直接结束}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))  //同样的，如果在向下找的过程中发现已经存在相同键的键值对了，直接结束，让p等于e一会覆盖就行了break;p = e;}}if (e != null) { // 如果e不为空，只有可能是前面出现了相同键的情况，其他情况e都是null，所有直接覆盖就行V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;   //覆盖之后，会返回原本的被覆盖值}}++modCount;if (++size > threshold)   //键值对size计数自增，如果超过阈值，会对底层哈希表数组进行扩容resize();   //调用resize进行扩容afterNodeInsertion(evict);return null;  //正常插入键值对返回值为null
}

根据上面的推导，我们在正常插入一个键值对时，会得到null返回值，而冲突时会得到一个被覆盖的值

public static void main(String[] args) {Map<String, String> map = new HashMap<>();System.out.println(map.put("0","zero"));System.out.println(map.put("0","one"));
}

输出

null
zero

当HashMap的一个链表长度过长的时候，会自动转换成红黑树

但是这样治标不治本，受限制的始终时底层哈希表的长度，还需要进一步对这个底层的哈希表进行扩容才能够，所以有了resize()方法

static final int MAXIMUM_CAPACITY = 1 << 30;final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;   //先把下面这几个旧的东西保存一下int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold; //The next size value at which to resizeint newCap, newThr = 0;  //这些是新的容量和扩容阈值if (oldCap > 0) {  //如果旧容量大于0，那么就开始扩容if (oldCap >= MAXIMUM_CAPACITY) {  //如果旧的容量已经大于最大限制了，那么直接给到 Integer.MAX_VALUEthreshold = Integer.MAX_VALUE;return oldTab;  //这种情况不用扩了}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)   //新的容量等于旧容量的2倍，同样不能超过最大值newThr = oldThr << 1; //新的阈值也提升到原来的两倍}else if (oldThr > 0) // 旧容量不大于0只可能是还没初始化，这个时候如果阈值大于0，直接将新的容量变成旧的阈值newCap = oldThr;else {               // 默认情况下阈值也是0，也就是我们刚刚无参new出来的时候newCap = DEFAULT_INITIAL_CAPACITY;   //新的容量直接等于默认容量16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //阈值为负载因子乘以默认容量，负载因子默认为0.75，也就是说只要整个哈希表用了75%的容量，那么就进行扩容，至于为什么默认是0.75，原因很多，这里就不解释了，反正作为新手，这些都是大佬写出来的，我们用就完事。}...threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;   //将底层数组变成新的扩容之后的数组if (oldTab != null) {  //如果旧的数组不为空，那么还需要将旧的数组中所有元素全部搬到新的里面去...   //详细过程就不介绍了}
}

LinkedHashMap

是直接继承自HashMap，具有HashMap的全部性质，同时得益于每一个结点都是一个双向链表，在插入键值对的同时保存了插入顺序

LinkedHashMap中的结点实现

static class Entry<K,V> extends HashMap.Node<K,V> {  Entry<K,V> before, after;   //这里多了一个指向前一个结点和后一个结点的引用Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}
}

这样我们在遍历LinkedHashMap的时候，顺序就同我们的插入顺序一致，当然也可以使用访问顺序，也就是刚刚被访问过的元素，会被排到最后一位

TreeMap

它的内部直接维护一个红黑树，没有使用哈希表，因为他会将我们插入的结点按规则进行排序，所以说直接采用红黑树会更好，我们在创建时，直接给予一个比较规则即可，跟之前的TreeSet是一样的

public static void main(String[] args) {Map<Integer , String> map = new TreeMap<>((a, b) -> b - a);map.put(0, "单走");map.put(1, "一个六");map.put(3, "**");System.out.println(map);
}

输出

{3=**, 1=一个六, 0=单走}

Map’s method

compute()

compute会将指定的Key的值进行重新计算，如果Key不存在，v会返回null

computeIfPresent()当Key存在时则计算并赋予新的值

public static void main(String[] args) {Map<Integer, String> map = new HashMap<>();map.put(1, "A");map.put(2, "B");map.compute(1, (k, v)-> {return v + "M";}) ;map.computeIfPresent(1, (k, v) -> {return v + "M";});System.out.println(map);
}

输出

{1=AMM, 2=B}

也可以使用computeIfAbsent()，当不存在Key时，计算并将键值对放入Map中：

public static void main(String[] args) {map.put(1, "A");map.put(2, "B");map.computeIfAbsent(0, (k)-> {return "M";});System.out.println(map);
}

输出

{0=M, 1=A, 2=B}

merge()

public static void main(String[] args) {List<Student> students = Arrays.asList(new Student("yoni", "English", 80),new Student("yoni", "Chinese", 98),new Student("yoni", "Math", 95),new Student("taohai.wang", "English", 50),new Student("taohai.wang", "Chinese", 72),new Student("taohai.wang", "Math", 41),new Student("Seely", "English", 88),new Student("Seely", "Chinese", 89),new Student("Seely", "Math", 92));Map<String, Integer> scoreMap = new HashMap<>();//merge方法可以对重复键的值进行特殊操作，比如我们想计算某个学生的所有科目分数之后，那么就可以像这样：students.forEach(student -> scoreMap.merge(student.getName(), student.getScore(), Integer::sum));scoreMap.forEach((k, v) -> System.out.println("key:" + k + "总分" + "value:" + v));
}static class Student {private final String name;private final String type;private final int score;public Student(String name, String type, int score) {this.name = name;this.type = type;this.score = score;}public String getName() {return name;}public int getScore() {return score;}public String getType() {return type;}
}

输出

key:Seely总分value:269
key:taohai.wang总分value:163
key:yoni总分value:273

replace()

可以快速替换某个映射的值

public static void main(String[] args) {Map<Integer, String> map = new HashMap<>();map.put(0, "zero");map.replace(0, ">>>");System.out.println(map);
}

也可以精准匹配

public static void main(String[] args) {Map<Integer, String> map = new HashMap<>();map.put(0,"zero");map.replace(0,"maka","baka"); //map.replace(key,oldValue,newValue);System.out.println(map);
}

输出

{0=zero}

remove()

使用方法跟replace差不多，也支持键同时匹配

public static void main(String[] args) {Map<Integer , String> map = new HashMap<>();map.put(0, "单走");map.remove(0, "单走");  //只有同时匹配时才移除System.out.println(map);
}

Stream流

Java 8 API 新增了一个新的抽象流Stream，可以让我们以一种声明的方式处理数据

Stream使用一种类似于SQL语句从数据库查询数据的直观方式来提供一种对Java集合运算和表达的高阶抽象。

Stream API 可以极大提高Java程序员的生产力。这种处理方法将要处理的元素集合看作一种流，流在管道中运输，并且可以在管道的节点上进行处理，比如筛选、排序、聚合等。元素流在管道中经过中间操作 (intermediate operation) 的处理，最后由最终操作（terminal operation）得到前面处理的结果

我们可以把一个Stream当作流水线处理：

public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("A");list.add("B");list.add("C");//the first method :remove "B"Iterator<String> iterator = list.iterator();while(iterator.hasNext()) {if(iterator.next().equals("B")) {iterator.remove();   }}//the second method: Stream 操作list = list //链式调用.stream() //获取流.filter(e -> !e.equals("B")) //只允许不是B的通过.collect(Collectors.toList()); //重新收集通过流水线的元素，变回listSystem.out.println(list);	
}

输出

[A, C]

再来一例

public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(3);list = list.stream().distinct()   //去重（使用equals判断）.sorted((a, b) -> b - a)    //进行倒序排列.map(e -> e+1)    //每个元素都要执行+1操作.limit(2)    //只放行前两个元素.collect(Collectors.toList());System.out.println(list);
}

输出

[4, 3]

当遇到大量的复杂操作的时候，我们可以使用Stream来快速编写代码，逻辑更加明了

注意：不能认为每一步都是直接依次执行的

实际上Stream会先记录每一步操作，而不是直接开始执行内容，当整个链式调用完成时，才会依次进行，也就是需要的时候，工厂的及其才会按照预定的流程启动

接下来，用一堆随机数来进行更多流操作的演示

public static void main(String[] args) {Random random = new Random();random.ints(-100, 100).limit(10);.filter(i -> i< 0).sorted().forEach(System.out::println);
}

我们可以生成一个统计实例来帮助我们快速进行统计：

public static void main(String[] args) {Random random = new Random();IntSummaryStatistics statistics = random.ints(0, 100).limit(100).summaryStatistics();System.out.println(statistics.getMax());System.out.println(statistics.getCount());System.out.println(statistics.getAverage());
}

输出

99
100
51.38

普通的List只需要一个method，就可以直接转换到方便好用的IntStream：

public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(1);list.add(2);list.add(3);list.add(4);list.stream().mapToInt(i -> i).summaryStatistics();
}

我们还可以通过使用flat来对整个流进行一个细分：

public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("A,B");list.add("C,D");list.add("E,F");//让每一个元素通过，进行分割，变成独立的6个元素list = list.stream().flatMap(e -> Arrays.stream(e.split(","))) //分割字符串并生成新的流.collect(Collectors.toList()); //汇成新的listSystem.out.println(list); //得到结果
}

输出

[A, B, C, D, E, F]

我们也可以只通过Stream来完成所有数字的和，使用reduce方法：

public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);int sum = list.stream().reduce((a, b) -> a + b)   //计算规则为：a是上一次计算的值，b是当前要计算的参数，这里是求和.get();    //我们发现得到的是一个Optional类实例，通过get方法返回得到的值System.out.println(sum);
}

Collections工具类

JDK为我们准备的Collections类，就是专门用于集合的工具类

public static void main(String[] args) {List<Integer> list = new ArrayList<>();Collections.max(list);Collections.min(list);
}

同样的，我们可以对集合进行二分搜索

注意：集合的类型必须是实现Comparable接口的类：

public static void main(String[] args) {List<Integer> list = Arrays.asList(2, 3, 8, 9, 10, 13);System.out.println(Collections.binarySearch(list,8));
}

我们也可以对集合的元素进行快速填充，但是，此填充是对集合中的已有元素进行覆盖：

也就是说，如果集合中本身没有元素，那么fill操作不会生效

public static void main(String[] args) {List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));Collections.fill(list, 6);System.out.println(list);
}

输出

[6, 6, 6, 6, 6]

有时候我们可能需要生成一个空的集合类返回，那么我们可以使用emptyList()来快速生成一个only read的空集合

public static void main(String[] args) {List<Integer> list = Collections.emptyList();//Collections.singletonList() 会生成一个只有一个元素的Listlist.add(10);   //不支持，会直接抛出异常
}

我们也可以寻找子集合的位置：

public static void main(String[] args) {List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));System.out.println(Collections.indexOfSubList(list, Arrays.asList(4, 5)));
}

输出

3

得益于泛型的类型擦除机制，实际上最终只要是Object的实现类，都可以保存到集合类中，那么就会出现这种情况

public static void main(String[] args) {//使用原始类型接收一个Integer类型的ArrayListList list = new ArrayList<>(Arrays.asList(1,2,3,4,5));list.add("aaa");   //我们惊奇地发现，这玩意居然能存字符串进去System.out.println(list);
}

输出

[1, 2, 3, 4, 5, aaa]

由于泛型机制的一些漏洞，实际上对应类型的集合类有可能会存放其它类型的值，泛型的类型检查只存在于编译阶段，只要绕过这个阶段，在实际运行时，不会进行类型检查；

checkedList()，可以将给定集合类进行包装，在运行时进行类型检查，如果add的不是当前类型集合支持的类型，就会抛出类型转换异常

public static void main(String[] args) {List list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));list = Collections.checkedList(list, Integer.class); //表示Integer这个类型list.add("aaa");System.out.println(list);
}

输出