Java - 集合

集合与数组的区别：

• 集合长度可变，数组长度不可变。
• 集合只能存储引用类型（自动装箱导致它看起来可以装基本类型），数组什么类型都可以。

集合分类：

1. 单列集合：Collection

• List：可重复（因为有索引可以区分开相同的元素），有存取顺序，有索引。
  • ArrayList 存读快，插删慢。
  • LinkedList
• Set：数学上的集合，元素不可重复。无索引，没法用fori循环！
  • HashSet：相同的元素，hash值一定会碰撞。
  • LinkedHashSet：有存取顺序。因为用了另外的数据结构记录这个顺序。
  • TreeSet：有序的。

注意：List <--> Set、数组 <--> 链表 都是相反的关系。

2. 双列集合：Map

key不可以重复，value可以重复。因为这就是数学里的映射，允许多对一，不允许一对多！

• HashMap 键可以有一个null值。有线程安全版本：ConcurrentHashMap
• LinkedHashMap
• TreeMap

字符串（特殊的集合）

• 遍历：利用toCharArray()转化为char[] 、使用charAt()方法
• 字符串倒序：先用构造器转换为StringBuider，然后调用其reverse方法 。字符串类型也有集合一样的contains方法。
  注意：判断字母或数字，用大于小于是最简单的，因为有ASCII码。

单列集合Collection API

• 增：add
• 删：remove（不依赖于索引，通过遍历实现的）、clear（省的再去new新的集合）
• 改
• 查
  • contains（List可以用来去重）
  • size
  • 没有 get ( int index ) 方法。因为get方法需要index，List有index，set没有index。但是有 toArray() 方法。
• 遍历：迭代器（没有索引的集合用得着）、foreach（语法糖）

Object[ ] toArray()方法注意事项：

public static void main(String[] args) {

        Collection<String> kartRider = new ArrayList<>();
        kartRider.add("SSS");
        kartRider.add("XX");
        kartRider.add("Owen");

//      运行时异常：ClassCastException
//      集合中的元素存在子父类关系，不代表集合之间存在子父类关系。  
//      只能对集合中的元素进行cast。
//      String[] kartRiderArray = (String[]) kartRider.toArray();
        Object[] kartRiderArray = kartRider.toArray();

        for (int i = 0; i < kartRiderArray.length; i++) {
            System.out.println( (String)kartRiderArray[i].length() );
        }

    }

还有一个重载方法<T> T[] toArray(T[] a)可以匹配类型

public static void main(String[] args) {

        Collection<String> kartRider = new ArrayList<>();
        kartRider.add("SSS");
        kartRider.add("XX");
        kartRider.add("Owen");

        String[] kartRiderArray = kartRider.toArray(new String[](kartRider.size()));

        for (int i = 0; i < kartRiderArray.length; i++) {
            System.out.println(kartRiderArray[i].length());
        }

    }

迭代器的使用分两步

• 调用集合方法获取集合的迭代器对象
• 调用迭代器方法进行遍历

public static void main(String[] args) {

        Collection<String> kartRider = new ArrayList<>();
        kartRider.add("SSS");
        kartRider.add("XX");
        kartRider.add("Owen");

//      调用集合方法获取集合的迭代器对象
        Iterator<String> it = kartRider.iterator();
//      调用迭代器方法进行遍历
        while(it.hasNext()) {
            System.out.println(it.next());
        }
    }

Collections工具类

提供了一些常用的处理集合的方法：sort、shuffle、binary search、reverse、addAll（懒人福音，把一个集合添加到另一个集合里面（批量添加，或者把一个无序集合转换成一个有序集合），省的遍历）。
数组的工具类 Arrays 也有 sort 方法。

List

• ArrayList
• LinkedList
  • 一个实现了List、Queue和Deque接口的双向链表。可以利用addFirst方法模拟Stack类的功能。Stack本身另外有一个类。
  • 与ArrayList相比，多了关于头尾的操作。
  • 栈和队列都是运算中受限的线性表，只能在两端进行操作，不能再中间进行插入、删除操作。
  • 链表的索引是利用链表遍历实现的：

  Node<E> node(int index) {
    // assert isElementIndex(index);
  
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
  }
  

List API

具有跟索引相关的增删改查方法。

• 增：add（元素）、add（索引，元素）（相当于插入元素，ArrayList的这个方法效率低）
• 删
• 改：set（索引，元素）
• 查：get（索引）
• 遍历：List 提供了功能更强大的的迭代器。可能是由于有了索引的缘故。

List.of 像是数组的静态初始化，返回一个长度不可变的List。利用addAll方法再把它添加到别的可变的列表中。

哈希值其实就是一种编号方式，就像利用地理位置、出生日期等属性为一个人编身份证号码一样，尽量保证唯一性。编号之后对数组长度取余，就得到存储地址。

Set

虽然没有索引，但是可以通过计算或比较get到元素。

• HashSet

  • 底层实现：数组+链表。和HashMap结构一样，只是值的位置不保存值，只利用键储存元素。
  • Hash的位置无法保证，所以HashSet无序！
  • 重写 hashCode() 和 equals() 方法.
    • hashCode( ) 默认以对象的物理地址作为输入计算hash值，因为每个对象的地址值都不一样，最终所有元素都会添加，所以有必要重写hashCode()方法。同时也要重写equals() 方法，用于hash值相同的时候做判断。
  • 为了减少hash冲突，数组达到0.75的容量，就会扩容。JDK8后，链表长到一定程度就会变成红黑树（自动平衡的二叉树）。

• LinkedHashSet

  • 有存取顺序。因为多用了一个数据结构记录顺序，记录的是元素的地址值。
    把 List 和 HashSet 结合使用也能实现去重和有序，这就和LinkedHashSet底层实现原理一样，多用了一个数据结构来记录顺序，就像是图的算法一样。

• TreeSet

  • 底层实现是二叉树，可以排序，输出的时候利用中序遍历。
  • 唯一性的保证、排序依据都依靠元素实现comparable接口或传入比较器对象。比较器可以写成匿名内部类。
  • 按照存储顺序打印：
    • 把 compareTo 方法特殊化：只需让比较器一直返回正数，最终，树就变成了链表。去重：判断相等，返回0. 不用修改类的代码。

Map API

• 增：put（key，value）
• 删：remove，clear
• 改：put
• 查：get、size、containsKey/Value：
• 遍历：keySet、values、entrySet（getkey、getValue）
  • values不叫valuesSet是因为value可以重复。
  • 两种遍历方式：横向（键找值）和竖向（键值对）。

注意：put方法具有添加和覆盖的功能，所以不叫add。

斗地主给牌排序：给牌按照大小编号后，利用HashMap或者parallel array。

反向输出

stack可以用来反向输出。
LinkedList在头上面加，然后输出的时候就会反向输出。
i -- 遍历也会实现反向输出。
集合元素倒序输出 Collections工具类的reverse
字符串倒转 StringBuider reverse 。利用构造器可以把String转化为StringBuider 。