Java基础 | 集合框架

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 引入了更高效的并发集合类,所以上述这几个同步方法已经没有什么用了