跳至主要內容

13、集合

T4makojava基础语法java数据结构大约 16 分钟

集合

数组的缺陷：

  • 一旦初始化以后，其长度就确定了
  • 数组一旦定义好，其元素的类型就确定了。只能操作指定类型的数据。
  • 初始化以后，长度不可修改
  • 数组中提供的方法非常有限，对于添加、删除、插入等操作非常不便，效率不高
  • 获取数组中实际元素的个数的需求，数组没有现成的属性或方法可用
  • 数组存储的特点：有序、可重复。对于无序、不可重复的需求，不能满足

1、Java 集合的分类

Java 集合可分为 Collection 和 Map 两种体系

  • Collection 接口：单列数据， 定义了存取一组对象的方法的集合
    • List： 元素有序、可重复的集合
      • ArrayList、LinkedList、Vector
    • Set： 元素无序、不可重复的集合
      • HashSet、LinkedHashSet、TreeSet
  • Map接口： 双列数据，保存具有映射关系key-value对的集合
    • HashMap、LinkedHashMap、TreeMap、Hashtble、Properties

2、Collection 接口中的方法的使用

方法描述
boolean add(Object obj)添加，成功返回 true，失败返回 false
boolean addAll(Collection coll)添加，成功返回 true，失败返回 false
int size()有效元素的个数
void clear()清空集合
boolean isEmpty()是否是空集合
boolean contains(Object obj)是否包含某个元素，通过元素的 equals 方法来判断是否是同一个对象
boolean containsAll(Collection c)也是调用元素的 equals 方法来比较
boolean remove(Object obj)通过元素 equals 方法判断是否是要删除的那个元素。只会删除找到的第一个元素
boolean removeAll(Collection c)删除
boolean retainAll(Collection c)取两个集合的交集，将结果存在当前集合中，不影响c
boolean equals(Object obj)集合是否相等
hashCode()获取集合对象的哈希值
iterator()返回迭代器对象，用于集合遍历
Object[] toArray()将集合转化为对象数组

相关信息

  • 集合求交运算：boolean retainAll(Collection c)
  • 并运算：boolean addAll(Collection c)
  • 差运算：boolean removeAll(Collection c)
    向 Collection 接口的实现类的对象中添加数据 obj 时，要求 obj 所在类要重写 equals()
Collection coll = new ArrayList();
coll.add("AA");
coll.add(123);// 自动装箱
coll.add(new Date());
System.out.println(coll.size()); // 3
Collection coll1 = new ArrayList();
coll1.add(456);
coll1.add("cc");
coll.addAll(coll1);
System.out.println(coll.size()); // 5
coll1.clear();
coll.remove(123);// true
System.out.println(coll.isEmpty());

3、List 接口

1、List 接口框架

List 接口：存储有序的、可重复的数据

  • ArrayList：线程不安全的，效率高。底层使用 Object[]
  • LinkedList：对于频繁的插入，删除，使用此类效率比 ArrayList 高，底层使用双向链表
  • Vector：作为 List 接口的古老实现类，线程安全的，效率低。底层使用 Object[]

List 接口中的常用方法

方法描述
void add(int index, Object e)在 index 位置插入 e 元素
boolean addAll(int index, Collection e)从 index 位置开始将 e 中的所有元素添加
Object get(int index)获取指定 index 位置的元素
int indexOf(Object obj)返回 obj 在集合中首次出现的位置
int lastIndexOf(Object obj)返回 obj 在当前集合中末次出现的位置
Object remove(int index)移除指定 index 位置的元素，并返回此元素
Object set(int index, Object e)设置指定 index 位置的元素为 e
List subList(int fromIndex, int toIndex)返回从 fromIndex 到 toIndex 位置的子集合

相关信息

如果使用泛型，get() 方法返回泛型类对象，如果没有使用泛型，返回 Object 对象，需要强制转换

2、ArrayList

相关信息

jdk7 下 ArrayList 的创建规则：

ArrayList list = new ArrayList();// 底层创建了长度是 10 的 Object[] 数组 elementDate
list.add(1);//elementData[0] = new Integer(123);
...
list.add(11);//扩容，扩容为原来的 1.5 倍，将原有数组中的数据复制到新的数组中

jdk8 下 ArrayList 的创建规则

ArrayList list = new ArrayList();//底层 Object[] elementData 初始化为 {}.并没有创建长度为 10 的数组
list.add(123);//第一次调用 add() 时，底层才创建了长度为 10 的数组，并将数据 123 添加到 elementDate，后续添加与 jdk7 无异

jdk7 中的 ArrayList 的对象的创建类似于单例的饿汉式
jdk8 中的 ArrayList 的兑现的创建类似于单例模式的懒汉式，延迟数组的创建，节省内存

3、LinkedList

LinkedList 中 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;
    }
}

LinkedList<E> 泛型类本身新增的一些常用方法：

方法描述
void addFirst(E e)向链表的头添加新结点 e
void addLast(E e)向链表的末尾添加新结点 e
void getFirst()得到第一个结点的数据
void getLast()得到最后一个结点的数据
void removeFirst()删除第一个结点
void removeLast()删除最后一个结点
void Objcet clone()得到当前链表的一个克隆链表（深拷贝）
LinkedList list =  new LinkedList();//内部声明了 Node 类型的 first 和 last 属性，默认值为 null
list.add(123);//将 123 封装到 Node 中，创建了 Node 对象

相关信息

常用方法
增：add(Object obj)
删：remove(int index) / remove(Object obj)
改：Object set(int index, Object ele)
查：Object get(int index)
插：void add(int index, Object ele)
长度：size()
遍历：

  • Iterator 迭代器
  • 增强 for 循环
  • 普通循环

List 添加的数据也需要在其所在类重写 equals() 方法，因为有 remove，contains 方法

相关信息

集合，数组之间的转换:

  • 集合 -> 数组：toArray()
  • 数组 -> 集合：Arrays.asList()

4、Vector

jdk7 和 jdk8 中通过 Vector() 构造器创建对象时，底层都创建了长度为 10 的数组，在扩容方面，默认扩容为原来的数组长度的 2 倍

相关信息

ArrayList、LinkedList、Vector 的异同:

  • 相同点：
    • 三个类都实现了 List 接口，存储数据的特点相同：存储有序的、可重复的数据
  • 不同点：
    • ArrayList：作为 List 接口的主要实现类：线程不安全的，效率高。底层使用 Object[] 数组
    • LinkedList：对于频繁的插入，删除，使用此类效率比 ArrayList 高，底层使用双向链表
    • Vector：作为 List 接口的古老实现类：线程安全的，效率低。底层使用 Object[] 数组

4、Iterator 迭代器接口

集合元素的遍历操作，使用迭代器 Iterator 接口

  1. 内部的方法：hasNext()、next()
  2. 集合对象每次调用 iterator() 方法都得到一个全新的「迭代器对象」
  3. iterator 内部定义了 remove()，可以在遍历的时候，删除集合中的元素。此方法不同于集合直接调用 remove
Collection coll = new ArrayList();//List 是有序的
coll.add(456);
coll.add(123);
coll.add(new String("Tom"));
coll.add(false);
coll.add(new Person("Jerry",20));

Iterator iterator = coll.iterator();
//next():①指针下移 ②将下移以后集合位置上的元素返回
while (iterator.hasNext()){
    System.out.println(iterator.next());
}

Collection coll = new ArrayList();//List 是有序的
coll.add(456);
coll.add(123);
coll.add(new String("Tom"));
coll.add(false);
coll.add(new Person("Jerry",20));
//
Iterator iterator = coll.iterator();
while (iterator.hasNext()){
    Object obj = iterator.next();
    if("Tom".equals(obj)){
        iterator.remove();
    }
}
Iterator iterator1 = coll.iterator();
while (iterator1.hasNext()){
    System.out.println(iterator1.next());
}

5、堆栈

堆栈是一种后进先出的数据结构

java.util 包中的 Stack<E> 泛型类创构建一个堆栈对象

方法描述
E push(E e)压栈，向顶端插入数据
E pop()出栈，顶端移除数据
boolean empty()判断栈是否还有数据
E peek(E e)获取栈顶数据
int search(Object data)获取数据在栈中的位置，顶端为 1，向下增加，如果不含此数据返回 -1

6、foreach 遍历集合

使用 foreach 遍历集合、数组

public class forTest {
    @Test
    public void test(){
        Collection coll = new ArrayList();//List是有序的
        coll.add(456);
        coll.add(123);
        coll.add(new String("Tom"));
        coll.add(false);
        coll.add(new Person("Jerry",20));

        //for(集合中元素的类型 局部变量 : 集合对象)
        //内部仍然调用了迭代器
        for(Object obj : coll) {
            System.out.println(obj);
        }
    }
    @Test
    public void test2(){
        int[] arr = new int[]{1,2,3,4,5,6};
        //for(数组中元素的类型 局部变量 : 数组对象)
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

7、Set 接口

  • HashSet：作为 Set 接口的主要实现类，线程不安全的，可以存储 null 值
  • LinkedHashSet：作为 HashSet 的子类，遍历其内部数据时，可以按照添加顺序遍历
  • TreeSet：可以按照添加对象的指定属性，进行排序

set 接口中没有额外的定义新的方法，使用的都是 Collection 中声明的方法

  • 向 set 中添加的数据，其所在类一定要重写 hashCode() 和 equals() 方法
  • 重写的 hashCode() 和 equals() 尽可能保持一致性：相等的对象必须具有相同的散列码
  • 对象中用作 equals() 方法比较的 Field，都应该用来计算 hashCode 值。

HashSet

  • 无序性：存储的数据在底层根据数据的哈希值决定
  • 不可重复性：相同的元素只能添加一个，添加的元素按照 equals() 方法判断时，不能返回 true

向 HashSet 中添加元素 a，首先调用元素 a 所在类的 hashCode() 方法，计算元素 a 的哈希值，此哈希值通过某种算法计算出 HashSet 底层数组中的存放位置（即索引位置），判断此位置上是否已经有元素

  • 如果此位上没有其他元素，则元素 a 添加成功
  • 较元素 a 与 b 的哈希值，如果哈希值不相同，则元素 b 添加成功
  • 如果哈希值相同，需要调用元素 a 所在类的 equals() 方法：
    • equals() 返回 true，元素 a 添加失败
    • equals() 返回 fasle，则元素 a 添加成功 --> 情况三

对于添加成功的情况 2、3：元素a存在指定索引位置上数据以链表的方式存储。
jdk 7：元素 a 放到数组中，指向原来的元素
jdk8：原来的元素在数组中，指向元素 a
（七上八下）

HashSet 底层：数组 + 链表

public void test(){
    Set set = new HashSet();
    set.add(456);
    set.add(123);
    set.add("AA");
    Iterator iterator = set.iterator();
    while (iterator.hasNext()){
        System.out.println(iterator.next());
    }
}

LinkedHashSet

LinkedHashSet 作为 HashSet 的子类，在添加数据时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据
优点：对于频繁的遍历操作，LinkedHashSet 效率高于 HashSet

TreeSet

树集合采用树结构存储数据，结点从左到右，从上到下，按小到大排序

向 TreeSet 添加的数据，要求是相同类的对象

TreeSet 的额外方法（SortedSet 接口规定）：

E first()返回 TreeSet 中第一个结点数据（最小数）
E last()返回 TreeSet 中最后一个结点数据（最大数）

两种排序方式：

  • 自然排序（实现 Comparable 接口）
  • 定制排序（Comparator 接口）

对于 TreeSet 集合而言，它判断两个对象是否相等的唯一标准是：两个对象通过 compareTo(Object obj) 方法比较返回值

  • 自然排序中，比较两个对象是否相同的标准：compareTo() 返回 0，不再是 equals()
  • 定制排序中，比较两个对象是否相同的标准：compare() 返回0，不再是 equals()
public class TreeSetTest {
    @Test
    public void test(){
        //举例一
        TreeSet set = new TreeSet();
        set.add(123);
        set.add(-123);
        set.add(66);
	    //遍历
        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
        
        //举例二
        // Person 类实现了 Comparable 接口
        TreeSet set1 = new TreeSet();
        set1.add(new Person("AA",20));
        set1.add(new Person("BB",22));
        set1.add(new Person("CC",18));
        set1.add(new Person("ABC",66));
        set1.add(new Person("ABC",65));
        Iterator iterator1 = set1.iterator();
        while (iterator1.hasNext()){
            System.out.println(iterator1.next());
        }
    }
    
	//使用 Comparator
    @Test
    public void test2() {
        Comparator com = new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof Person && o2 instanceof Person) {
                    Person p1 = (Person) o1;
                    Person p2 = (Person) o2;
                    return Integer.compare(p1.getAge(), p2.getAge());
                } else {
                    throw new RuntimeException("类型不合");
                }
            }
        };
        TreeSet set1 = new TreeSet(com);
        set1.add(new Person("AA", 20));
        set1.add(new Person("BB", 22));
        set1.add(new Person("CC", 18));
        set1.add(new Person("ABC", 66));
        set1.add(new Person("ABC", 65));
        Iterator iterator1 = set1.iterator();
        while (iterator1.hasNext()) {
            System.out.println(iterator1.next());
        }
    }
}

8、Map 接口

Map：双列数据，存储 key-value 对的数据

  • HashMap：线程不安全的，效率高，可以存储 null 的 key 和 value
  • LinkedHashMap：保证在遍历 map 元素时，可以按照添加的顺序实现遍历，对于频繁的遍历操作，效率高于 HashMap
  • TreeMap：保证按照添加的 key-value 对进行排序，实现排序遍历，此时考虑 key 的自然排序或定制排序（底层使用红黑树）
  • Hashtable：作为古老的实现类：线程安全，效率低；不能存储 null 的 key 和 value
  • Properties：常用来处理配置文件。key 和 value 都是 String 类型

HashMap 底层实现：

  • 数组 + 链表（jdk7及以前）
  • 数组 + 链表 + 红黑树（jdk8）

Key-Value 的理解：

  • Map中的key：
    • 无序的、不可重复的
    • 使用 Set 存储所有的 key
    • key 所在类要重写 equals() 和 HashCode() 方法
  • Map 中的 value：无序的、可重复的
    • 使用 Collection 存储所有的 value
    • value 所在类要重写 equals() 方法
  • 一个键值对 key-value 构成了一个 Entry 对象
    • Map 中的 entry：无序的、不可重复的，使用 set 存储所有的 entry

装载因子：
HashMap 在需要更多的存储空间时，会自动增大容量，若 HashMap 的装载因子是 0.75 ，那么当 HashMap 的容量使用了 75% 时，就把容量怎大到原始容量「两倍」，并将原有的数据复制过来
HashMap 装载因子默认值为 0.75，默认容量是 16

static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

HashMap 常用方法：

方法描述
Object put(Object key,Object value)将指定 k-v 添加（或修改）当前 map 对象中
void putAll(Map m)将m中的所有 key-value 对存放到当前 map 中
V get(Object key)返回 key 所对应的 value
void clear清空 Map
Object clone()返回当前映射的克隆
boolean constainsKey(Object key)是否包含指定 key，有返回 true，否则返回 false
containsValue(Object value)是否包含指定 value，有返回 true，否则返回 false
boolean isEmpty()若 map 中不含 k-v，返回 true，否则返回 false
V remove(Object key)删除 key 所以对应的 k-v 对，并返回 key 所对应 value 值
int size()返回 map 的大小，即 k-v 个数
boolean equals(Object obj)判断当前map和参数对象obj是否相等
Set keySet()返回所有 key 构成的 Set 集合
Collection values()返回所有 value 构成的 Collection 集合
Set entrySet()返回所有 k-v 对构成的 Set 集合

HashMap 的遍历：

Map map = new HashMap();
map.put("AA",123);

// 遍历所有的 key
Set set = map.keySet(); // 获取 key 集合
Iterator iterator = set.iterator();
while (iterator.hasNext()){
    System.out.println(iterator.next());
}

// 遍历所有的 values 
Collection coll = map.values(); // 获取 values 集合
for(Object obj: coll){
    System.out.println(obj);
}

// 遍历所有的 key-value
// 方式一:
Set entrySet = map.entrySet(); // 获取 k-v（entry）集合
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
    Object obj = iterator1.next();
    Map.Entry entry = (Map.Entry) obj; // 获取每个 entry
    System.out.println(entry.getKey()+"--->"+entry.getValue());
}
// 方式二:
Set set1 = map.keySet(); // 获取 key 集合
Iterator iterator2 = set.iterator();
while (iterator2.hasNext()){
    Object key = iterator2.next();
    Object value = map.get(key);
    System.out.println(key+"--->"+value);
}

3、HashMap 的底层实现原理

以 jdk7 为例说明：
HashMap map = new HashMap():

  • 实例化后底层创建了长度是 16 的一维数组 Entry[] table
    map.put(key1,value1):
  • 首先，调用 key1 所在类的 hashCode() 计算 key1 哈希值，得到在 Entry 数组中的存放位置。
    • 若此位置为空，添加成功。
    • 若此位置上数据不为空，比较 key1 和已存在数据的哈希值：
      • 若哈希值不相同，添加成功。
      • 若哈希值相同：调用 key1 所在类的 equals() 方法：
        • 若 equals() 返回 false：添加成功
        • 若 equals() 返回 true：使用 value1 替换 value2

补充：情况 2,3 数据以链表方式存储
在不断添加过程中，涉及到扩容问题：扩容为原来的两倍，并将原有的数据复制过来。

jdk8 相较于 jdk7 在底层实现方面的不同：

  1. new HashMap()：底层没有创建长度为 16 的 Entry 数组
  2. jdk8 底层数组是 Node[]数组 ，而非 Entry[] 数组
  3. 首次调用 put 方法时，底层创建长度为 16 的数组
  4. jdk7 底层结构只有：数组 + 链表。jdk8 底层结构：数组 + 链表 + 红黑树
    当数组的某一个索引位置上元素以链表形式存在的数据个数 >8 且当前数组的长度 >64 时，此索引位置上的所有数据改为使用红黑树存储。

HashMap 源码中的重要常量 ：

  • DEFAULT_INITIAL_CAPACITY : HashMap 的默认容量， 16
  • MAXIMUM_CAPACITY ： HashMap 的最大支持容量， 2^30
  • DEFAULT_LOAD_FACTOR： HashMap 的默认加载因子：0.75
  • TREEIFY_THRESHOLD： Bucket 中链表长度大于该默认值，转化为红黑树:8
  • MIN_TREEIFY_CAPACITY： 桶中的 Node 被树化时最小的 hash 表容量。：64
  • threshold： 扩容的临界值， = 容量 * 填充因子

4、TreeMap 两种添加方式的使用

向 TreeMap 中添加 key-value，要求 key 必须是由同一个类创建的对象
因为要按照 key 排序：自然排序、定制排序

相关信息

关于 compareTo()：

@Override
public int compareTo(Object o) {
    // return this.age - ((Person) o).age; // 从小至大
    return ((Person) o).age - this.age; // 从大至小
}

public class TreeMapTest {
    //自然排序（Person 类实现 comparable 接口）
    @Test
    public void test(){
        TreeMap map = new TreeMap();
        map.put(new Person("DD",22),123);
        map.put(new Person("BB",20),123);
        map.put(new Person("CC",18),123);
        map.put(new Person("AA",17),123);

        Set entrySet = map.entrySet();
        Iterator iterator = entrySet.iterator();
        while (iterator.hasNext()){
            Object obj = iterator.next();
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey()+"---"+entry.getValue());
        }
    }
    //定制排序
    @Test
    public void test2(){
        TreeMap map = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Person && o2 instanceof Person){
                    Person p1 = (Person) o1;
                    Person p2 = (Person) o2;
                    return Integer.compare(p1.getAge(),p2.getAge());
                }
                throw new RuntimeException("");
            }
        });
        map.put(new Person("DD",22),123);
        map.put(new Person("BB",20),123);
        map.put(new Person("CC",18),123);
        map.put(new Person("AA",17),123);
        Set entrySet = map.entrySet();
        Iterator iterator1 = entrySet.iterator();
        while (iterator1.hasNext()){
            Object obj = iterator1.next();
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey()+"---"+entry.getValue());
        }
    }
}

5、Properties

Properties：用来处理配置文件。key和value都是String类型

public class PropertiesTest {
    public static void main(String[] args) {
        FileInputStream fis = null;
        try {
            Properties pros = new Properties();
            fis = new FileInputStream("jdbc.properties");
            pros.load(fis);//加载流对应文件

            String name = pros.getProperty("name");
            String password = pros.getProperty("password");

            System.out.println(name+password);
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if(fis != null){
                try {
                    fis.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

9、Collections 工具类

Collections 是一个操作 Set、 List 和 Map 等集合的工具类

  • reverse(List)： 反转 List 中元素的顺序
  • shuffle(List)： 对 List 集合元素进行随机排序
  • sort(List)： 根据元素的自然顺序对指定 List 集合元素按升序排序
  • sort(List， Comparator)： 根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
  • swap(List， int， int)： 将指定 list 集合中的 i 处元素和 j 处元素进行交换
  • Object max(Collection)： 根据元素的自然顺序，返回给定集合中的最大元素
  • Object max(Collection， Comparator)： 根据 Comparator 指定的顺序，返回给定集合中的最大元素
  • Object min(Collection)
  • Object min(Collection， Comparator)
  • int frequency(Collection， Object)： 返回指定集合中指定元素的出现次数
  • void copy(List dest,List src)：将src中的内容复制到dest中
  • boolean replaceAll(List list， Object oldVal， Object newVal)： 使用新值替换List 对象的所有旧值

Collections 类中提供了多个 synchronizedXxx() 方法，该方法可使将指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题

0  字
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.15.5
T4mako's blog
Copyright © 2024 T4mako