Java——集合

集合优点：

可以动态保存任意多个元素，且类型不限
提供一系列操作方法：add、remove、set、get等

集合分类：

单列集合（Collection）分为 List (ArrayList、LinkedList、Vector)和 Set (HashSet、TreeSet)
双列集合（Map）: HashMap(使用频率最高) 、 TreeMap 、Hashtable 、 Properties

Collection接口

Collection常用方法

CollectionMethod
//常用操作
List list = new ArrayList();
list.add(10);
list.add("jack");
list.add(true);
System.out.println(list);   //输出
list.remove(0);   //删除第一个元素
list.remove("jack");  //指定删除某个对象
System.out.println(list.contains("jack"));  //查找元素是否存在
System.out.println(list.size);  //获取元素个数
System.out.println(list.isEmpty());   //判空
list.clear();  //清空
list.addAll(list2);   //添加多个元素
System.out.println(list.containsAll(list2));  //查找多个元素
list.removeAll(list2);  //删除多个元素

Collection接口遍历元素

方法一 ： Iterator (迭代器)
Collection col = new ArrayList();
col.add(...);
Iterator it = col.iterator();
while(it.hasNext()){    //判断集合是否还有数据
	Object obj = it.next();  //遍历 快捷键itit 查看快捷ctrl+j
}
//遍历结束后it迭代器指向最后的元素
//如果希望再次遍历，需要重置迭代器
it = col.iterator();

方法二 ：增强for循环 (底层依然是迭代器)  //快捷键 I
for(Object book : col){
	sout(book);
}


Exercise
public class Collection_ {
    public static void main(String[] args) {
        @SuppressWarnings("all")
        List list = new ArrayList();
        list.add(new Dog("AA",3));
        list.add(new Dog("BB",6));
        list.add(new Dog("CC",4));

        for (Object o :list) {
            System.out.println(o);
        }
        System.out.println("============================");
        Iterator it = list.iterator();
        while (it.hasNext()) {
            Object obj =  it.next();
            System.out.println(obj);
        }


    }
}

class Dog{
    private String name;
    private int age;

    public Dog(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Dog{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

如果集合中存放的是对象元素，对集合遍历时，需要对象调用方法时，应注意向下转型（Object—>）

List接口

List接口是Collection接口的子接口

List集合类中元素有序（添加顺序和取出顺序一致）、且可以重复
List集合中的每一个元素都有对应的顺序索引

1、List集合类中元素有序（添加顺序和取出顺序一致）、且可以重复
List list = new ArrayList();
        list.add("java");
        list.add("c++");
        list.add("c");
        list.add("php");
        list.add("python");
        System.out.println(list);
输出：[java, c++, c, php, python]
    
2、List集合中的每一个元素都有对应的顺序索引
    	list.add(1,"javaScript");
        list.set(2,"c#");
        System.out.println(list);
输出：[java, javaScript, c#, c, php, python]
    
3、常用方法
        list.add(1, "mary");
        List list2 = new ArrayList();
        list2.add("jack");
        list2.add("tom");
        list.addAll(1, list2);
        System.out.println("list=" + list);
        list.set(2,"c");
        System.out.println("list=" + list);
        System.out.println(list.indexOf("c"));//2
        System.out.println(list.lastIndexOf("c"));   //最后索引位置
        list.remove(0);
        List returnlist = list.subList(1, 3); //截取一段 前闭后开
        System.out.println(list);
        System.out.println("returnlist=" + returnlist);
输出：   list=[java, jack, tom, mary, javaScript, c#, c, php, python]
        list=[java, jack, c, mary, javaScript, c#, c, php, python]
        2
        6
        [jack, c, mary, javaScript, c#, c, php, python]

ArrayList底层操作机制

ArrayList中维护了一个Object类型的数组elementData

transient Object[] elementData;

其中transient 修饰成员变量时，意味着该成员变量不会参与序列化过程。

序列化：序列化是将对象的状态转换为字节流的过程，以便将其保存到文件、数据库或通过网络传输。
当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0,第一次添加时,则扩容elementData为10,如需再次扩容,则扩容elementData为1.5倍
如果使用的是指定大小的构造器，则初始elementData容量大小为指定大小，如果需要扩容，则直接扩容到1.5倍

LinkedList

LinkedList底层维护了一个双向链表
LinkedList中维护了两个属性first和last分别指向首节点和尾节点
每个节点（Node对象），里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点，最终实现双向链表
所以LinkedList的元素添加和删除，不是通过数组完成的，相对来说效率较高

如何选择ArrayList和LinkedList：

如果改查操作比较多，选择ArrayList
如果增删操作比较多，选择LinkedList
大部分情况下查询比较多，因此一般选择ArrayList，也可以一个项目中，一个模块使用ArrayList，另一个模块使用LinkedList

ArrayList、LinkedList和Vector的区别

Java中的ArrayList、LinkedList和Vector都是用于存储集合元素的类，但它们在实现上有一些区别。

线程安全性：
- ArrayList：是非线程安全的。在多线程环境下，如果不进行额外的同步处理，可能会导致并发问题。
- LinkedList：同样是非线程安全的。
- Vector：是线程安全的。它通过在每个方法上使用synchronized关键字来实现同步，因此可以在多线程环境中使用，但这也使得性能相对较低。
底层数据结构：
- ArrayList：底层数据结构是动态数组，支持随机访问元素。
- LinkedList：底层数据结构是双向链表，不支持直接的随机访问，需要从头或尾开始遍历。
- Vector：底层数据结构也是动态数组，与ArrayList类似。
性能：
- ArrayList：由于底层是数组，因此对于随机访问和按索引位置添加/删除元素的操作性能较好。但在插入和删除中间元素时，可能需要移动大量元素。
- LinkedList：在插入和删除中间元素时性能较好，因为只需修改相邻节点的引用。但对于随机访问性能较差。
- Vector：由于是线程安全的，性能相对较低，不推荐在单线程环境中使用，可以考虑使用ArrayList代替。
增长策略：
- ArrayList 和 Vector：在元素数量超过当前容量时，它们会重新分配一个更大的数组，ArrayList通常1.5倍，Vector通常两倍。
- LinkedList：没有预定义的容量，每次插入都会动态分配内存。
迭代器（Iterator）：
- ArrayList 和 Vector：支持通过迭代器（Iterator）进行遍历。
- LinkedList：由于是双向链表，还支持从头到尾或从尾到头的遍历。

总体而言，选择使用哪个类取决于具体的需求。如果需要快速随机访问元素，且不涉及多线程操作，ArrayList是一个不错的选择。如果需要频繁插入和删除元素，或者需要支持多线程操作，可以考虑使用LinkedList或Vector，具体取决于对多线程支持的需求。在单线程环境下，通常推荐使用ArrayList。

Set接口

无序（添加和取出的顺序不一致，但取的时候位置固定），没有索引
不允许有重复的数据（取决于地址），最多包含一个null
用的比较多的是 HashSet 和 TreeSet

Set接口常用方法

Set常用方法和List一样

Set接口遍历方式

可以使用迭代器
增强for
不能使用索引的方式来获取

		Set set = new HashSet();
        set.add("c++");
        set.add("java");
        set.add("c");
        set.add("php");
        set.add("null");
        System.out.println(set);

        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            Object obj =  iterator.next();
            System.out.print(obj + " ");
        }
        System.out.println("\n===================");
        for (Object o : set) {
            System.out.print(o + " ");
        }
输出：
[c++, java, c, null, php]
c++ java c null php 
===================
c++ java c null php

HashSet说明

HashSet实现了Set接口（无序，不重复，无索引）
HashSet实际上是HashMap

   HashSet set = new HashSet();
        set.add("lucy"); //T
        set.add("lucy"); //F
        set.add(new Cat("tom"));//T
        set.add(new Cat("tom"));//T
        set.add(new String("java"));//T
        set.add(new String("java"));//F
class Cat{
    private String name;

    public Cat(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Cat{" +
                "name='" + name + '\'' +
                '}';
    }
}
输出：[java, Cat{name='tom'}, lucy, Cat{name='tom'}]

HashSet底层机制说明

HashSet底层是HashMap
添加一个元素时，先得到hash值，然后将hash值转化为索引值
找到存储表table，看这个索引位置是否已经存放元素
如果没有，直接加入
如果有，调用equals比较，如果相同，就放弃添加，如果不同则添加到最后
在Java8中，如果一条链表的元素个数超过了TREEIFY_THRESHOLE(默认是8)，并且table的大小>=MIN_TREEIFY_CAPACITY(默认64)，就会进行树化（红黑树）
第一次添加时，table数组扩容到16，临界值（threshold）是16*加载因子，（loadFactor）是0.75 = 12
如果table数组使用到了临界值12，就会扩容到16*2 = 32，新的临界值就是32 *0.75 = 24，依次类推

LinkedHashSet

LinkedHashSet是HashSet的子类
LinkedHashSet底层是一个LinkedHashMap，底层维护了一个数组+双向链表
LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是以插入顺序存储的。
LinkedHashSet不允许添加重复元素
在LinkedHashSet中维护了一个表和双向链表（LinkedHashSet中有head和tail）
每个结点中有pre和next属性，可以形成一个双向链表
在添加一个元素时，先求hash值，再求索引，确定该元素在table中的位置，然后将要添加的元素加入到双向链表中（需要用equals判断，如果规定的equals方法重复，则不能添加）

tail.next = newElement;
newElement.pre = tail;
tail = newElement;    //更新tail指针，使新插入的元素成为尾结点

第一次添加时，直接将数组table扩容到16
HashMap$Node[] 中存放LinkedHashMap$Entry, 因为Entry extends HashMap;

TreeSet

TreeSet基于红黑树数据结构实现，因此具有有序性和高效的插入、删除和查找操作。

特性：

有序性（Ordered）：TreeSet 是有序的集合，它按照元素的自然顺序或者使用提供的比较器（Comparator）进行排序。这使得元素在集合中以特定的顺序存储。
唯一性（Unique）：TreeSet 不允许重复元素。如果试图插入重复元素，插入操作将被忽略。
基于红黑树（Red-Black Tree）：TreeSet 使用红黑树作为底层数据结构，这确保了在对数时间内执行插入、删除和查找操作。

TreeSet比较器：

当使用无参构造器，创建TreeSet时,按从小到大排序

TreeSet treeSet = new TreeSet();
      treeSet.add("abc");
      treeSet.add("zzz");
      treeSet.add("asdfg");
      treeSet.add("aaaa");
      treeSet.add("a");
      System.out.println(treeSet);
结果： [a, aaaa, abc, asdfg, zzz]

当希望按照自定义方式进行排序时，可以用Comparator

TreeSet treeSet = new TreeSet(new Comparator() {
           @Override
           public int compare(Object o1, Object o2) {
               return ((String)o2).compareTo((String)o1);
           }
       });
       treeSet.add("abc");
       treeSet.add("zzz");
       treeSet.add("asdfg");
       treeSet.add("aaaa");
       treeSet.add("a");
       System.out.println(treeSet);
 结果： [zzz, asdfg, abc, aaaa, a]

//按长度排序
TreeSet treeSet = new TreeSet(new Comparator() {
           @Override
           public int compare(Object o1, Object o2) {
               return ((String)o2).length()-((String)o1).length();
           }
       });
       [asdfg, aaaa, abc, a]

Map接口

Map接口实现类特点

Map与collection并列存在，用于保存具有映射关系的数据 key-value
Map中的key和value可以是任意引用类型的数据，会封装在HashMap$Node对象中
Map中的key不允许重复，原因和HashSet一样，但如果key重复，则用新的value代替旧的
Map的value可以重复
Map的key可以为null，但只能有一个，value也可以为null，可以有很多个
常用String类作为Map的key, （但其类型其实为 OBJECT，所以object类均可）
key和value之间存在单向一对一的关系，即通过指定的key总能找到与之对应的value
一对k-v是放在一个HashMap$Node中，Node实现了Entry接口

Map接口常用方法

Map hashMap = new HashMap();
      hashMap.put("001",123);      //添加
      hashMap.put("002",123);		
      hashMap.put("003",123);
      hashMap.put("001",222);		//"001"重复，将会把001-123覆盖掉
      System.out.println(hashMap);
      hashMap.remove("003");      //根据键删除映射关系
      System.out.println(hashMap);
      System.out.println(hashMap.get("002"));  //根据键获取值
      System.out.println(hashMap.size());       //获取元素个数
      System.out.println(hashMap.isEmpty());    //判断元素个数是否为0
      System.out.println(hashMap.containsKey("001")); //查找键是否存在
      hashMap.clear();              //清空
      System.out.println(hashMap);
结果： {001=222, 002=123, 003=123}
{001=222, 002=123}
123
2
false
true
{}

Map遍历方法

containsKey：查找键是否存在
keySet：获取所有的键
entrySet：获取所有关系k-v
values：获取所有的值

Map hashMap = new HashMap();
      hashMap.put("001","java");
      hashMap.put("002","c++");
      hashMap.put("003","c");
      hashMap.put("004","python");

      //一、先取出所有的key，通过key取出对应的value
      Set keyset = hashMap.keySet();
      for (Object key : keyset) {   //增强for
          System.out.println(key + "-" + hashMap.get(key));
      }
      Iterator iterator1 = keyset.iterator();
      while (iterator1.hasNext()) {
          Object key =  iterator1.next();
          System.out.println(key + "-" + hashMap.get(key));
      }
      
      //二、把所有的values取出来
      Collection values = hashMap.values();
      for (Object value : values) {
          System.out.println(value);
      }
      Iterator iterator2 = values.iterator();
      while (iterator2.hasNext()) {
          Object value =  iterator2.next();
          System.out.println(value);
      }
      
      //三、通过EntrySet来获取k-v
      Set entrySet = hashMap.entrySet();
      for (Object entry : entrySet) {
          Map.Entry m =(Map.Entry)entry;
          System.out.println(m.getKey() + "-" + m.getValue());
      }
      Iterator iterator3 = entrySet.iterator();
      while (iterator3.hasNext()) {
          Object entry =  iterator3.next();
          Map.Entry m = (Map.Entry)entry;
          System.out.println(m.getKey() + "-" + m.getValue());
      }

HashMap

HashMap是Map接口使用频率最高的实现类
与HashSet一样，不保证映射顺序，因为底层是以hash表的方式存储的
HashMap没有实现同步，因此是线程不安全的

底层机制

HashMap底层维护了Node类型的数组table，默认为null
当创建对象时，将加载因子（loadfactor）初始化为0.75
当添加k-v时，通过key的哈希值得到下table 的索引，然后判断该索引处是否有元素，如果没有元素直接添加，如果该索引处有元素，则继续判断该元素的key是否和准备加入的key值一样，如果相等，则直接替换val，如果不相等需要判断是树结构还是链表结构，做出相应的处理，如果添加时发现容量不够，则需要扩容
第一次添加时，扩容table容量为16，临界值（threshold）为12（16*0.75）
以后再次扩容，则需要扩容table容量为原来的两倍，临界值为原来的两倍，即24，以此类推
在Java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD（默认是8），并且table的大小>=MIN_TREEIFY_CAPACIYU(默认64)，就会树化（红黑树）

HashTable

存放的元素是键值对：即k-v
hashTable的键和值都不能为null,否则会抛出NullPointerException
hashTable使用方法基本上和HashMap一样
hashTable是线程安全的，hashMap线程不安全

Properties

Properties类继承自Hashtable类并实现了Map接口，也是使用一种键值对的形式来保存数据
使用特点和Hashtable类似
Properties还可以用于从xxx.properties文件中，加载数据到Properties类对象，并进行读取和修改
说明：工作后 xxx.properties文件通常作为配置文件

TreeMap

和TreeMap基本一致，此处元素为键值对。

Collections工具类

Collections 是一个操作 Set 、List 和 Map 等集合的工具类
Collections 中提供了一系列静态的方法对集合元素进行排序、查询、修改等操作

排序操作：

reverse(List)：反转 List 中元素的顺序
shuffle(List)：对List 集合元素进行随机排序
sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
sort(List,Compartor)：根据指定的Compatator产生的顺序对List集合元素进行排序
swap(List,int,int)：将指定List 集合中的i处元素和j元素进行交换

查找、替换操作：

Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
Object max(Collection,Compartor)：根据Compartor指定的顺序，返回给定集合中的最大元素
Object min(Collection)
Object min(Collection,Compartor)
int frequency (Collection,Object)：返回指定集合中指定元素出现的次数
void copy (List dest,List src)：将src中的内容复制到dest中
boolean replaceAll(List list,Object oldVal,Object newVal)：使用新值替换List对象的所有旧值

小结：开发中如何选择集合实现类

主要取决于业务操作特点，然后根据集合实现类特性进行选择

先判断存储的类型（一组对象或一组键值对）
一组对象：Collection接口
```
 允许重复：List
```
增删多：LinkedList（底层双向链表）

改查多：ArrayList（底层Object 类型的可变数组）

不允许重复：Set

无序：HashSet（底层HashMap，哈希表，数组+链表+红黑树）

排序：TreeSet

插入和取出顺序一致：LinkedHashSet（数组+双向链表）
一组键值对：Map

键无序：HashMap（底层：哈希表，jdk7：数组+链表，jdk8：数组+链表+红黑树）

键排序：TreeMap

键插入和取出顺序一致：LinkedHashMap

读取文件：Properties