Java容器 - 图1

Collection

List

  1. ArrayList

    1. add()             //将元素插入到指定位置的 arraylist 中
    2. addAll()         //添加集合中的所有元素到 arraylist 中
    3. clear()             //删除 arraylist 中的所有元素
    4. contains()         //判断元素是否在 arraylist
    5. get()             //通过索引值获取 arraylist 中的元素
    6. indexOf()         //返回 arraylist 中元素的索引值
    7. removeAll()         //删除存在于指定集合中的 arraylist 里的所有元素
    8. remove()         //删除 arraylist 里的单个元素
    9. size()             //返回 arraylist 里元素数量
    10. isEmpty()         //判断 arraylist 是否为空
    11. subList()         //截取部分 arraylist 的元素
    12. sort()             //对 arraylist 元素进行排序
    13. toArray()         //将 arraylist 转换为数组
    14. toString()         //将 arraylist 转换为字符串
    15. lastIndexOf()     //返回指定元素在 arraylist 中最后一次出现的位置
    16. containsAll()     //查看 arraylist 是否包含指定集合中的所有元素

  2. LinkedList

add 和 offer ：offer返回boolean值
peek
poll
offer

  1. public boolean add(E e)    //链表末尾添加元素，返回是否成功，成功为 true，失败为 false。
  2. public void add(int index, E element)    //向指定位置插入元素。
  3. public void addFirst(E e)    //元素添加到头部。
  4. public void addLast(E e)    //元素添加到尾部。
  5. public boolean offer(E e)    //向链表末尾添加元素，返回是否成功，成功为 true，失败为 false。
  6. public boolean offerFirst(E e)    //头部插入元素，返回是否成功，成功为 true，失败为 false。
  7. public boolean offerLast(E e)    //尾部插入元素，返回是否成功，成功为 true，失败为 false。
  8. public void clear()    //清空链表。
  9. public E removeFirst()    //删除并返回第一个元素。
  10. public E removeLast()    //删除并返回最后一个元素。
  11. public boolean remove(Object o)    //删除某一元素，返回是否成功，成功为 true，失败为 false。
  12. public E remove(int index)    //删除指定位置的元素。
  13. public E poll()    //删除并返回第一个元素。
  14. public E remove()    //删除并返回第一个元素。
  15. public boolean contains(Object o)    //判断是否含有某一元素。
  16. public E get(int index)    //返回指定位置的元素。
  17. public E peek()    //返回第一个元素。
  18. public E peekFirst()    //返回头部元素。
  19. public E peekLast()    //返回尾部元素。
  20. public int size()    //返回链表元素个数。
  21. public Object[] toArray()    //返回一个由链表元素组成的数组。
  22. public T[] toArray(T[] a)    //返回一个由链表元素转换类型而成的数组。

比较ArrayList和LinkedList

  1. 线程安全：都不安全，Vector保证线程安全
  2. 底层数据结构：数组 vs 双向链表
  3. 插入和删除是否受位置影响：受 vs 头尾不受，其他位置受
  4. 快速随机访问：支持 vs 不支持
  5. 内存：val vs val和指针

Set

  1. HashSet

    1. add();
    2. remove();
    3. clear();
    4. contains();
    5. size();
    6. isEmpty();

    HashSet、LinkedHashSet 和 TreeSet 三者的异同:

    1. 线程安全：都不保证
    2. 底层实现：HashSet是HashMap，LinkedHashSet是
    3. 应用场景

Queue

Queue 接口 抛出异常 返回特殊值
插入队尾 add(E e) offer(E e)
删除队首 remove() poll()
查询队首元素 element() peek()
Deque 接口 抛出异常 返回特殊值
插入队首 addFirst(E e) offerFirst(E e)
插入队尾 addLast(E e) offerLast(E e)
删除队首 removeFirst() pollFirst()
删除队尾 removeLast() pollLast()
查询队首元素 getFirst() peekFirst()
查询队尾元素 getLast() peekLast()

ArrayDeque 与 LinkedList

  1. 底层数据结构：可变长数组＋双指针 vs 链表
  2. 存储null数据：不支持 vs 支持
  3. 从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈

PriorityQueue
典型例题包括堆排序、求第K大的数、带权图的遍历

Map

HashMap

hashmap.replace(key, newValue);
hashmap.get(key);
hash.getOrDefault(key, default);

  1. clear()    //删除 hashMap 中的所有键/值对
  2. clone()    //复制一份 hashMap
  3. isEmpty()    //判断 hashMap 是否为空
  4. size()    //计算 hashMap 中键/值对的数量
  5. put()    //将键/值对添加到 hashMap 中
  6. remove()    //删除 hashMap 中指定键 key 的映射关系
  7. containsKey()    //检查 hashMap 中是否存在指定的 key 对应的映射关系。
  8. containsValue()    //检查 hashMap 中是否存在指定的 value 对应的映射关系。
  9. replace()    //替换 hashMap 中是指定的 key 对应的 value。
  10. replaceAll()    //将 hashMap 中的所有映射关系替换成给定的函数所执行的结果。
  11. get()    //获取指定 key 对应对 value
  12. getOrDefault()    //获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值
  13. forEach()    //对 hashMap 中的每个映射执行指定的操作。
  14. entrySet()    //返回 hashMap 中所有映射项的集合集合视图。
  15. keySet()    //返回 hashMap 中所有 key 组成的集合视图。
  16. values()    //返回 hashMap 中存在的所有 value 值。

底层实现
jdk1.8之后 数组+链表＋红黑树
当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
Java容器 - 图2

TreeMap

TreeMap它还实现了NavigableMap接口和SortedMap 接口

  1. NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力

  2. SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力 默认按照key的升序排序 ```java public class Person { private Integer age;

    public Person(Integer age) { this.age = age; }

    public Integer getAge() { return age; }

  1. public static void main(String[] args) {
  2.     TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
  3.         @Override
  4.         public int compare(Person person1, Person person2) {
  5.             int num = person1.getAge() - person2.getAge();
  6.             return Integer.compare(num, 0);
  7.         }
  8.     });
  9.     treeMap.put(new Person(3), "person1");
  10.     treeMap.put(new Person(18), "person2");
  11.     treeMap.put(new Person(35), "person3");
  12.     treeMap.put(new Person(16), "person4");
  13.     treeMap.entrySet().stream().forEach(personStringEntry -> {
  14.         System.out.println(personStringEntry.getValue());
  15.     });
  16. }

}

  2. <a name="jSRUE"></a>
  3. ### ConcurrentHashMap
  5. jdk1.7![](https://cdn.nlark.com/yuque/0/2022/jpeg/26312519/1649903914810-7a7169a9-21b2-4af4-b439-873c4b7305e4.jpeg#clientId=ua3aa21b3-f0d3-4&crop=0&crop=0&crop=1&crop=1&from=paste&id=u7dfbb9d5&margin=%5Bobject%20Object%5D&originHeight=944&originWidth=1798&originalType=url&ratio=1&rotation=0&showTitle=false&status=done&style=none&taskId=ueac9bab5-e68f-46e5-89e4-797037c415c&title=)<br />ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。<br />Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。
  7. jdk1.8![](https://cdn.nlark.com/yuque/0/2022/png/26312519/1649903927325-7b482c6b-93af-4275-a7d0-a0466206ff45.png#clientId=ua3aa21b3-f0d3-4&crop=0&crop=0&crop=1&crop=1&from=paste&id=ub6269129&margin=%5Bobject%20Object%5D&originHeight=454&originWidth=1024&originalType=url&ratio=1&rotation=0&showTitle=false&status=done&style=none&taskId=ub746c8e2-9f94-493d-aacb-3f7291719a5&title=)<br />ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。
  10. <a name="t7o0Z"></a>
  11. ## Collections工具类
  12. ```java
  13. void reverse(List list)//反转
  14. void shuffle(List list)//随机排序
  15. void sort(List list)//按自然排序的升序排序
  16. void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
  17. void swap(List list, int i , int j)//交换两个索引位置的元素
  18. void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面
  1. int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
  2. int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
  3. int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
  4. void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
  5. int frequency(Collection c, Object o)//统计元素出现次数
  6. int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)
  7. boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素