Java集合
单列集合
数据存储在一列，继承Collection接口
Collection
- List：存储列表数据
- ArrayList：底层数组实现，查询快
- LinkedList：底层双向链表实现，增删快
- Vector：底层数组实现，操作方法被
synchronized修饰，线程安全
- Set：存储不重复的数据
- HashSet：底层HashMap实现
- LinkedHashSet：继承HashSet，依靠链表维护元素顺序
List
ArrayList
从名字可以看出ArrayList是数组列表，实现了List接口
这个类中 使用数组Object[] elementData 存储数据
ArrayList常用方法
- void add(E element)：末位插入
- void add(int index, E element)：index处插入
- boolean addAll(Collection<? extends E> c)：末位插入同类型的的一个列表
- boolean addAll(int index, Collection<? extends E> c)：index处插入同类型的的一个列表
- E remove(int index)：删去index位置的元素
- boolean remove(Object o)：删去第一次出现的元素o
- int size()：返回列表长度
- void clear()：清空list元素
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Vector;
public class TestList {
public static void main(String[] args) {
ArrayList<String> list0 = new ArrayList<>();
list0.add("x");
list0.add("y");
list0.add("z");
ArrayList<String> list = new ArrayList<>();
list.add("1"); // 尾插
list.add("3");
list.add("4");
list.add(1,"2"); // 在索引1的地方插入 1,2,3,4
list.addAll(list0); // 末位插入列表list0 1,2,3,4,x,y,z
list.addAll(0, list0); // 在位置0（头部）插入列表list0 x,y,z,1,2,3,4,x,y,z
System.out.println(list);
list.remove(2); // 移除位置2 的元素
list.remove("x"); // 移除第一次出现的x
System.out.println(list);
System.out.println(list.size()); // 输出列表长度
list.clear(); // 清空列表，
System.out.println(list);
}
}
LinkedList
从名字可以看出ArrayList是链表列表，实现了List接口
常用API方法与ArrayList相似
类中定义了头尾两个节点，数据插入在两个节点中间
transient Node<E> first;
transient Node<E> last;
Vector
底层数组实现，与ArrayLis相同，操作方法被synchronized修饰，线程安全
Object[] elementData 数组对象存储元素，与ArrayList
ArrayList、LinkedList、Vector区别
-
数据结构
- ArrayList、Vector：数组
- LinkedList：双向链表
-
元素访问效率
- ArrayList最快，通过索引，O(1)级别访问
- Vector次之，O(1)级别访问，
synchronized会伴随性能开销 - LinkedList最慢，O(n)级别访问
-
元素插入效率
- LinkedList最快，头、尾O(1)级别插入，其他位置O(n)
- ArrayList次之，尾O(1)级别插入，其他O(n)，因为数组插入需要移动元素，会更慢
- Vector最后
-
线程安全
- Vector线程安全
- 其他非线程安全
-
扩容机制
- ArrayList，数组容量满了1.5倍扩容
- Vector，数组容量满了2倍扩容
- LinkedList，链表不存在扩容
Set
存储不重复的数据的列表，元素之间没有特定的顺序
HashSet
基于哈希表的原理来实现元素的快速添加、删除和查找等操作
底层是利用HashMap来实现的（先了解HashMap）
这使得元素的添加、删除和查找操作在理想情况下（哈希冲突较少时）能达到接近常数时间复杂度，即 O (1)
常用方法
- boolean add(E e)：插入
- boolean remove(Object o)：删除
- int size()：元素个数
- void clear()：清空
import java.util.HashSet;
public class TestSet {
public static void main(String[] args) {
HashSet<String> set = new HashSet<>();
set.add("Java");
set.add("Python");
set.add("C++");
set.add("C++"); // 重复,无效
System.out.println(set);
System.out.println(set.size());
}
}
LinkedHashSet
LinkedHashSet 继承自 HashSet，既拥有 HashSet 的高效去重特性，又额外维护了元素的插入顺序。它通过在底层结合 HashMap 和双向链表来实现这一功能
内部同样使用 HashMap 来存储元素，以保证元素唯一性
维护了一个双向链表，用于记录元素的插入顺序
双列集合
Map：（key, value）键值对的存储方式
- HashMap：底层数组+链表实现
- TreeMap：底层红黑树实现
HashMap
实现了Map接口
HashMap的底层数据结构在 Java 8 之前主要是数组 + 链表的形式，自 Java 8 起则采用了数组 + 链表 + 红黑树的结构
初始长度16
链表用于存储哈希值相同的不同键值对，也就是在发生哈希冲突时发挥作用
HashMap.java 395行
1791行
transient Node<K,V>[] table：table数组存储，由此可知，数组的每一个元素都是链表头节点（大概图示）
具体实现挺复杂，大概是这个意思，过（给我整笑了）
储存<key, value>键值对的元素，key类似索引，value表示索引处的值
常用API方法
- V put(K key, V value)：尾插入
- V remove(Object key)：删除key值为key的元素
- V replace(K key, V value)：替换key处元素的内容
- int size()：返回HashMap的元素个数
- void clear()：清空HashMap
import java.util.HashMap;
public class TestHashMap {
public static void main(String[] args) {
HashMap<String, String> hashMap = new HashMap<>();
hashMap.put("科目一","Java");
hashMap.put("科目二","C++");
hashMap.put("科目三","Go");
// 重复的key值"科目三"，相当于更新key"科目三"的值,"科目三"更新为"Python"
hashMap.put("科目三","Python");
hashMap.remove("科目三");
System.out.println(hashMap);
System.out.println(hashMap.size()); // 获取元素个数
hashMap.clear(); // 清空map
System.out.println(hashMap.size());
}
}
key重复
HashMap为了保证key的唯一，有重复的key，将覆盖以往的key，之前的key不复存在
哈希冲突
HashMap（进而HashSet）在添加元素时会通过计算元素的哈希值来确定元素在底层存储结构中的位置。如果不同元素计算出的哈希值相同，就会产生哈希冲突
方法：采用了链地址法（也叫拉链法），即当发生哈希冲突时，会在对应哈希桶（通过哈希值确定的存储位置）位置形成一个链表（在 Java 8 及以后，如果链表长度达到一定阈值，会转化为红黑树来提高性能），将具有相同哈希值的元素依次存储在这个链表（或红黑树）中
HashMap特点
优点：快速查询、插入、删除
缺点：无序、非线程安全
TreeMap
黑树来存储键值对，红黑树的每个节点对应一个键值对，
数据结构的知识忘了差不多了，待续…