Glonkkkkk' Blog
0%

集合

发表于 更新于 分类于

集合

理解底层机制、看源代码，集合的应用

可以动态保存任意多个对象，使用方便 一系列操作对象的方法：增删改查，add、remove、set、get

ch14-集合类图
ch14-集合类图

集合框架体系

​ 单列集合

  • List
    • Vector
    • ArrayList
    • LinkedList
  • Set
    • TreeSet
    • HashSet

Map双列集合，存放K-V

  • HashMap
    • LinkedHashmap
  • Hashtable
    • Properties
  • TreeMap

Collection

接口实现类的特点： 可以存放多个元素，每个元素可以是Object 有些实现类可以存放重复的元素，有些不可以 有些实现类是有序的，有些是无序的 Collection接口没有直接的实现子类，是通过它的子接口Set和List来实现的。

  • 常用方法，以ArrayList为例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 创建
List list = new ArrayList();
// 添加元素->转换成对象
list.add("zzh");
// 删除
list.remove(Object o);// 指定删除某个元素
list.remove(0);// 按index删除
// 查找某个元素是否存在
list.contains("zzh");
// 获取元素个数
list.size();
// 判断是否为空
list.isEmpty();
// 清空
list.clear();
// 添加多个元素
list.addAll(list2);
// 查找多个元素是否都存在
list.containsAll(list2);
// 删除多个元素
list.removeAll(list2)

遍历元素方式

  • 使用迭代器

Iterator是一个迭代器，主要用于遍历集合中的元素。仅用于遍历集合，本身不存放对象。

tips：显示所有快捷键，CTRL+J： itit：while迭代 I:for迭代

1
2
3
4
5
6
7
8
9
10
// 得到一个集合的迭代器
Iterator iterator = coll.iterator();
// 判断是否还有下一个元素
iterator.hasNext();
// 下移，返回下一个元素
iterator.next();
// 使用范例：退出迭代循环后，迭代器指向最后的元素。
while(iterator.hasNext()){
    Object obj = iterator.next();
}
  • 增强for循环

可以用在集合和数组上使用，底层仍是迭代器

1
for(Object o : col)
List

集合类中元素有序，有对应的索引，且可重复。 常用类：Vector、ArrayList、LinkedList 常用方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
List list = new ArrayList();
// 在指定位置index插入元素obj
list.add(int index, Object obj);
// 获取指定index位置的元素
list.get(Object obj);
// 返回集合中元素首次出现的位置
list.indexOf(Object obj);
// 删除指定位置的元素
list.remove(int index);
// 删除指定元素
list.remove(object o);
// 替换指定位置的元素
list.set(int index, Object obj);
// 返回子集合
list.subList(int fromIndex, int toIndex);

三种遍历方式： 使用iterator、使用增强for、使用普通for（视作数组）

  • ArrayList

注意事项： 可以加入空元素，是由数组实现数据存储的。 基本等同于Vector，但ArrayList执行效率高、线程不安全

源码分析： 底层维护Object数组elementData。 创建对象时如果使用无参构造器，则初始容量为0；第一次添加时，扩容为10；再次扩容为1.5倍 如果使用指定大小的构造器，则初始容量确定；再次扩容为1.5倍

  • Vector

底层也是一个对象数组。 线程安全，支持线程同步和互斥。

扩容机制源码分析： 创建对象时如果使用无参构造器，则初始容量为10；再次扩容为2倍 如果使用指定大小的构造器，则初始容量确定；再次扩容为2倍

  • LinkedList

底层实现了双向链表和双端队列，可以添加任何元素（可重复、可空），线程不安全、没有同步机制 LinkedList维护了first、last，分别指向首节点和尾节点。 每个节点维护prev、next、item单个属性，通过prev指向前一个，next指向后一个节点。

  • list的选择： 查改较多，选择ArrayList 增删较多，选择LinkedList
Set

基于HashMap实现，集合类中元素无序、没有索引，不允许重复的元素，最多包含一个null。 常用类：HashSet、TreeSet 常用方法：和Collection接口相同。 遍历方式：迭代器、增强for

1
2
3
4
5
6
7
8
9
10
11
12
13
// 创建
Set set = new HashSet();
// 增加元素
set.add("john");
set.add("lucy");
// 遍历
Iterator iterator = set.iterator();
while(iterator.hasNext()){
    Object object = iterator.next();
}
for(Object o : set){
    sout(o);
}
  • HashSet

实现了Set接口，底层实际上是HashMap（数组+链表+红黑树），存储效率高。

元素添加的逻辑： 1.先得到元素的hash值，转换成索引值 2.在存储表的索引位置，看这个位置是否有已经存放的元素 3.如果没有，元素直接加入存储表；如果有，则进行hash值和equals比较，不相同则添加到最后；都相同则不添加。 4.当链表元素超过8，table元素超过64时，则自动进行树化；否则仍采用数组扩容机制

源码解读： 1.首先生成HashMap(); 2.执行add() 3.执行put，方法会执行hash(key)得到key对应的hash值 4.

扩容机制： 1.第一次添加时，数组扩容到16，到达临界值16*0.75时，扩容为16x2；以此类推 2.达到树化条件的时候进行树化。

  • LinkedHashSet

是HashSet的子类，底层是LinkedHashMap，维护一个数组+双向链表 根据元素的hashCode值来决定元素的存储位置，同时用链表维护元素的次序，保证存取的有序。

元素添加的逻辑： 1. 添加元素：先求hash值，再求索引确定元素在table中的位置，然后将添加的元素加入到双向链表 2. 可以保证插入的顺序和遍历顺序一致。

  • TreeSet

默认是无序的；可以通过调用有参构造器，传入比较器（匿名内部类）来指定排序规则。

Map

双列元素，用于保存具有映射关系的数据key-value key和value是任何引用类型的数据，会封装到HashMap$Node对象中 key不可以重复，value可以重复；出现相同的key会发生替换 常用String类作为key，key-value之间存在单向一对一关系，通过指定的key找到对应的value

1
2
3
4
5
// 创建
Map map = new HashMap();
// 增加元素
map.put("key1","value1");
map.put("key2","value2");
HashMap
  • 常用方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 创建
Map map = new HashMap();
// 添加元素
map.put("zzh",18);
map.put("jcc",18);
map.put("jcc",19);
System.out.println(map);
// 根据键删除映射关系
map.remove("zzh");
// 根据键获取值
map.get("jcc");
// 获取元素个数
map.size();
// 判断个数是否为0
map.isEmpty();
// 清除k-v
map.clear();
// 查找键是否存在
map.containsKey("jc");
// 把所有的values取出
  • 遍历方式
  1. containsKey：查找键是否存在
  2. keySet：获取所有的键
  3. entrySet：获取所有关系的k-v
  4. values：获取所有的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 1.先取出所有的key，通过key取出对应的value
Set keyset = map.keySet();
// (1)增强for
for(Object key: keyset){
    map.get(key);
}
// (2)迭代器iterator
iterator iterator = keyset.iterator();
while (iterator.hasNext()) {
    Object key =  iterator.next();
    map.get(key);
}
// 2.把所有的values取出后遍历
// (1)增强for (2)迭代器iterator
Collection values = map.values();
for(Object o : values){
    System.out.println(o);
}
// 3.通过EntrySet，来取出k-v
// (1)增强for (2)迭代器iterator
Set entrySet = map.entrySet();
for(Object entry : entrySet){
    // entry向下转型
    Map.Entry m = (Map.Entry) entry;
    m.getKey();
    m.getValue();
}

不保证映射的顺序，底层是以hash表的方式存储。没有实现同步，线程不安全。

  • 元素添加的逻辑： 1.先得到key元素的hash值，转换成索引值 2.在存储表的索引位置，看这个位置是否有已经存放的元素 3.如果没有，元素直接加入存储表；如果有，则对key值进行hash值和equals比较，不相同则添加到最后；都相同则替换value值。 4.当链表元素超过8，table元素超过64时，则自动进行树化；否则仍采用数组扩容机制

  • 扩容机制：和HashSet完全一致 1.第一次添加时，数组扩容到16，到达临界值16*0.75时，扩容为16x2；以此类推 2.达到树化条件的时候进行树化。

HashTable

存放K-V键值对，键和值都不能为空。 使用方法基本和HashMap一样，但sync线程安全、效率低。 根据扩容机制进行扩容：初始大小为11，临界值为8，按照2n+1进行扩容。

Properties

继承自HashTable，并且实现了Map接口,也是使用键值对存放数据。 使用特点和HashTable类似。 可以用于从.properties文件中加载数据到Properties类对象。

TreeMap

默认是无序的；可以通过调用有参构造器，传入比较器（匿名内部类）来指定K的排序规则。

如何选择集合实现类

主要取决于业务操作特点，然后根据集合实现类特性进行选择。

  1. 先判断存储类型（单列 or 键值对）
  2. 一组对象：Collection接口 允许重复：List 增删多：LinkedList、改查多：ArrayList 不允许重复：Set 无序：HashSet、排序：TreeSet、插入和取出顺序一致：LinkedHashSet
  3. 一组键值对：Map 键无序：HashMap、键排序：TreeMap、插入和取出顺序一致：LinkedHashMap 读取文件：Properties

Collections工具类

是一个操作Set、List和Map等集合的工具类，可以对集合元素进行排序、查询和修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//创建ArrayList 集合，用于测试.
List list = new ArrayList();
list.add("tom");
list.add("smith");
list.add("king");

// 反转字符串
Collections.reverse(list);
// 自然排序
Collections.sort(list);
// 交换指定位置
Collections.swap(List, i, j);
// 根据元素的自然顺序，返回给定集合中的最大元素
Collections.max(list)    
// 指定顺序排序，使用匿名内部类加入比较器
// 指定集合中指定元素的出现次数 
Collections.frequency(list, "tom"));
// 拷贝 将list中的内容复制到dest中，需要将dest大小扩充到和list一致
Collections.copy(dest, list);
// 将list中的oldVal替换为newVal
Collections.replaceAll(list, oldval, newVal);