JavaSE第十一天——集合框架Collection

一、List接口

List接口是一个有序的集合，允许元素有重复，它继承了Collection接口，提供了许多额外的功能，比如基于索引的插入、删除和访问元素等。

常见的List接口的实现类有ArrayList、LinkedList和Vector。

List接口的实现类

1、ArrayList

• 底层基于数组实现，查询效率高，增删效率低（因为需要移动元素）。

• 线程不安全，但性能较高。

• 适用于需要频繁查询的场景。

2、LinkedList

• 底层基于双向链表实现，查询效率低（需要从头或尾遍历），增删效率高。

• 提供了额外的头尾操作方法，如addFirst(), addLast(), getFirst(), getLast(), removeFirst(), removeLast()等。

• 线程不安全。

• 适用于需要频繁增删的场景，尤其是首尾操作。

List接口的主要方法

• void add(int index, E element): 在指定位置插入元素。

• E get(int index): 返回指定位置的元素。

• int indexOf(Object o): 返回此列表中指定元素的首次出现的索引，如果此列表不包含该元素，则返回-1。

• int lastIndexOf(Object o): 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含该元素，则返回-1。

• E remove(int index): 移除指定位置的元素。

• boolean contains(Object o): 如果此列表包含指定的元素，则返回true。

• Iterator<E> iterator(): 返回在此列表中的元素上进行迭代的迭代器

 使用注意事项：

使用List集合时，要注意索引越界的问题，即不要访问或操作不存在的索引位置。

在多线程环境下，如果需要对List进行并发操作，需要考虑线程安全的问题，可以选择使用线程安全的实现类。

二、哈希表和Map接口

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构，

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

这个映射函数叫做散列函数，存放记录的数组叫做散列表。

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

• 则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数

Map接口

在Java的集合框架中，Map接口是一种存储键值对（key-value pair）的数据结构；Map不允许出现重复的键（key），但允许多个键映射到相同的值（value）。

Map接口并不继承自Collection接口，而是与Collection接口并行存在，用于处理键值对映射数据；常见的Map接口实现类有HashMap、LinkedHashMap、TreeMap等。

Map接口的实现类

1、HashMap

• 基于哈希表实现，允许null键和null值。

• 不保证映射的顺序，特别是它不保证该顺序恒久不变。

• 性能通常优于Hashtable和TreeMap。

2、LinkedHashMap

• 类似于HashMap，但遍历顺序是按照键值对插入到映射中的顺序（插入顺序）或最近最少使用（LRU）顺序。

• 提供了按访问顺序（访问顺序）或插入顺序（插入顺序）遍历映射的方法。

3、TreeMap

• 基于红黑树实现，能够按照键的自然顺序或自定义顺序进行排序。

• 所有的元素都根据键的自然顺序（或创建TreeMap时提供的Comparator进行排序）。

• 适用于需要有序遍历的场景。

Map接口的主要方法

• V put(K key, V value): 将指定的值与此映射中的指定键关联（可选操作）。如果包含一个该键的映射关系，则旧值被替换。

• V get(Object key): 返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回null。

• V remove(Object key): 如果存在一个键的映射关系，则从此映射中移除它（可选操作）。

• boolean containsKey(Object key): 如果此映射包含指定键的映射关系，则返回true。

• boolean containsValue(Object value): 如果此映射将一个或多个键映射到指定值，则返回true。

• int size(): 返回此映射中的键-值映射关系的数量。

• boolean isEmpty(): 如果此映射不包含键-值映射关系，则返回true。

• Set<K> keySet(): 返回此映射中包含的键的Set视图。

• Collection<V> values(): 返回此映射中包含的值的Collection视图。

• Set<Map.Entry<K,V>> entrySet(): 返回此映射中包含的映射关系的Set视图。（每个键值对都是一个 Map.Entry 实例，而 Map.Entry<K,V> 是 Map 接口中的一个静态内部接口。）

三、Set接口

Set接口是一个不包含重复元素的集合，它继承自Collection接口，包含了Collection接口的所有方法，如add(), remove(), contains(), size(), isEmpty()等

Set集合主要用于存储无序且不重复的元素，不保证集合中元素的顺序，某些Set实现类可能会对元素进行排序）

Set接口的实现类

1、HashSet

• 基于哈希表实现，不保证元素的迭代顺序，也不保证元素的顺序在长时间内保持不变。

• 性能通常优于其他Set实现类，因为它提供了常数时间的添加、删除和查找操作。

2、LinkedHashSet

• 类似于HashSet，但迭代顺序是元素插入到集合中的顺序（插入顺序）。

• 在需要保持元素插入顺序的场景中很有用。

3、TreeSet

• 基于红黑树实现，能够对元素进行自然排序或根据创建TreeSet时提供的Comparator进行排序。

• 适用于需要有序集合的场景。

Set接口的主要方法

• boolean add(E e): 如果此集合尚未包含指定元素，则添加指定元素。
• boolean addAll(Collection<? extends E> c): 如果指定集合中的所有元素都尚未添加到此集合中
• boolean contains(Object o): 如果此集合包含指定的元素，则返回true。
• boolean containsAll(Collection<?> c): 如果此集合包含指定集合中的所有元素，则返回true。
• boolean removeAll(Collection<?> c): 移除此集合中那些也包含在指定集合中的所有元素（可选操作）。
• boolean retainAll(Collection<?> c): 仅保留此集合中也包含在指定集合中的元素（可选操作）。

注意事项：

1、在使用Set集合时，要注意集合中元素的唯一性，不要添加重复的元素。

2、如果需要在集合中保持元素的插入顺序或进行排序，请选择适当的Set实现类（如LinkedHashSet或TreeSet）。

3、在多线程环境下使用Set集合时，需要考虑线程安全的问题。

4、如果需要线程安全的Set集合，可以使用Collections.synchronizedSet()方法

 四、迭代器 Iterator

容器里面很多元素，如果需要遍历里面的元素，应该怎么操作？我们可以使用循环遍历集合：普通for循环 和 增强for循环，也可以使用Iterator来遍历。

Iterator是java中的一个接口，核心作用就是用来遍历容器的元素，当容器实现了Iterator接口后，可以通过调用容器里面的Iterator()方法获取一个 Iterator对象；迭代器本身并不属于集合结构的一部分，而是用于遍历集合的工具。

那为啥是调用容器里面的Iterator方法呢？因为容器的实现有多种，不同的容器遍历规则不一样，比如ArrayList/LinkedList/HashSet/TreeSet等，为了能够顺序地访问一个集合（Collection）的元素，而又不需要知道该集合的底层表示。所以设计了Iterator接口，让容器本身去实现这个接口，实现里面的方法，从而让开发人员不用关系容器的遍历机制，直接使用对应的方法即可。

三个核心方法

• boolean hashNext() ：用于判断iterator内是否有下个元素，如果有则返回true，没有则false

• Obejct next()：返回iterator的下一个元素，同时指针也会向后移动1位

• void remove()：删除指针的上一个元素（容易出问题，删除元素不建议使用容器自己的方法）

使用迭代器的步骤

1、获取迭代器对象 

• 通过调用集合的iterator()方法，我们可以获取到该集合的迭代器对象。

• ElementType 是集合中元素的类型，collection 是需要遍历的集合对象。

Iterator<ElementType> iterator = collection.iterator();

2、判断迭代器中是否还有元素

• 使用iterator.hasNext()方法来判断迭代器中是否还有下一个元素

while (iterator.hasNext()) {  
    // 迭代器中还有元素  
}

3、访问集合中的元素

• 使用iterator.next()方法来获取迭代器中的下一个元素。

• 在调用next()方法之前，必须确保迭代器中还有元素，否则会抛出NoSuchElementException异常

ElementType element = iterator.next();

4、安全地遍历集合

• 在遍历集合的过程中，如果需要删除某个元素，应该使用迭代器的remove()方法，而不是集合的remove()方法

• 直接使用集合的remove()方法会导致在并发修改集合的情况下抛出ConcurrentModificationException异常。

if (someCondition) {  
    iterator.remove(); // 删除当前元素  
}

注意：迭代器遍历集合时，只能单向遍历，无法从后往前遍历。