Java 中提供的一种容器，长度可变，存储的是对象。
类集是 Java 数据结构的实现

链表

链表是离散存储线性结构 n 个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。

  • 优点：空间没有限制，插入删除很快
  • 缺点，存储数据很慢
  1. class Node{
  2.     Object data;
  3.     Node next;
  4. }

二叉树

  1. class Node{
  2.     Object data;
  3.     Node left, right;
  4. }

红黑树

栈

先进后出

队列

先进先出

Collection 接口

在整个 Java 类集中保存单值的最大操作父接口
常用子接口 List（允许重复）， Set（不允许重复）

List 接口

public interface List extends Collection 子接口的定义
实现类

ArrayList(动态数组),

  1. ArrayList<String> data = new ArrayList<>();
  2.         data.add("Hello  ");//返回 true
  3.         data.add(1, "cnmcnm"); //List 接口单独定义的
  4.         data.add("World");
  5.         data.remove(1);//根据索引删除内容
  6.         data.remove("World");//删除指定对象
  7.         System.out.println(data);//长度是任意长
  8.         for(int i=0; i<data.size(); i++){
  9.             System.out.print(data.get(i)+", ");
  10.         }

通过无参构造方法

LinkedList(链表)

双向链表实现，增加删除更快，查找慢（与 ArrayList 相反）

vector

同步的

  1. public static void main(String[] args) {
  2.         //Vector：
  3.         Vector<String> data = new Vector<>();
  4.         data.add("Hello  ");//返回 true
  5.         data.add(1, "cnmcnm"); //List 接口单独定义的
  6.         data.add("World");
  7.         data.remove(1);//根据索引删除内容
  8.         data.remove("World");//删除指定对象
  9.         System.out.println(data);//长度是任意长
  10.         for(int i=0; i<data.size(); i++){
  11.             System.out.print(data.get(i)+", ");
  12.         }
  13.     }

ListIterator 和 Iterator

Iterator 属于迭代输出，基本的操作原理：是不断的判断是否有下一个元素，有的话，则直接输出。

  1. public static void main(String[] args) {
  2.         //由前向后的单向输出
  3.         ArrayList<Integer> data = new ArrayList<>();
  4.         data.add(1);
  5.         data.add(2);
  6.         data.add(3);
  7.         data.add(4);
  8.         data.add(5);
  9.         Iterator<Integer> iterator = data.iterator();
  10.         while(iterator.hasNext()){//判断下一个数据是否有
  11.             //在迭代的时候不能进行集合中的remove方法，要用迭代器的remove方法
  12.             System.out.print(iterator.next()+", ");//取出数据
  13.         }
  14.         iterator.remove();//删除指针所指的当前内容
  15.         System.out.println("\n"+data.size());
  16.     }
  1. public static void main(String[] args) {
  2.         //由前向后的单向输出
  3.         ArrayList<Integer> data = new ArrayList<>();
  4.         data.add(1);
  5.         data.add(2);
  6.         data.add(3);
  7.         data.add(4);
  8.         data.add(5);
  9.         ListIterator<Integer> iterator = data.listIterator();
  10.         iterator.add(100);//该元素紧接在next()返回的元素之前插入
  11.         iterator.next();
  12.         iterator.next();
  13.         iterator.set( 20000);
  14.         iterator.previous();
  15.         iterator.previous();
  16.         iterator.previous();
  17.         while(iterator.hasNext()){
  18.             System.out.println(iterator.next());
  19.         }
  20.     }

增强 for

用于迭代数组 或 集合（Collection下的集合）

set 集合

不包含重复元素的集合。

  • 注意：如果将可变对象用作set元素，则必须非常小心

HashSet

散列存放（哈希表在后续HashMap详细讲）
不保证存储顺序

  1. public static void main(String[] args) {
  2.         HashSet<String> set = new HashSet<>();
  3.         set.add("一二三四五");
  4.         set.add("上山打老虎");
  5.         set.add("老虎没打到");
  6.         set.add("打到小松鼠");
  7.         set.add("打到小松鼠");
  8.         for (String s : set) {
  9.             System.out.println(s);
  10.         }
  11.         /*上山打老虎
  12.           打到小松鼠
  13.           一二三四五
  14.           老虎没打到*/
  15.     }

TreeSet 和 Comparable

二叉树存储 有序，基于 Map 集合

  • 此类的iterator方法返回的迭代器是快速失败的：如果在创建迭代器之后的任何时间修改集合，除了通过迭代器自己的remove方法之外，迭代器将抛出ConcurrentModificationException 。

一定要实现 comparable 接口才可以实现比较

  1. public static void main(String[] args) {
  2.         TreeSet<String> data = new TreeSet<>();
  3.         data.add("A");
  4.         data.add("C");
  5.         data.add("D");
  6.         data.add("B");
  8.         TreeSet<Person> data2 = new TreeSet<>();
  9.         Person p1 = new Person("张三", 14);
  10.         Person p2 = new Person("张三", 15);
  11.         data2.add(p1);
  12.         data2.add(p2);
  13.         for (Person s:data2) {
  14.             System.out.println(s);
  15.         }
  16.     }
  17.     static class Person implements Comparable<Person>{
  18.         private String name;
  19.         private int age;
  21.         @Override
  22.         public int compareTo(Person o) {//自己定义规则
  23.             //返回的数据 负数(this小)/0(相等)/正数(this大)
  24.             if(this.age>o.age){
  25.                 return 1;
  26.             }else if(this.age == o.age){
  27.                 return 0;
  28.             }
  29.             return -1;
  30.         }

重复元素的说明

Map 集合（Mapping 映射）

多值存储，存储的是 键值对 数据（钥匙和锁）
键不可以重复，每一个键映射一个值
keySet();取出键 再迭代
put 添加数据
get
remove(); 取出并删除

哈希表

初始桶数量 16
散列因子 0.75以上 扩容一倍

Hashmap

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,//先得到hash值，即存储位置
  2.                    boolean evict) {
  3.         Node<K,V>[] tab; Node<K,V> p; int n, i;
  4.         if ((tab = table) == null || (n = tab.length) == 0)//判断哈希表是否为空
  5.             n = (tab = resize()).length;                    //扩容
  6.         if ((p = tab[i = (n - 1) & hash]) == null)  //取余运算 判断是否在桶中有数据
  7.             tab[i] = newNode(hash, key, value, null); //创建一个新节点
  8.         else {
  9.             Node<K,V> e; K k;
  10.             if (p.hash == hash &&
  11.                 ((k = p.key) == key || (key != null && key.equals(k))))//判断键是否存在
  12.                 e = p;                                            //覆盖老的值
  13.             else if (p instanceof TreeNode)                        //是否是树节点8个及以上
  14.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  15.             else {                                            //遍历链表
  16.                 for (int binCount = 0; ; ++binCount) {
  17.                     if ((e = p.next) == null) {
  18.                         p.next = newNode(hash, key, value, null);
  19.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  20.                             treeifyBin(tab, hash); // 变成二叉树
  21.                         break;
  22.                     }
  23.                     if (e.hash == hash &&
  24.                         ((k = e.key) == key || (key != null && key.equals(k))))
  25.                         break;
  26.                     p = e;
  27.                 }
  28.             }
  29.             if (e != null) { // existing mapping for key 覆盖操作
  30.                 V oldValue = e.value;
  31.                 if (!onlyIfAbsent || oldValue == null)
  32.                     e.value = value;
  33.                 afterNodeAccess(e);
  34.                 return oldValue;
  35.             }
  36.         }
  37.         ++modCount;//修改次数
  38.         if (++size > threshold)
  39.             resize();                        //看是否到达默认加载因子，是则扩容
  40.         afterNodeInsertion(evict);
  41.         return null;
  42.     }
  1. //HashMap/HashTable/ConCurrentMap
  2.     //TreeMap
  3.     //LinkedHashMap
  4. public static void main(String[] args) {
  5.         HashMap<String, String> m1 = new HashMap<>();
  6.         m1.put("key1", "我 草泥马");//将指定的值与此映射中的指定键相关联。
  7.                                     // 如果映射先前包含键的映射，则替换旧值
  8.         m1.put("key2", "我 是你爹");
  9.         Set<String> set = m1.keySet();//返回此映射中包含的 键 的Set视图
  10.         for(String key: set){
  11.             System.out.println(key+"+"+m1.get(key));//get()
  12.                                         // 返回指定键映射到的值，如果此映射不包含键的映射，则返回null
  13.         }
  14.         Collection<String> values = m1.values();//返回此映射中包含的值的Collection视图。
  15.         for(String value: values){
  16.             System.out.println(value);
  17.         }
  18.         m1.remove("key1");//从此映射中删除指定键的映射（如果存在）。
  19.         System.out.println(m1);
  20.     }

HashMap/ 线程不安全 效率高
HashTable/线程安全（排队执行，效率低）
ConCurrentMap 采用分段锁（多个排队的队伍）机制，保证线程安全，效率又比较高

散列因子

给到0.9，可能有的桶中的链表已经很长了，所以效率更低。
故散列因子越高，查询效率越低。
思考好初始容量，减少散列次数（重建数据结构）。

JDK9 新特性

  1. public static void main(String[] args) {
  2.         List<String> list = List.of("cxcx,xcxc,");//不可以改变
  3.         //list.add("12345");//报错，因为不可以添加
  4.         Set<String> set = Set.of("cxcx,xcxc,");//不可以改变
  5.         for(String s:set){
  6.             System.out.println(s);
  7.         }
  8.         Map<String, String> map = Map.of("haha1", "一二三四五", "haha2", "上山打老虎");
  9.         Set<String> keyset = map.keySet();
  10.         for(String key:keyset){
  11.             System.out.println(key+" -> "+map.get(key));
  12.         }
  14.     }