Java集合

集合 一，java中的所有容器 1，变量 2，数组 2.1,数组的特点：

• 数组一旦定义，长度是固定的。
• 一个数组只能存贮一种数据类型
• 数组可以有无限种（数据类型和维度）

3，集合 二，数据结构： 栈

先进后出

队列

先进先出

数组

查询快 增删慢

链表： 查询慢，增删块

- 单向链表

节点

链表：

在链表中添加一个元素

在链表中删除一个元素

• 双向链表表

双向链表和单向链表的区别：

单向链表：只能从前往后查，节约空间。

双向链表：既可以往前查找，也可以从后去查，浪费空间，

数据的设计模式：

拿时间换空间，拿空间换时间

数据结构设计的精髓 ： 时间和空间的转换

案例：

题目的思想 ：拿时间换空间， 拿空间换时间
题： 有一个容器， 里面存储了1万个 连续的数 0-9999 (数的顺序是打乱的) ， 但是这些数里面 其中一个数 是缺失的， 有一个数 是重复的。
比如： 0 1 2 3 7 5 6 7 8 9 – 7 是重复的 4是缺失的。
顺序乱的： 9 6 7 3 2 7 5 1 0 8 – 7 是重复的 4是缺失的。
请你 用最快速的方法， 找到 那个缺失的数， 找到那个重复的数。

​ 这道题 最快速 2n

三，集合的体系结构 单列集合

双列集合

三，Collection(单列集合)

1. 概念：

集合类的根接口，用于存储一系列符合某种规则的元素，它有两个重要的子接口，分别是 java.util.List 与
java.util.Set。

2. 共性方法：

public boolean add(E e)：把给定的对象添加到当前集合中 。
public void clear()：清空集合中所有的元素。
public boolean remove(E e)：把给定的对象在当前集合中删除。
public boolean contains(E e)：判断当前集合中是否包含给定的对象。
public boolean isEmpty()：判断当前集合是否为空。
public int size()：返回集合中元素的个数。
public boolean removeif(Prodicate o)	根据条件进行删除
Collection中有一个iterator()；它的作用是返回一个Iterator接口。通常，我们通过Iterator迭代器来遍历集合。ListIterator是List接口所特有的，在List接口中，通过ListIterator()返回一个ListIterator对象。

3. 单利集合通用遍历方式：迭代器遍历

public static void main(String[] args) {
    Collection arr = new ArrayList<>();
    arr.add("aaaa");
    arr.add("bbbb");
    //遍历集合arr
    //获取迭代器
    Iterator iterator = arr.iterator();//获取迭代器
    while (iterator.hasNext()) {//通过指针判断有没有下一个元素可以迭代
        String next = iterator.next();//取到元素，然后将指针向后移动。
        System.out.println(next);
    }
}

4 .removeif(Prodicate o) 底层

曾强for

底层还是迭代器

public static void main(String[] args) {
    ArrayList arr=new ArrayList<>();
    arr.add("aaa");
    for (String s : arr) {
        System.out.println(s);
    }
}

四，list 1. 概念：

接口，list它的实现类可以存储重复元素，有索引，存取有序。List接口继承于Collection接口，它可以定义一个允许重复的有序集合。因为List中的元素是有序的，所以我们可以通过使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。

List接口为Collection直接接口。List所代表的是有序的Collection，即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素

2.List的特有方法 增

//boolean add(Object obj);
void add(int index, E e);

删

//boolean remove(E e);
E remove(int index);

改

E set(int index , E e)

查

E get(int index);

3. ArrayList 3.1底层数据结构：

数组

3.2概念

ArrayList是一个动态数组，也是我们最常用的集合。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。每次扩容1.5倍所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

ArrayList擅长于随机访问。同时ArrayList是非同步的。

3.3ArreyList底层的扩容

这里的size有两个作用。可以用来当做索引，也可以作为数组的长度。

在不超过10的情况下：

当超出10的情况：

4. linkedListt 4.1. 底层数据结构

双向链表

linkedList也是非同步的

4.2 特有方法：头和尾相关的方法

public void addFirst(E e)	在该列表开头插入指定的元素
public void addLast(E e)	将指定的元素追加到此列表的末尾
public E getFirst()		返回此列表中的第一个元素
public E getLast()		返回此列表中的最后一个元素
public E removeFirst()		从此列表中删除并返回第一个元素
public E removeLast()		从此列表中删除并返回最后一个元素

4.3 linkedList没有索引，但是他是List的实现类，那也就有get,set方法，但是它底层是链表，没有索引，因此，底层进行了索引的模拟 伪代码展示

public class Text01 {
    public  get(int index) {
        int count = 0; //计数器
        int size0 = this.size(); // size0 记录了 当前linkedList集合有多少个元素。
        if (index < size0 / 2) { // 从前往后
            while (true) {
                //从前往后找的代码
                //每找一次
                count++;
                if (count == index) {
                    //找到了
                    return 那个值;
                }
            }
        } else {
            while (true) {
                // 从后往前找
                //每找一次
                size0--;
                if (size0 == index) {
                    //找到了
                    return 那个值;
                }
            }

        }

    }

}	

4.4 add源码

5. Vector 5.1 底层数据结构

数组

在jdk1.7和1.8的时候，通过Vector（）创建对象的时候，都是创建一个长度为10的数组，在扩容方面也扩为原来的二倍

public Vector() {
    this(10);
}

Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。

五，Set 1 . TreeSet 1.1 底层数据结构

底层是通过TreeMap实现的，也就是红黑树，将TreeMap的所有值设置为null，将键赋值给TreeSet

1.2 特点

去重复 (把元素排了序，排序中遇到重复 去掉了重复)， 存取无序，没有索引

1.3 排序方式：

自然排序

让自定义对象实现Comparable接口，重写CompareTo方法

比较器排序

通过带惨构造创建TreeSet集合对象，通过匿名内部类的方式创建Comparator 的实现类 ，重写Compare方法，写规则。

两种排序方式的优先级：

如果TreeSet存储元素的时候， 元素自己也具备自然排序规则， 同时你也传入了比较器， 那么 TreeSet 底层会优先使用 比较器。

2. 哈希值 HashCode方法

HashCode方法 是 Object 的， 所有类的对象 都是可以调用HashCode方法的。 Object 的HashCode方法
是底层调用的一个本地函数， 他是通过你的对象的地址值通过一些算法得到一个唯一的数字， 不同的对象 这个数字是绝对不会相同的。

类 继承了 Object 也是可以重写 HashCode方法的， 重写之后，HashCode方法的返回值 就不再代表地址了。

//自定义的学生类重写hashCode（）方法

@Override
public int hashCode() {
    return name != null ? name.hashCode() : 0;//通过对象的name值来获取不同的hash值
}

3，HashSet (☆☆☆☆)： 3.1 底层数据结构

哈希表 （数组+链表）

数组的长度默认值为16，加载因子为0.75

在JDK1.8之后，底层链表长度大于8的时候就转换为红黑树

HashSet的底层其实是HashMap的键来做的，将HashMap的值全部设置为null

3.2 HashSet保证元素唯一性

首先拿着元素的 HashCode值，和哈希表所有的哈希值去比。看看哈希表中，有没有存在存在和元素的哈希值相同的元素；
如果不存在 ： 就直接把这个元素 添加到哈希表中
如果存在： 就让这个元素 拿着自己的equals方法，和哈希值相同的那些元素，依次去equals
如果比了一遍：都是false 则添加到集合中
如果比了一遍：有返回true的 则不添加集合(替换)

如果存储自定义对象，需要重写hashCode()方法和equals()方法

通过hashCode()方法得到存储的索引位置。通过equals()方法判断两个对象是否相同

3.2 HashSet的add()方法

源码解析：

TreeSet底层存储原理

4. linkedHashSet(☆☆☆) ： 4.1 底层数据结构：

在哈希表的基础上 额外使用了一个链表来存储 元素存入的顺序去重 存取有序 无索引

数组的长度默认值为16，加载因子为0.75

linkedHashSet没有add()方法，所以它调用的是HashSet的add()方法

六，Map（双列） (☆☆☆☆☆): 1 .特点：

​

双列 ： 键 和 值 都是一一对应的

​ 键是不能重复的， 值无所谓 ​ 因为双列集合中 键是充当编号的作用， 而值
才能真正存储的数据，而数据是多样的，不被限制。但是编号必须是唯一的， 你只能通过编号找到唯一的值， 而不能通过编号找到好几个值。

2.共性方法

public Value put(Key, Value)  添加一个键值对， 会去找 如果这个集合中没有这个键 就添加键值对，并返回一个null
										// 如果这个集合中已经有即将添加的键了， 就让即将添加的键对应的值  把已经存在的键值对的 那个值 替换掉，并返回被替换的值
 public Value remove(key);	//删除								
 public boolean isEmpty();
 public void clear();
 public void containsKey(key );
 public void containsValue(value );
 public int size();
 public value get(key);
 public Set keySet();  // 把所有的键封装成一个Set集合 返回。 
 public Collection values(); // 为什么返回的是Collection  因为 值是没有任何要求的。

Map map = new HashMap<>();
			map.put("003", "张三");
			map.put("004","李四");
			map.put("005","王五"); 

3.Map的遍历方式：

获取Map集合的每一个键 获取Map集合的 每一个值，还要保证键和值的对应关系。

遍历方式一：

 根据键找值(效率低)

 Map map = new HashMap<>();
map.put("杨过","小龙女");
map.put("张无忌","周芷若");
map.put("国境","皇绒");
 Set keys = map.keySet();
for(
 String key :keys)

 {
     String value = map.get(key);
     System.out.println(key + "-" + value);
 }

 遍历方式二：

 根据键值对找键和值(效率高)

 Map map = new HashMap<>();
map.put("杨过","小龙女");
map.put("张无忌","周芷若");
map.put("国境","皇绒");
 Set> entries = map.entrySet();
for(
 Entry entry :entries)

 {
     String key = entry.getKey();
     String value = entry.getValue();
     System.out.println(key + "-" + value);

     遍历方式三：Map 接口提供了一个
     default
         的方法 foreach
         public class HashSetTest1 {
             public static void main(String[] args) {
                 Map map = new HashMap<>();
                 map.put("杨过", "小龙女");
                 map.put("张无忌", "周芷若");
                 map.put("国境", "皇绒");
                 map.forEach(
                         (Student key, String value) -> {
                             System.out.println(key + "----" + value);
                         }
                 );
             }
         }

         interface Map {
             public default void forEach(BiConsumer action) {
                 Objects.requireNonNull(action);
                 for (Map.Entry entry : entrySet()) {
                     K k;
                     V v;
                     try {
                         k = entry.getKey();
                         v = entry.getValue();
                     } catch (IllegalStateException ise) {
                         throw new ConcurrentModificationException(ise);
                     }
                     action.accept(k, v);
                 }
             }
         }

         interface BiConsumer {
             void accept(T t, U u);
         }

4. forEach（)的底层

5.HashMap

键是唯一的， 底层是用哈希表来维持键的唯一的.

6. TreeMap

TreeMap 双列集合， 键是唯一的， 底层如何保证键的唯一呢， TreeMap 底层是用红黑树来维持键的唯一的。

注意：

所以使用 TreeMap 的键的位置存储 元素的话，则元素 1:要么已经实现了
Comparable接口并重写了compareTo方法的排序规则， 2：要么就在TreeMap中的构造方法里面
传递一个 Comparator 的子类对象 。 如果两个任何一个都不提供的话 则就运行报错，因为TreeMap 无法知晓排序规则。