Java集合
1. 单列集合
- 单列集合体系结构（继承/实现关系）：
- 一、
Collection 接口：
- 1. List 接口
- ArrayList 实现类
- LinkedList 实现类
- Vector 实现类（已淘汰）
- 2. Set 接口
- HashSet 实现类
- LinkedHashSet 实现类
- TreeSet 实现类
- List系列集合：添加的元素是有序（存取顺序），可重复，有索引的。
- Set 系列集合：添加的元素是无序（存取顺序），不重复，无索引的。
①Collection使用方法
Collection 接口
- Collection 接口：单列集合的顶层父接口，它的功能是所有单列集合都可以继承使用的。
- 功能：
public boolean add(E e)：把给定的对象添加到集合中去。public void clear()：清空集合中所有元素。public boolean remove(E e)：把给定对象在当前集合中删除。public boolean contains(Object obj)：判断当前集合中是否包含给定对象。public boolean isEmpty()：判断当前集合是否为空。public int size()：返回当前集合中元素的个数。
②Collection遍历方法
迭代器遍历：
- 迭代器在Java中的类是
Irerator,迭代器是集合专用的遍历方式。 - Collection集合获取迭代器：
Iterator<E> iterator()返回迭代器对象，默认指向当前集合的0索引。
- Iterator常用方法：
boolean hasNext()：判断当前位置是否有元素，有返回true，无返回false。E next：获取当前位置元素，并将迭代器对象移动到下一个位置。
//迭代器遍历示例： List<String> list = new ArrayList<>(); //list.add()...装入数据 Iterator<String> iterator = list.iterator(); while(iterator.hasNext()){ //当前位置有无元素？ String str = iterator.next(); //获取当前位置元素，指向下一位置 System.out.println(str); //打印 //iterator.remove(); 删除 }
- Coding细节：
- 1.迭代器遍历完毕指针不会复位
- 2.遍历到不存在元素的位置，继续遍历会报错NoSuchElementException
- 3.为保证正确遍历，循环中只能使用一次next()方法
- 4.迭代器遍历时，不能用集合的方法进行增加或删除操作（可使用迭代器自带的remove()方法进行删除）
增强for循环遍历：
- 增强for循环的底层就是迭代器，简化了迭代器的代码书写。
- 出现在JDK5之后，内部原理就是一个Iterator迭代器。
- 所有的单列集合和数组可以用增强for循环进行遍历。
Collection<String> coll = new ArrayList<>(); coll.add("zhangsan"); coll.add(".29."); coll.add("ebb29bbe"); //增强for for(String str : coll){ System.out.println(str); }
利用lambda表达式遍历：
Collection<String> coll = new ArrayList<>(); coll.add("zhangsan"); coll.add(".29."); coll.add("ebb29bbe"); //遍历 coll.forEach( str -> System.out.println(str) );
③List使用方法
List接口：
- Collection集合的方法，List都继承了。
- List集合有索引，所以多了索引操作的相关方法。
- 索引相关方法：
void add(int index,E element)：在集合指定位置插入元素。E remove(int index)：删除指定索引位置的元素，返回被删除的元素。E set(int index,E element)：修改指定索引位置的元素，返回被修改的元素。E get(int index)：返回指定索引位置的元素。
④List遍历方法
迭代器：参照Collection集合增强for循环：参照Collection集合Lambda表达式：参照Collection集合列表迭代器：
List<String> list = new ArrayList<>(); list.add("ebb29bbe"); ListIterator<String> iterator = list.listIterator(); while(iterator.hasNext()){ String str = iterator.next(); //可在遍历过程新增元素 iterator.add(".29."); } //遍历到末尾，可使用方法从后往前遍历 while(iterator.hasPrevious()){ String str = iterator.previous(); //可在遍历过程新增元素 iterator.add(".29."); }
for循环：
List<String> list = new ArrayList<>(); list.add("ebb29bbe"); for(int i = 0;i < list.size(); ++i){ String str = list.get(i); System.out.println(str); }
⑤ArrayList底层原理
ArrayList底层原理：
- ①利用空参创建的ArrayList集合，在底层创建一个默认长度位0的数组。
- ②添加第一个元素时，底层会创建一个新的长度为10的数组。
- ③长度10的数组存满时，扩容1.5倍。
- ④如果依次添加多个元素，1.5倍扩容不够用，则新创建的数组长度以实际为准。
⑥LinkedList使用方法
LinkedList使用:
- LinkeList底层数据结构时双链表，查询慢，增删快，如果操作的是首尾元素，速度也是极快的。
- LinkedList特有方法：
public void addFirst(E e)：在列表开头插入指定元素public void addLast(E e)：将指定元素追加到列表末尾public E getFirst()：返回列表中的第一个元素public E getLast()：返回列表中的最后一个元素public E removeFirst()：从列表中删除并返回第一个元素public E removeLast()：从列表中删除并返回最后一个元素
⑦Iterator 底层原理
Iterator底层原理：
- ①创建
Iterator实例，底层就是创建了一个Iterator内部类的对象，这个内部类就代表迭代器。 - 内部类对象创建时，会用一个属性记录集合被操作的次数（modCount：每一次add和remove这个变量都会自增）。
- ②
hasNext()底层就是用当前索引与集合长度作比较，索引不等于长度就返回true，否则返回false。 - ③
next()底层最开始会验证当前集合操作次数与开始记录的操作次数是否一致，不一致说明迭代器使用期间使用了集合的方法进行新增/删除，进而抛出并发修改异常（ConcurrentModificationExcelption）。 - 结论：如何避免并发修改异常？ 就是在迭代器或增强for遍历集合时，避免使用集合的方法进行新增/修改。
⑧Set集合
- Set系列集合特点：
- 无序、不重复、无索引
- Set集合方法基本与Collection集合方法一致
- Set集合实现类特点:
- ①HashSet：存取无序、不重复、无索引
- ②LinkedHashSet：存取有序、不重复、无索引
- ③TreeSet：可排序、不重复、无索引
⑨HashSet底层原理
- 哈希值：
- 根据 hashCode()方法 计算出来的int类型整数
- hashCode() 定义在Object类中，所有类都可以调用，默认使用地址值进行计算。
- 一般情况下会重写hashCode()，利用对象内部的属性值计算哈希值。
- 对象的哈希值特点：
- 如果没有重写
hashCode()，不同对象计算出的哈希值是不同的。 - 若已经重写
hashCode()，不同的对象属性值相同时，计算出的哈希值相同。 - 哈希碰撞：小概率事件，不同的属性值或者不同的地址值，计算出来的哈希值有可能相同。
HashSet底层原理:
集合方法基本与Collection集合方法一致
- ①HashSet集合底层采用哈希表存储数据。
- ②哈希表是一种对增删改查数据性能都较好的数据结构。
- ③哈希表组成：
JDK8之前：数组 + 链表JDK8开始：数组 + 链表 + 红黑树- 底层原理：
- 实例化时，底层创建一个默认长度16、默认加载因子0.75的数组，名为table。（扩容机制：元素个数 >= 数组长度 * 0.75 后，长度扩容为原本的两倍 ）
- 新增元素时，根据元素的哈希值以及数组的长度计算出相应的位置：
int index = (数组长度 - 1) & 哈希值; - 计算出应存入的索引后，判断索引位置是否为
null，如果是就直接存入。 - 如果不为
null，通过equals() 比较属性值，属性值一致不会存入数据，属性值不一致时，存入索引位置，形成链表。 JDK8之前：新元素存入数组，老元素挂在新元素下面。JDK8开始：新元素直接挂在老元素下面。（当链表长度大于8而且数组长度大于等于64时，当前链表会自动转换成红黑树存储数据）
- 注意：如果集合中要存储的是自定义对象时，一定要重写equals() 和 hashCode()。
问题一：HashSet为什么存取顺序不一致：底层数组存储的是链表，而遍历这些链表时，与存储数据时的顺序很可能不一致。问题二：HashSet为什么没有索引：底层时数组+链表+红黑树，很难去规定索引。问题三：HashSet是利用什么机制保证数据去重的？利用hashCode方法和equals方法保证去重，因为方法重写后，属性值一致的对象哈希值一致，存放的位置一致，若equals比较到相同，会不做存入操作。
⑩LinkedHashSet底层原理
LinkedHashSet底层原理：
集合方法基本与Collection集合方法一致
- 存取有序、不重复、无索引
- LinkedHashSet可以保证存储和取出时元素的顺序一致。
- 底层原理： LinkedHashSet底层依旧是哈希表，但是每个元素又额外多出一个双链表的机制来记录存储的顺序，其余与HashSet原理一致。
- 注意：如果集合中要存储的是自定义对象时，一定要重写equals() 和 hashCode()。
⑩① TreeSet集合
TreeSet：
集合方法基本与Collection集合方法一致
- 不重复、无索引、可排序（按照元素大小自然排序）。
- 对于数值类型：Integer、Double、，默认按照大小自然排序。
- 对于字符、字符串类型：按照字符再ASCII码表中对于的数值进行升序排序。
- TreeSet集合底层时基于红黑树的数据结构实现排序的，增删改查的性能都比较好。
2. 双列集合
双列集合特点：
- ①双列集合一次需要存储一对数据，分别为键和值。
- 键不能重复，值可以重复。
- 键和值是一一对应的，每一个键只能找到自己对应的值。
- 键和值这个整体，我们称之为 键值对 或 键值对对象，Java中叫做”Entry对象“。
①Map使用方法
Map集合：
- Map集合是双列集合的顶层接口，它的功能是全部双列集合都可以继承使用的。
- 使用：
V put(K key,V value)：添加元素V remove(Object key)：根据键删除键值对void clear()：移除所有的键值对boolean containsKey(Object key)：判断集合中是否包含指定键boolean cintainsValue(Object value)：判断集合中是否包含指定值boolean isEmpty()：判断集合是否为空int size()：集合的长度，也就是集合中键值对的个数
②Map遍历方法
通过键找值方式-增强for：
//实例化Map集合 Map<String,String> map = new HashMap<>(); //添加元素： map.put("1","29"); map.put("2","002900"); map.put("3","..29.."); //根据键找值 Set<String> keys = map.keySet();//所有键的set集合 for(String key : keys){ //遍历所有的键 String value = map.get(key); //根据键找值 System.out.println(key + "--" + value); //打印 }
通过键找值的方式，还可以通过迭代器Iterator、Lambda表达式等方式来实现，可参照上文的Collection遍历方式，这里不做补充。
键值对方式 - 增强for：
//实例化Map集合 Map<String,String> map = new HashMap<>(); //添加元素： map.put("1","29"); map.put("2","002900"); map.put("3","..29.."); //键值对方式 Set<Map.Entry<String,String>> entrys = map.entrySet(); for(Map.Entry<String,String> entry : entrys){ String key = entry.getKey(); String value = entry.getValue(); System.out.println(key + "--" + value); //打印 }
Lambda表达式：
//实例化Map集合 Map<String,String> map = new HashMap<>(); //添加元素： map.put("1","29"); map.put("2","002900"); map.put("3","..29.."); //Lambda表达式 map.forEach((key,value)-> System.out.println(key + "--" + value));
③HashMap底层原理
HashMap底层原理:
- ①HashMap是Map里面的一个实现类。
- ②使用方式可以直接参考Map集合。
- ③特点都是与键相关：存取无序、不重复、无索引。
- ④HashMap和HashSet底层原理一致，都是哈希表。
- 哈希值：（复习）
- 根据hashCode()方法计算出来的int类型整数
- **hashCode()**定义在Object类中，所有类都可以调用，默认使用地址值进行计算。
- 一般情况下会重写hashCode()，利用对象内部的属性值计算哈希值。
- 对象的哈希值特点：
- 如果没有重写
hashCode()，不同对象计算出的哈希值是不同的。 - 若已经重写
hashCode()，不同的对象属性值相同时，计算出的哈希值相同。 - 哈希碰撞：小概率事件，不同的属性值或者不同的地址值，计算出来的哈希值有可能相同。
底层原理：
- 实例化时，底层创建一个默认长度16、默认加载因子0.75的数组。（扩容机制：键值对个数 >= 数组长度 * 0.75 后，长度扩容为原本的两倍 ）
- 使用put()新增数据时，底层创建Entry对象存储 键和值，根据键的哈希值以及数组的长度计算出相应的位置：
int index = (数组长度 - 1) & 哈希值; - 计算出应存入的索引后，判断索引位置是否为
null，如果是就直接存入。 - 如果不为
null，通过equals()比较键的值，值一致会进行覆盖(键值对的旧value值被新value值覆盖)，属性值不一致时，存入索引位置，形成链表。 JDK8之前：新元素存入数组，老元素挂在新元素下面。JDK8开始：新元素直接挂在老元素下面。（当链表长度大于8而且数组长度大于等于64时，当前链表会自动转换成红黑树存储数据）
- 依赖hashCode()和equals()保证键的唯一性，如果键存储的是自定义对象，此对象需要重写hashCode()和equals()，值存储的是自定义对象则不需要重写。
④LinkedHashMap集合
LinkedHashMap特点：
- 由键决定：存取有序，不重复，无索引
- 原理：底层数据结构依旧是哈希表（参考HashMap），只是每个键对元素又额外多了一个双链表的机制来记录存储的顺序。
⑤TreeMap集合
TreeMap：
- TreeMap和TreeSet底层原理一致，都是 红黑树结构。
- 由键决定特性：不重复，无索引，可排序。
- 注意：默认按照键从小到大的顺序进行排序，也可以自己规定键的排序规则。
- ①实现Comparable接口，指定排序规则。
- ②创建集合时传递Comparator比较器对象，指定排序规则。
- ③上述两者同时使用，实际会根据方法②的规则排序。
3. Collections工具类
Collections:
- java.util.Collections —— 集合工具类
- Collections不是集合，而是集合的工具类
- 使用:
public static <T> boolean addAll(Collections<T> c,T... elements)：向指定单列集合中批量添加元素。public static void shuffle(List<?> list)：打乱List集合中元素的顺序。public static <T> void sort(List<T> list)：排序。public static <T> void sort(List<T> list,Comparator<T> c)：按照指定规则排序。public static <T> int binarySearch(List<T> list,T key)：通过二分查找法查找元素。public static <T> void copy(List<T> dest,List<T> src)：拷贝集合中的元素。public static<T> int fill(List<T> list,T obj)：使用指定元素填充集合。public static <T> void max(Collection<T> c)：获取默认自然排序后的元素最大值。public static <T> void min(Collection<T> c)：获取默认自然排序后的元素最小值。public static <T> void swap(List<?> list,int i,int j)：交换集合中指定索引位置的元素。
4. 不可变集合
应用场景：
- 如果某个数据不能被修改，把它防御性地拷贝到不可变集合中是个很好的实践。
- 如果集合对象被不可信的库调用时，不可变形式是安全的。
使用：
- 在List、Set、Map接口中都存在静态的of方法，用于获取不可变集合。
- 方法：
static <E> List<E> of(E...elements)：创建一个具有指定元素的List集合对象。static <E> Set<E> of(E...elements)：创建一个具有指定元素的Set集合对象。static <K,V> Map<K,V> of(E...elements)：创建一个具有指定元素的Map集合对象。(传递参数存在上限 - 20个参数，即10个键值对，超过10个需要用ofEntries方法)
注意 —— 上述方式创建的集合的元素不能添加、不能修改、不能删除
