Java集合学习

发表于 2023-02-09 更新于 2023-03-03 分类于 Java

集合继承结构图

classDiagram
    direction BT
    class Iterable {
        <<interface>>
        +Iterator()
    }
    
    class Collection {
        <<interface>>
    }
    
    class Iterator {
        <<interface>>
        +hasNext()
        +next()
        +remove()
    }
    
    class List {
        <<interface>>
    }
    
    class Set {
        <<interface>>
    }

    class ArrayList

    class LinkedList

    class Vector

    class HashSet

    class SortedSet {
      <<interface>>
    }

    class TreeSet
    
    Collection --|> Iterable : 继承
    Iterator <-- Collection : 关联
    List --|> Collection : 继承
    Set --|> Collection : 继承
    
    ArrayList ..|> List : 实现
    LinkedList ..|> List : 实现
    Vector ..|> List : 实现
    
    HashSet ..|> Set : 实现
    SortedSet --|> Set : 继承
    TreeSet ..|> SortedSet : 实现

Iterable 可迭代的，可遍历的，所有集合元素都是可迭代的，可遍历的
Collection 继承 Iterable，其所有集合也都是可迭代的
Iterator 和 Collection 是关联关系，Iterator 是迭代器
List 继承 Collection，List集合存储元素特点：
- 有序可重复，存储的元素有下标
- 有序实际上是说存进去是这个顺序，取出来还是这个顺序
- 这里的顺序不是按照大小排序。有序是因为List集合都有下标
- 下标从 0 开始，以 1 递增
ArrayList 集合底层是数组这种数据结构，是非线程安全的
LinkedList 集合底层采用了双向链表的数据结构
Vector 集合底层是数组这种数据结构，是线程安全的
Set 继承 Collection，Set 集合存储元素特点：
- 无序不可重复，无序表示存进去是这个顺序，取出来就不一定是这个顺序了
- Set 集合中元素没有下标，且 Set 集合中的元素不能重复
HashSet 集合在创建对象的时候，底层实际上是创建了一个 HashMap 集合
向 HashSet 集合存储元素，实际是存储到 HashMap 集合中，HashMap 集合是一个哈希表数据结构
HashSet集合初始化容量是16，初始化容量建议是2的幂
扩容：扩容之后是原容量的2倍
SortedSet 集合存储元素的特点：
- 由于继承 Set 集合，所以它也是无序不可重复，但是放在 SortedSet 集合中的元素可以自动排序
- 该集合中的元素是自动按照大小顺序排序的
TreeSet 集合底层实际是 TreeMap，创建TreeSet集合时，底层实际上创建了一个 TreeMap 集合，
向 TreeSet 集合中存放数据时，是将数据存放到 TreeMap 集合中
TreeMap 集合底层采用的是二叉树数据结构

classDiagram
    class Map {
        <<interface>>
    }
    
    class SortedMap {
        <<interface>>
    }
    
    class HashMap
    
    class Hashtable
    
    class TreeMap
    
    class Properties
    
    HashMap ..|> Map : 实现
    Hashtable ..|> Map : 实现
    SortedMap --|> Map : 继承
    TreeMap ..|> SortedMap : 实现
    Properties --|> Hashtable : 继承

Map 集合和 Collection 集合没有关系
- Map 集合以 key 和 value 的键值对的方式存储元素
- key 和 value 存储的是java对象的内存地址
- 所有Map集合的 key 特点：无序不可重复的
- Map 集合的 key 和 Set 集合存储元素特点相同
HashMap 集合底层是哈希表数据结构 / (数组+链表+红黑树)，是非线程安全的
- JDK8之后，如果哈希表中单向链表中元素超过8个，单向链表会变成红黑树数据结构
- 当红黑树上节点数量小于6时，会重新把红黑树变成单向链表数据结构
- 初始化容量16，默认加载因子0.75
- 扩容：扩容之后的容量是原容量的2倍
- 集合的key和value可以为null
Hashtable 集合底层也是哈希表数据结构，是线程安全的，现使用较少，因为控制线程安全有更好的方案了
- 初始化容量11
- 扩容：原容量 * 2 + 1
- 集合的key和value不能为null
SortedMap 集合的 key 存储元素特点：
- 无序不可重复的，SortedMap 集合 key 部分的元素会自动按照大小顺序排序，称为可排序的集合
TreeMap 集合底层是二叉树的数据结构
Properties 集合是线程安全的，因为继承 Hashtable，存储元素的时候也是采用 key 和 value 的形式存储，并且 key 和 value 只支持 String 类型，不支持其它类型，其被称为属性类

总结（所有的实现类）

ArrayList：底层是数组
LinkedList：底层是双向链表
Vector：底层是数组，线程安全的，效率较低，使用较少
HashSet：底层是 HashMap，放到 HashSet 集合中的元素等同于放到 HashMap 集合 key 部分
TreeSet：底层是 TreeMap，放到 TreeSet 集合中的元素等同于放到 TreeMap
HashMap：底层是哈希表 / (数组+链表+红黑树)
Hashtable：底层是哈希表，线程安全的，效率较低，使用较少
Properties：线程安全，key 和 value 只能存储字符串
TreeMap：底层是二叉树，TreeMap 集合的 key 可以自动按照大小顺序排序

List 集合存储元素的特点：
- 有序可重复
Set（Map） 集合存储元素特点：
- 无序不可重复
- 集合中元素没有下标
SortedSet（SortedMap） 集合存储元素特点：
- 无序不可重复
- 集合中元素是可排序的
  
  Map 集合的 key，就是一个 Set 集合
  往 Set 集合中放数据，实际上放到了 Map 集合的 Key 部分

TreeSet/TreeMap自平衡二叉树，遵循左小右大原则存放
遍历二叉树有三种方式：
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根

前中后说的是 “根” 的位置
TreeSet集合/TreeMap集合采用的是：中序遍历方式
Interator迭代器采用的是中序遍历

放到TreeSet或者TreeMap集合key部分的元素要想要做到排序，包括两种方式：
- 第一种：放在集合中的元素实现java.lang.Comparable接口
- 第二种：在构造TreeSet或者TreeMap集合的时候给它传一个比较器对象