Java基础 | 集合框架

Java基础 | 集合框架

124 次访问
· Java基础

概述

集合与数组

  1. 集合和数组都是对多个数据进行存储操作的结构，即 Java 容器，此时的存储是指内存层面的存储，不涉及持久化的存储
  2. 数组一旦初始化，长度就确定了，而且存储的数据类型也确定了，数组提供的操作方法太少，增删插等操作不方便，效率不高，对于无序、不可重复的要求不能满足

集合的特点

  1. 用于存储对象的容器，动态存储
  2. 集合的长度是可变的
  3. 集合中不可以存储基本数据类型值

集合定义在 java.util 包下，可以分为两个体系

  • Collection：单列集合，用于存储对象
    • List 接口：元素有序、可重复的合
      • ArrayList
      • LinkedList
      • Vector
    • Set 接口：元素无序、不可重复的集合
      • HashSet
        • LinkedHashSet
      • TreeSet
  • Map：双列集合，用于存储具有映射关系的 key-value（键值对） 的对象
    • HashMap
      • LinkedHashMap
    • TreeMap
    • Hashtable
      • Properties

Collection 接口

集合容器因为内部的数据结构不同，有多种具体容器，不断向上抽象，就形成了集合框架，框架的顶层是 Collection 接口

常见方法

  1. 添加
boolean add(Object obj);
// 添加元素

boolean addAll(Collection coll); 
// 将coll中的元素添加至调用addAll()的集合中
  1. 删除
boolean remove(Object obj); 
// 删除obj元素

boolean removeAll(Collection coll); 
// 将两个集合中相同的元素从当前集合中删除

boolean retainAll(Collection coll); 
// 取交集：将两个集合中相同的元素从当前集合中保留，删除不同元素

void clear(); 
// 清空集合
  1. 判断
boolean contains(Object obj); 
// 判断集合中是否存在 obj 元素，注意，对于重写了 equals() 方法的类，比如String，底层是使用equals方法去比较 obj 对象的内容，如果没有写，则比较地址也就是 Object 类的对象，所以一般要求向集合中添加的类都要重写 equals() 方法

boolean containsAll(Collection coll); 
// 判断集合中是否包含coll中的所有元素

boolean isEmpty(); 
// 判断集合是否为空

boolean equals(Collection coll);
// 判断集合元素是否全部相同（不同的Collection实现类可能考虑或不考虑有序）
  1. 获取
int size(); 
// 返回集合中元素的个数

Iterator iterator(); 
// 取出元素的方式：迭代器，返回迭代器对象，因为每个容器的数据结构不同，所以该迭代器对象是在具体容器内部实现的，具体实现方法对于使用容器者不重要
  1. 其他
int hashcode();
// 返回集合的哈希值

Object[] toArray(); 
// 将集合转成数组

注意：数组转换为集合需要 Arrays 类的静态方法 asList(T t)

String str[] = new String[]{"hello","","world"}
List<String> list = Arrays.asList(str);
System.out.println(list);

ArrayList list1 = Arrays.asList(new Integer[]{123,456});
System.out.println(list1);

LinkedList list2 = Arrays.asList(new int[]{123,456});
System.out.println(list2);

遍历集合

Iterator 迭代器接口

Iterator 接口的对象即迭代器，用于遍历 Collection 容器（不用于 Map 遍历）中的元素，而不暴露容器的内部细节,注意集合对象每次调用 iterator() 都会得到一个全新的迭代器对象

方法

  • hasNext()
    • 判断当前指针位置的下一位置是否存在元素
    • 如果不用此方法控制遍历，可能出现 NoSuchElementException
  • next()
    1. 指针下移
    2. 返回指针下移之后所指位置上的元素
  • remove()
    在遍历的时候删除集合中的元素，此方法不同于集合直接调用remove()，如果还未调用 next()方法，或在上次调用 next()方法后已经调用了 remove()方法，再调用 remove() 方法的时候会出现 IllegalStateException

遍历的正确方方式

Iterator it = coll.iterator();
while(it.hasNext()) {
    System.out.println(it.next());
}

错误1

Iterator it = coll.iterator();
// 调用 next() 就会让指针后移
while(it.next()!=null) {
    System.out.println(it.next());
}

错误2

Iterator it = coll.iterator();
// 调用集合的 iterator() 就会返回一个全新的迭代器
while(coll.iterator().hasNext()) {
    System.out.println(coll.iterator().next());
}

使用迭代器删除集合中的对象

Iterator iterator = coll.iterator;
while(iterator.hasNext()) {
    Object obj = iterator.next();
    if(targetObj.equals(obj)) {
        iterator .remove();
    }
}

JDK5.0 新增 foreach 循环

Collection coll = new ArrayList();
coll.add(123);
coll.add("hello world");
coll.add(false);
// 集合元素的类型 局部变量 : 集合对象
for(Object obj : coll) {
    System.out.println(obj);
}

int[] arr = new int[]{1,2,3,4,5};
// 数组元素的类型 局部变量 : 数组对象
for(int i : arr) {
    Syetem.out.println(i);
}

注：增强 for 循环在底层也是调用迭代器

Collection 子接口：List

List 中的元素有序、可重复，每个元素都有其对应的顺序索引，可以根据索引存取，可以用来代替数组

List 接口的实现类主要是：ArrayList，LinkedList，Vector

  • ArrayList 是 List 的主要实现类，线程不安全，效率高，底层使用数组存储数据
  • LinkedList 底层使用双向链表，如果频繁插入和删除操作，效率高于 ArrayList
  • Vector 作为 List 接口的古老实现类，线程安全，效率低，底层使用数组存储数据

ArrayList

jdk7

  • 使用数组存储数据
  • 空参构造器 ArrayList()
    初始化一个长度为 10 的 Object 数组
  • 添加数据 add(E e)
    如果此次添加数据导致底层的 elementData 数组容量不够，则扩容，默认情况下，扩容为 newCapacity = oldCapacity + (oldCapacity >> 1)，即原来容量的 1.5 倍，然后将原数组中的数据复制到新的数组中
  • 建议使用有参构造器，先指定一个容量，减少扩容次数
    ArrayList list = new ArrayList(int initialCapacity)

jdk8

  • 空参构造器
    底层数组初始化为{}，没有创建长度为 10 的数组，相当于懒汉式，延迟了对象创建，节省内存
  • add()
    第一次调用 add() 的时候，底层才创建了长度为10的数组，并将数据添加进数组，后续的添加和扩容与jdk7一样

LinkedList

  • LinkedList 内部将元素封装到 Node 对象中，且声明了 Node 类型的 first 和 last 属性，默认值为 null，分别指向链表头尾
  • add() 创建 Node 对象
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev,E element,Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Vector

Vector 扩容方式：默认扩容为之前的2倍

List 接口中常用方法

相比 Collection 中的常用方法，多了关于索引的方法

void add(int index,Object ele)
// 在 index 索引位置插入元素

boolean addAll(int index,Collection eles)
// 从index索引位置开始将eles中所有元素添加进来

Object get (int index)
// 获取指定 index 索引位置的元素

Object set(int index,Object ele)
// 修改指定index位置的元素为ele

int indexOf(Object obj)
// 返回 obj 在集合中首次出现的索引，若不存在，返回 -1

int lastIndexOf(Object obj)
// 返回 obj 在集合中末次出现的索引，若不存在，返回 -1

Object remove(int Index)
// 移除指定 index 位置的元素，并返回该元素，注意 Collection 中的remove(Object obj)是按照对象删除

List subList(int fromIndex,int toIndex)
// 返回从 fromIndex 到 toIndex 位置的子集，左闭右开

对比 ArrayList 和 LinkedList

ArrayListLinkedList
底层实现数组链表
获取指定元素速度很快需要从头开始查找元素
添加元素到末尾速度很快速度很快
在指定位置添加/删除需要移动元素不需要移动元素
内存占用小较大

Collection 子接口：Set

  1. 无序性
    以 HashSet 为例，底层使用数组加链表实现，但是存储的数据在底层数组中并非按照数组的索引的顺序添加，而是根据哈希值确定，遍历的顺序不同于添加元素的顺序，但是每次的遍历顺序是相同的，不等于随机性
  2. 不可重复性
    向 Set 中添加的对象不可以重复，即保证添加的元素按照 equals() 判断时，不可返回true
  3. Set 没有提供额外的方法

HashSet

  • 作为 Set 接口的主要实现类，线程不安全，可以存储 null 值
  • 底层实现是数组加链表
  • 添加元素的过程
    向 HashSet 中添加元素 A，首先调用元素 A 所在类的 hashCode() 方法，计算元素 A 的 hash 值，然后此 hash 值通过某种算法计算出元素在 HashSet 底层数组中的存放位置（索引），判断数组如果此位置上没有其他元素，则添加成功，如果有其他元素 B（或以链表形式存在多个元素），则比较元素 A、B 的 hash 值，若不同，则添加成功，若哈希值相同，再调用 A 所在类的 equals() 方法，equals() 返回 true 则添加失败，若返回false，则添加成功，并以链表形式进行存储
  • 对于自定义类，如果没有重写 hashcode() 方法，则调用 Object 的 hashcode()，类似于随机数，就算两个对象的内容一样，哈希值也不同，那么放入底层数组的时候位置就大概率不同，所以也不会去调用 equals() 方法比较内容，调用 equals() 只会出现在：重写了 hashcode() 方法且哈希值相同且数组索引相同的情况下。如果 equals() 也返回 true，再使用链表追加
  • 要求：向set中添加的数据，其所在的类一定要重写 equals() 方法和 hashCode() 方法，且相同的对象一定要具有相等的哈希值，也就是说对象中用于 equals() 比较的 Field 也一定要用于计算哈希值
  • 注意，如果指定索引位置上已经以链表形式储存元素
    • jdk7 中，元素 A 放入数组中，指向原来的元素
    • jdk8 中，原来的元素放入数组中，指向 A

LinkedHashSet

  • 作为 HashSet 的子类，遍历其内部数据时，可以按照添加的顺序遍历
  • 其底层也是使用数组加链表存储数据，但同时也维护了两个引用，记录此数据的前后数据元素，对于频繁遍历，能提高效率

TreeSet

  • 底层使用红黑树，要求存入的数据必须是同一个类的对象，对象不可重复
  • 可以按照添加对象的指定属性进行排序：自然排序（实现 Comparable 接口）或定制排序（实现 Comparator 接口）
  • TreeSet 存储的元素必须实现了 Comparable 接口，或者创建 TreeSet 对象时传入一个 Comparator 接口的实现类对象

Map 接口

  • Map 接口存储双列数据，即 key-value（键值对）的数据
  • Map 中的 key 是无序不可重复的，使用 Set 存储 key，key 所在的类必须重写 equals() 和 hashCode()
  • Map 中的 value 无序可重复，使用 Collection 存储，value 所在的类要重写 equals()方法
  • 一个 key-value（键值对）构成一个 Entry 对象，Entry 对象是无序不可重复的，使用 Set 存储

HashMap

  • HashMap 是 Map 的主要实现类，线程不安全，效率高，可以存储值为 null 的 key 和 value
  • 底层实现：jdk7及之前使用数组 + 链表，jdk8 使用数组 + 链表 + 红黑树

jdk7

  • HashMap map = new HashMap();
    实例化一个 HashMap，底层创建了一个长度为 16 的数组 Entry[] table

  • map.put(k,v);
    首先调用 k 所在类的 hashCode() 方法计算 k 的哈希值，此哈希值再通过某种算法计算得到在 Entry[] 数组中的存放位置（索引）

    • 如果此位置上的数据为空，则 k-v 添加成功
    • 如果此位置上的数据不为空，也就是说此位置上存在一个或多个（链表形式）数据，则比较 k 和已存在的数据（一个或多个）的哈希值
      • 如果 k 的哈希值与已存在的数据的哈希值都不同，则 k-v 添加成功（以链表形式）
      • 如果 k 的哈希值和已经存在的某个数据的哈希值相同，继续比较
        • 调用 k 所在类的 equals()方法，如果 equals()返回 false，k-v添加成功
        • 如果 equals()返回 true：使用 v 替换之前的键值对中的 value（即修改已有的数据）

  • 在不断地添加过程中，涉及到扩容问题，当超出临界值且要存放的位置非空时，进行扩容，默认扩容方式：扩容位原来的2倍，并将元素复制到新的 Map

jdk8

  • new HashMap() 没有创建一个长度为 16 的数组
  • 底层为 Node[] 数组而不是 Entry[]
  • 首次调用 put() 方法时才创建长度为 16 的数组
  • 当数组某个索引位置的元素以链表形式存在的数据个数 >8，且数组长度 >64 时，该索引位置上所有数据改为使用红黑树存储
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

底层典型属性

  • DEFAULT_INITIAL_CAPACITY：HashMap的默认容量，16
  • DEFAULT_LOAD_FACTOR：HashMap的默认加载因子，0.75
  • threshold：扩容的临界值，= 容量*加载因子：16 * 0.75 => 12
  • TREEIFY_THRESHOLD：Bucket 中链表长度大于该默认值 8，转化为红黑树
  • MIN_TREEIFY_CAPACITY：Bucket 中的 Node 被树化时最小的数组容量，64

LinkedHashMap

  • LinkedHashMap 继承于HashMap，其底层使用的结构与 HashMap 相同，
  • LinkedHashMap 内部提供了 Entry，替换 HashMap 中的 Node
  • 底层的 Entry 类加了一对指针指向前后元素，可以按照添加元素的顺序实现遍历，对于频繁的遍历操作，效率高于HashMap
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before,after;
    Entry(int hash,K key,V value,Node<K,V> next) {
        super(hash,key,value,next)
    }
}

TreeMap

TreeMap 底层使用红黑树，向 TreeMap 中添加 key-value，要求 key 必须是用同一个类创建的对象，因为要按照 key 进行排序，实现自然排序（Comparable）或定制排序（Comparator）

Hashtable

Hashtable 是 Map 的古老实现类，线程安全，效率低，不能存储值为 null 的 key 和 value

Properties

  • 作为 Hashtable 的子类，常用于处理配置文件
  • 配置文件中的 key 和 value 都是 字符串，所以 Properties 中的 key 和 value 都是 String
  • 存取数据时，建议使用 setProperty(String key,String value) 方法和 getProperty(String key)
Properties pros = new Properties();
// 加载对应的文件流，这里简写，实际应用时，需要捕捉异常和关闭资源
pros.load(new FileInputStream("jdbc.properties"));
String user = pros.getProperty("user");
System.out.println(user);

常用方法

Object put(Object key,Object value)
// 将指定 key-value 添加到（或修改）当前 Map 对象中

void putAll(Map m)
// 将 m 中的所有 key-value 存储到当前 Map 对象中

Object remove(Object key)
// 移除指定 key 的key-value 对，并返回 value，如果当前 Map 中没有指定的 key，返回null

void clear()
// 清空当前 Map 对象中的数据，注意不是 map=null 操作，当前 Map 对象依然存在

Object get(Object key)
// 获取指定 key 对应的 value

boolean containsKey(Object key)
// 是否包含指定的key

boolean containsValue(Object value)
// 是否包含指定的value

int size()
// 返回当前 Map 对象的 key-value 对的个数

boolean isEmpty()
// 判断当前 Map 对象是否为空

boolean equals(Object obj)
// 判断当前 Map 对象和参数对象 obj 是否相同

/* 遍历Map ，先获取 key-value 对应的集合，之后可以用迭代器去遍历*/
Set keySet()
// 返回所有key构成的Set集合

Collection values()
// 返回所有 value 构成的 Collection 集合

Set entrySet()
// 返回所有 key-value 对构成的 Set 集合

Collections 工具类

Collections 是操作 Collection、Map 的工具类
常用方法

void reverse(List<?> list)
// 反转 List 中的元素的顺序

void shuffle(List<?> list)
// 对List中的元素进行随机排序

void sort(List)
// 根据自然顺序升序排序，List 中的元素必须实现了 Comparable 接口

void sort(List<T> list, Comparator<? super T> c)
// 根据指定 Comparator 产生的顺序对 List 集合元素进行排序

void swap(List<?> list,int i,int j)
// 将指定索引位置的两个元素交换

void copy(List dest,List src)
// 将 src 中的内容复制到 dest 中

boolean replaceAll(List list,Object oldVal,Object newVal)
// 使用新值替换 List 对象的所有旧值

Object max(Collection coll)
// 根据自然顺序，返回最大元素，元素必须实现了 Comparable 接口

Object max(Collection coll ,Comparator comp)
// 根据指定的比较器引发的顺序，返回给定集合的最大元素

Object min(Collection Coll)
// 根据自然顺序，返回最小元素，元素必须实现了 Comparable 接口

Object min(Collection Coll,Comparator comp)
// 根据指定的比较器引发的顺序，返回给定集合的最小元素

int frequency(Collection<?> c,Object o)
// 返回集合中元素 o 出现的次数

不可变集合
Collections 还提供了一组方法把可变集合封装成不可变集合

List<T> unmodifiableList(List<? extends T> list)

Set<T> unmodifiableSet(Set<? extends T> set)

Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> map)

注意：继续对原始的可变集合进行增删是可以的，并且，会直接影响到封装后的不可变集合。因此，如果希望把一个可变集合封装成不可变不可变，那么，返回不可变集合后，最好立刻置空可变集合的引用

线程安全集合
ArrayList 和 HashMap 都是线程不安全的，Collections还提供了一组方法，可以把线程不安全的集合变为线程安全的集合

List<T> synchronizedList(List<T> list)

Set<T> synchronizedSet(Set<T> set)

Map<K,V> synchronizedMap(Map<K,V> map)

注意：Java 5 引入了更高效的并发集合类，所以上述这几个同步方法已经没有什么用了

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://yzt.cool/archives/2020-03-19-javacollection

# Java # 集合

Java基础 | 泛型