JAVA集合框架

14.集合

14.1 集合框架概述

在java中，对于多元素的存储提供了丰富的集合类支持。

Collection接口：集合类的根接口，定义了所有集合中的共性方法

List接口：有序集合，允许存在重复元素，可通过索引进行遍历

Set接口：无序集合，不允许存在重复元素，不能通过索引进行遍历

14.2 Collection集合

Collection集合常用方法

1. public boolean add(E e) 把指定的元素添加到集合中
2. public void clear() 清空集合中的所有元素
3. public boolean remove(E e) 移除集合中给定的元素
4. public boolean contains(E e) 如果集合中包含指定的元素，则返回 true
5. public boolean isEmpty() 判断集合是否为空
6. public int size() 返回集合中的元素个数
7. public Object[] toArray() 将集合中的元素转换成数组的格式存储

14.3 Iterator接口

在程序开发中，经常需要遍历集合中的元素。针对这种需求，JDK专门提供了Iterator接口来对集合进行遍历，

Iterator又被称为迭代器。

Iterator常用方法

1. public boolean hashNext() 判断集合中是否仍有元素可以迭代，有就返回true
2. public E next() 返回迭代的下一个元素
3. public void remove() 移除当前迭代的元素

代码演示说明

public class CollectionTest {

    public static void main(String[] args) {
        Collection collection = new ArrayList();
        collection.add("hello");
        collection.add(123);
        
        Iterator it = collection.iterator();
        while(it.hasNext()) {
            it.next();
            it.remove();
        }
        System.out.println(collection.size());
    }
}

14.4 数据结构

java中的集合主要使用了如下几种数据结构

1. 数组
2. 栈
3. 队列
4. 链表
5. 红黑树

数组

数组会在内存中开辟一块连续的内存空间，然后当有数据进入的时候会将数据按顺序的存储在这块连续的内存中。

链表

创建链表的过程和创建数组的过程不同，不会先划出一块连续的内存。因为链表中的数据并不是连续的，链表在存储数据的内存中有两块区域，一块区域用来存储数据，一块区域用来记录下一个数据保存在哪里（指向下一个数据的指针）。当有数据进入链表时候，会根据指针找到下一个存储数据的位置，然后把数据保存起来，然后再指向下一个存储数据的位置。这样链表就把一些碎片空间利用起来了，虽然链表是线性表，但是并不会按线性的顺序存储数据。

栈

栈是限制在一端进行插入操作和删除操作的线性表（俗称堆栈），允许进行操作的一端称为“栈顶”，另一固定端称为“栈底”，当栈中没有元素时称为“空栈”。向一个栈内插入元素称为是进栈，push；从一个栈删除元素称为是出栈，pop。特点 ：后进先出(LIFO)

队列

队列是一种先进先出的线性表，它只允许在表的一端进行，而在另一端删除元素。

在队列中，允许插入的一端叫做队尾，允许删除的一端则称为队头。

**红黑树**

普通的二叉查找树在极端情况下可退化成链表，此时的增删查效率都会比较低下。

为了避免这种情况，就出现了一些自平衡的查找树，比如 AVL(自平衡二叉树)，红黑树等。这些自

平衡的查找树通过定义一些性质，将任意节点的左右子树高度差控制在规定范围内，以达到平衡状态。

红黑树通过如下的性质定义实现自平衡：

1. 根节点是黑色
2. 节点是红色或黑色
3. 所有叶子都是黑色(叶子是NIL节点)
4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点(简称黑高)

14.5 List接口

List接口的常用方法

1. public boolean add(E e) 向集合中新增元素
2. public void clear() 清空集合中的元素
3. public boolean contains() 如果集合中包含指定的元素，则返回 true
4. public E get(int index) 获取集合中指定索引的元素
5. public boolean remove(Object o) 移除集合中给定的元素
6. public int size() 返回集合中的元素个数

14.6 List接口子类

ArrayList集合

​ ArrayList集合，底层使用的是数组的数据结构，查询快，增删慢。所以ArrayList适用于元素遍历

LinkedList集合

​ LinkedList集合，底层使用的是链表结构，方便元素的添加与删除。适用于频繁修改的业务场景。

Vector集合

​ 底层也是使用数据结构存储，最大的区别在于，Vector集合是同步的，线程安全的。

14.7 Set接口

Set接口与List接口相似，都是继承自Collection接口。只不过Set集合中的元素不能重复且无序。

Set接口的常用实现类是HashSet，底层实现是哈希表，查询速度非常快。

哈希值

java中对象的hash值，是由系统底层生成的一串十进制的整数，代表对象的逻辑地址，但不是实际存储

的物理地址。

public class HashCodeTest {

    public static void main(String[] args) {
        Person person = new Person();
        System.out.println(person.hashCode());
    }
}

哈希表

哈希表=数组+链表

java8以后，哈希表=数组+链表+红黑树

HashSet集合

HashSet底层就是使用哈希表这种数据结构来进行存储。

LinkedHashSet集合

由于HashSet集合保证了数据的唯一性，但元素的存储是无序的，因此可以通过LinkedHashSet来解决该问题

，它是链表与哈希表的组合数据结构。

14.8 Map接口

Map集合主要用于存储KV类型的对象。

常用实现类

1. HashMap<K,V>

   ​ 采用哈希表进行存储，元素的存储顺序不能保证一致。

2. LinkedHashMap<K,V>

   ​ HashMap的子类，采用哈希表+链表的结构，能够保证存储顺序的一致性

Map接口中的常用方法

1. public V put(K key, V value) 将制定的键和值存储到Map集合中
2. public V get(Object key) 根据制定的键，在Map中获取指定的值
3. public V remove(Object key) 根据制定的键，删除Map集合中对应的键值对
4. public Set<K> keySet() 获取Map集合中所有的键，并存储到Set集合中
5. public Collection<V> values() 获取Map集合所有的值，并存储到Collection集合中
6. public Set<Map.Entry<K,V>> entrySet() 获取Map集合中所有的键值对

14.9 Collections工具类

Collections工具类，主要用于对Collection集合类进行排序、求大小值等操作。

Collections工具类常用方法

• public static boolean addAll(Collection<? super T> c, T... elements) 同时添加多个元素到集合
• public static int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) 二分查找法
• public static T max(Collection<? extends T> coll) 根据元素的自然排序，返回集合中的最大值
• public static T min(Collection<? extends T> coll) 根据元素的自然排序，返回集合中的最小值
• public static void sort(List<T> list) 根据元素的自然顺序 对指定列表按升序进行排序
• public static void sort(List<T> list, Comparator<? super T> c) 根据指定比较器产生的顺序对指定列表进行排序。

代码演示说明

addAll()

public class CollectionsTest {

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        //同时添加多个元素
        Collections.addAll(list, "a", "b", "c", "d");
        //元素遍历
        list.forEach(x -> System.out.println("element: " + x));
    }
}

sort升序

public class CollectionsTest {

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        //同时添加多个元素
        Collections.addAll(list, "b", "e", "c", "f");
        //升序
        Collections.sort(list);
        //元素遍历
        list.forEach(x -> System.out.println("element: " + x));
    }
}

自定义sort排序

由于Collections.sort()默认只支持基本数据类型和字符串的自然排序，如果想要对自定义对象进行自然排序，排序对象需要实现Comparable接口，并重现其compareTo()方法

自定义对象

public class User implements Comparable<User>{

    private String name;
    private int age;

    public User() {}

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

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

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

    @Override
    public int compareTo(User o) {
        return o.getAge() - this.getAge();
    }
}

compareTo排序规则

• this - 其他对象等于升序
• 其他对象 - this等于降序

sort(List list, Comparator<? super T> c)

对于自定义对象的排序，除了通过对象实现Comparable接口之外，还可以单独实现Comparator接口来创建外置

比较器，来对集合进行排序

public class CollectionsTest {

    public static void main(String[] args) {
        List<User> list = new ArrayList<>();
        //添加对象元素
        list.add(new User("mike", 20));
        list.add(new User("bob", 22));
        list.add(new User("max", 18));
        //升序
        Collections.sort(list, new Comparator<User>() {
            @Override
            public int compare(User o1, User o2) {
                return o1.getAge() - o2.getAge();
            }
        });
        //元素遍历
        list.forEach(u -> System.out.println(u));
    }
}

compare排序规则

• o1 - o2等于升序
• o2 - o1等于降序

Comparable接口与Comparator的区别?

参数	Comparable	Comparator
排序逻辑	排序逻辑在待排序对象中实现，故称为自然排序	排序逻辑独立实现
实现	实现Comparable接口	实现Comparator接口
排序方法	int compareTo(Object o1)	int compare(Object o1, Object o2)
触发排序	Collections.sort(List)	Collections.sort(List, Comparator)
接口所在包	java.lang.Comparable	java.util.Comparator

max(Collection<? extends T> coll)

public class CollectionsTest {

    public static void main(String[] args) {
        List<User> list = new ArrayList<>();
        //添加对象元素
        list.add(new User("mike", 20));
        list.add(new User("bob", 22));
        list.add(new User("max", 18));
        //get max user
        User maxUser = Collections.max(list);
        System.out.println("max user: "+ maxUser);
    }
}

min(Collection<? extends T> coll)

public class CollectionsTest {

    public static void main(String[] args) {
        List<User> list = new ArrayList<>();
        //添加对象元素
        list.add(new User("mike", 20));
        list.add(new User("bob", 22));
        list.add(new User("max", 18));
        //get max user
        User maxUser = Collections.min(list);
        System.out.println("max user: "+ maxUser);
    }
}

binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

public class CollectionsTest {

    public static void main(String[] args) {
        List<User> list = new ArrayList<>();
        //添加对象元素
        list.add(new User("mike", 20));
        list.add(new User("bob", 22));
        list.add(new User("max", 18));
        //二分查找
        int index = Collections.binarySearch(list, new User("bob", 22));
        System.out.println("user index: " + index);
    }
}