[数据结构与算法]Java集合框架及其数据结构全析

Java集合框架及其数据结构全析

最近学到了集合章节，其中的Map接口和Collection接口及它们的实现类相当多且功能不一，结合网上资料及API文档，做个笔记。

1.类集概述

如果大致了解过Java的集合，我们就可以发现集合中所有的实现类都是为了完成增，删，改，查的数据容器存储作用，与我们之前学习的数组作用一致，Java的容器的优点就是通过将许多功能特点不同的数据结构放在一个篮子里，取名为集合，方便使用和总结，

Java集合与数组也有不同：

1. Java集合的长度会自动扩容，不用像数组一样一定要先确定长度

Java集合都实现了toArray（）方法方便与数组的转换

1.1各种数据结构

1.1.1 数组

数组（Array），就是把有限个数据类型一样的元素按顺序放在一起，用一个变量命名，然后通过编号可以按顺序访问指定位置的元素的一个有序集合。

类似于抽屉，特点是方便查找但增删数据效率低。

1.1.2 链表

链表（linked list）

特点是：用一组任意的存储单元存储线性表的数据元素，因此为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。

class Node{
    Object data;  //数据储存
    Node next;  //储存逻辑上下一个元素的结点地址
}

1.1.3 二叉树（红黑树）

（略）红黑树百度简介为：

红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。

红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。

由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hnZROxrB-1627998863374)(C:\Users\ASUS\Pictures\截图\2021-08-03_101731.png)]

（重要）二叉树的概念为：二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

二叉树数据结构的特点是：

1.有序存储

2.非常适于查找，因为查找的过程与二分查找类似，数据量越大越适于用二叉树存储数据

class Node{
    Object data;  //数据
    Node left;  //左节点
    Node right;  //右节点
}

1.1.4 栈，队列

栈与队列都是使用操作受限的数据结构

栈（stack）：只能从顶部弹出和存储，先进先出的数据结构

队列（queue）：数据从头部进入只能从尾部出去，先进先出的数据结构

1.1.5 哈希表（重，难）

哈希表的百度解释为：

散列表（Hash table，也叫哈希表），

是根据关键码值(Key value)而直接进行访问的数据结构。

也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

这个映射函数叫做散列函数，

存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

从百度解释可以看出，哈希表是以键记录地址，Map有一对键值对可以再通过值存储数据，HashSet 却比较特殊，直接使用键来存储数据从而又可以快速查找又能存储数据

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-V2c20pt7-1627998863376)(C:\Users\ASUS\Pictures\截图\2021-08-03_104542.png)]

特殊的，当哈希桶中的数据到达8之后，该桶中数据会从链表转化为红黑树存储，当桶中数据存储为红黑树，同时数据减小到6时，又会换回链表存储。

2. Collection

作为根界面，其定义的方法最普遍也最泛用。

• 集合层次结构中的根界面Collection 。 集合表示一组被称为其元素的对象。 一些集合允许重复元素，而其他集合不允许。

常用方法：

• • add(E e)
  • 确保此集合包含指定的元素（可选操作）。
• • clear()
  • 从此集合中删除所有元素（可选操作）。
• • addAll(Collection<? extends E> c) 将指定集合中的所有元素添加到此集合（可选操作）。
• • contains(Object o)
  • 如果此集合包含指定的元素，则返回 true 。
• • toArray()
  • 返回一个包含此集合中所有元素的数组。

因为集合中收录的数据结构都会实现Collection接口，具有一定的相同底层逻辑，所以都可以用迭代器方便的迭代（类似遍历）

第一种迭代器使用方法：

ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
Iterator<String> iterator = arrayList.iterator();
while (iterator.hasNext()){
    String s = iterator.next();
    System.out.println(s);
}
//输出结果为 
//A
//B
//C

—不同类实现迭代器中还有快速失败和安全失败的区分：

快速失败：迭代器线程进行时，数据发生改变，会抛出异常

安全失败：迭代器线程进行时，改变数据仍不会影响进程

后面发现操作可以放进别的方法来简化代码，所以出现了增强for循环

第二种迭代器使用方法：

for（数据类型（引用） 变量名：集合或数组名）{}

ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
for (String s: arrayList) {  //可以使用foreach快捷打出框架
    System.out.println(s);
}  //输出结果与上面一致

2.1 List 接口

作为可重复的有序数据结构接口

其常用方法为：

• • add(E e)
  • 将指定的元素追加到此列表的末尾
• • add(int index, E element) //增
  • 将指定的元素插入此列表中的指定位置
• • get(int index) //查
  • 返回此列表中指定位置的元素。
• • remove(int index) //删
  • 删除该列表中指定位置的元素（可选操作）。
• • remove(Object o)
  • 从列表中删除指定元素的第一个出现（如果存在）（可选操作）。
• • sort(Comparator<? super E> c)
  • 使用随附的 Comparator排序此列表来比较元素。
• • toArray()
  • 以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。
• • set(int index, E element) //改
  • 用指定的元素替换此列表中指定位置的元素。

其实现类为：

2.1.1 ArrayList（95%）

ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A"); //增
arrayList.add("B");
arrayList.add("C");
arrayList.remove("C");  //删
arrayList.remove(1); 
arrayList.set(0,"B");  //改
for (String s: arrayList) {
            System.out.println(s);  //查
        }
//结果为B

改实现类自动扩容，第一次为10，之后1.5倍增长

2.1.2 Vector(4%)

构造和使用与ArrayList一致

除了空参构造，它还有两个特殊的构造，可以自定义数组的初始容量和容量增量，且其标准扩容为翻番扩容，所以大量数据更适合用此存储

• • Vector(int initialCapacity)
  • 构造具有指定初始容量并且其容量增量等于零的空向量。
• • Vector(int initialCapacity, int capacityIncrement)
  • 构造具有指定的初始容量和容量增量的空向量。

2.1.3 LinkedList（1%）

使用双向链表结构查找，存储，所以有增删快，查找满的特点。

LinkedList有相较于其他实现类特殊的方法

• • addFirst(E e)
  • 在该列表开头插入指定的元素。
• • addLast(E e)
  • 将指定的元素追加到此列表的末尾。
• • getFirst()
  • 返回此列表中的第一个元素。
• • getLast()
  • 返回此列表中的最后一个元素

所以可以用来模拟栈，队列的数据结构

2.2 Set接口

不包含重复元素的集合

其常用方法与Collection类似，并未添加太多新的方法

2.2.1 HashSet类（常用）

新的方法不多，对象的创建也与List类似

存储的是散列的哈希表

2.2.2 TreeSet类

TreeSet中存储的是不重复的排序数据，有序二叉树哈希表存储，其关于Comparable的重写还有特殊的要求：

可以看到，当我们的自定义对象没有重写Compare方法时，TreeSet无法找到排序依据，

(细节) 当对象需要用哈希表存储时，必须重写equals（）和hashcode（）方法 包括后面的HashMap 和 TreeMap

这个时候我们可以让自定义对象实现Compare接口并且重写

CompareTo方法：

为int类型，

返回正数则调用者排在前面，

负数则实参排在前面，

相等就会被替换（因为不能存储相同数据）

具体操作：

class Book implements Comparable<Book>{

    private String name;
    private String info;
    private int number;

    @Override
    public int compareTo(Book o) {
        if(this.number > o.number){
            return 1;
        }
        else if(this.number < o.number){
            return -1;
        }
        return 0;
    }
}

全部代码：

public static void main(String[] args) {

    Book book = new Book("老人与海","人类意志的歌咏",12);
    Book book1 = new Book("老人与海1","人类意志的歌咏1",13);
    Book book2 = new Book("老人与海2","人类意志的歌咏2",14);

    TreeSet t = new TreeSet();
    t.add(book);
    t.add(book1);
    t.add(book2);
    for (Object b:t) {
        System.out.println(b.toString());
    }
}

class Book implements Comparable<Book>{

    private String name;
    private String info;
    private int number;

    @Override
    public int compareTo(Book o) {
        if(this.number > o.number){
            return 1;
        }
        else if(this.number < o.number){
            return -1;
        }
        return 0;
    }

    @Override
    public String toString() {
        return "Book{" +
                "name='" + name + '\'' +
                ", info='" + info + '\'' +
                ", number=" + number +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Book book = (Book) o;
        return number == book.number && Objects.equals(name, book.name) && Objects.equals(info, book.info);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, info, number);
    }

    public Book() {
    }

    public Book(String name, String info, int number) {
        this.name = name;
        this.info = info;
        this.number = number;
    }

    public String getName() {
        return name;
    }

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

    public String getInfo() {
        return info;
    }

    public void setInfo(String info) {
        this.info = info;
    }

    public int getNumber() {
        return number;
    }

    public void setNumber(int number) {
        this.number = number;
    }
}

输出结果：

Book{name=‘老人与海’, info=‘人类意志的歌咏’, number=12}
Book{name=‘老人与海1’, info=‘人类意志的歌咏1’, number=13}
Book{name=‘老人与海2’, info=‘人类意志的歌咏2’, number=14}

3. Map接口

存储着一对对键值对，且不可重复存储，

常用方法为：

• • get(Object key)
  • 返回到指定键所映射的值，或 null如果此映射包含该键的映射
• • keySet()
  • 返回此地图中包含的键的Set视图。 //返回Set[]
• • put(K key, V value) //与add不同，是put添加
  • 将指定的值与该映射中的指定键相关联（可选操作）。
• • values()
  • 返回此地图中包含的值的Collection视图。 //返回Collection[]
• • containsKey(Object key)
  • 如果此映射包含指定键的映射，则返回 true 。
• • containsValue(Object value)
  • 如果此地图将一个或多个键映射到指定的值，则返回 true 。

3.1 HashMap<K,V> 散列表

Map实现类使用实例（HashTable，ConcurrentHashMap泛用）

具体实现如下：

HashMap<Integer,String> hashMap = new HashMap<>();

hashMap.put(1,"A");
hashMap.put(2,"B");
hashMap.put(3,"C");

String value = hashMap.get(1);
System.out.println(value);

Set<Integer> integers = hashMap.keySet();
for (int i:integers) {
    System.out.println(i + "->" +hashMap.get(i));
}

//输出结果
//A
//1->A
//2->B
//3->C

此地图将一个或多个键映射到指定的值，则返回 true 。

3.2 Map集合各子类区别分析