嗯, 实习的时候看到这个, 感觉蛮好, 这里摘录学习, 生活加油:
我曾经害怕别人嘲笑的目光, 后来, 发现他们的目光不会在我身上停留太久, 人们更愿意把目光放在自己身上. 知乎上看到, 讲给自己.
List
List 和 Set 都属于 Collection 的子接口, List 集合中的元素是按照插入顺序进行排列的, 允许出现重复元素,
List 接口下的常用实现类有 ArrayList 和 LinkedList, 对于 List 来讲,
元素只能是通过 set 更新, 不能通过 add 更新, 通过 add 只能在指定索引位置添加元素, 不会实现元素的覆盖, 通过 remove 移除
接口继承关系:
- ArrayList :
- // 查找指定位置元素的下标
- public int indexOf(Object o);
- // 查找指定元素最后一次出现的位置
- public int lastIndexOf(Object o) ;
- // 清空集合元素
- public void clear();
- // 等等......
ArrayList 的特点: **
ArrayList 内部是使用数组来存储数据, 并且是一个 "动态" 的数组, 在添加元素时, 如果发现容量不够时, 会进 行扩容.
ArrayList 支持随机访问元素, 随机访问元素的效率是 O(1)
ArrayList 在尾部添加元素的效率为 O(1),add 方法默认在尾部进行添加, 在使用的时候最好在尾部添加元素 效率更佳
ArrayList 在进行删除元素或者在中间, 头部插入元素时会导致数组内部移动, 进行数组拷贝, 平均时间复杂度 为 O(n)
ArrayList 的迭代方式:
1, 下标迭代
- // 使用下标对 List 进行外部迭代
- for (int i = 0; i <list.size(); i++) {
- System.out.println(list.get(i));
- }
2, 可以使用增强 for 进行迭代
- // 采用增强 for 的迭代方式其实底层是使用迭代器进行迭代, 在迭代的过程中不允许对元素进行修改
- for (String s : list) {
- System.out.println(s);
- }
3, 采用内部迭代的方式
- // 内部迭代 forEach, 在迭代的过程中仍然不允许对元素进行修改过删除操作
- list.forEach(item -> System.out.println(item));
- // 内部迭代还支持并行方式对元素进行迭代 如果数据量非常大的时候可以采用该方式 (一般不采用) 迭代出来的元素可能无序
- list.parallelStream().forEach(System.out::println);
- list.stream().forEach(System.out::print);
4, 内部迭代底层实现
- public void forEach(Consumer<? super E> action) {
- Objects.requireNonNull(action);
- final int expectedModCount = modCount; @SuppressWarnings("unchecked")
- final E[] elementData = (E[]) this.elementData; final int size = this.size;
- for (int i=0; modCount == expectedModCount && i <size; i++) {
- action.accept(elementData[i]);
- }
- if (modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
- }
5, 使用迭代器进行迭代
- // 直接使用迭代器进行迭代 这种迭代方式允许在迭代中对元素进行修改和删除操作
- Iterator<Long> iterator = list.iterator(); while (iterator.hasNext()){
- System.out.println(iterator.next());
- }
几种迭代方式的性能比较
在数据规模为一千万的情况下内部迭代表现较好, 尽管在千万级的数据量并行迭代依然速度不快, 因为在线程的频换 切换和销毁等因素造成了一定的开销.
在百万数据规模的情况下, 增强 for 的性能较好, 可以根据数据量来对元素进行迭代, fori 方式和增强 for 性能差异不是很大.
LinkedList:
LinkedList 继承自 AbstractSequentialList 可以知道 LinkedList 的元素是顺序访问的, 随机访问元素需要对链表进行遍历, 同样实现了克隆和序列化接口 LinkedList 还实现了 Deque 相关的方法, 可以当做一个队列来使用
LinkedList 的类继承关系
LinkedList 的特点:
LinkedList 的内部数据结构是一个双向链表, 有一个头结点和一个尾部节点, 在头部和尾部插入的效率非常高 O(1)
LinkedList 的平均查找效率为 O(n)
LinkedList 的删除和修改都需要先定位元素的位置, 但是对于删除操作本身只需要 O(1)的时间复杂度 LinkedList 因为采用了链表结构, 所以理论空间是没有限制的, 不需要扩容
LinkedList 在使用下标访问元素的时候使用了折半查找, 但是在数据量大的情况下, 查找效率依然很慢 便于用作 LRU
LinkedList 的迭代方式
LinkedList 的迭代方式其实和 ArrayList 大同小异, 但是 ArrayList 在进行 get(index)的操作只需要 O(1)的时间复杂度
所以我们在使用 LinkedList 的时候不采用 fori 形式的遍历
增强 for 方式进行遍历, 其实相当于使用迭代器进行访问, 增强 for 反编译以后其实就是 iterator
使用迭代器对链表进行迭代, Linked 的迭代器内部就是从头节点开始依次向下寻找节点
使用内部迭代 forEach 方式
几种迭代方式的比较:
LinkedList 使用增强 for 方式进行遍历速度较快, 使用该 fori 进行遍历时候, 在百万级数据量程序直接卡死, 所以 LinkedList 严禁使用 fori 遍历
在千万级别数据量的情况下, 速度和 ArrayList 差不多, 但 ArrayList 较快, 因为 ArrayList 数据空间是连续的
ArrayList 和 LinkedList 的区别
是否保证线程安全: ArrayList 和 LinkedList 都是不同步的, 也就是不保证线程安全;
底层数据结构: Arraylist 底层使用的是 Object 数组; LinkedList 底层使用的是双向链表数据结构(JDK1.6 之前为循环链表, JDK1.7 取消了循环. 注意双向链表和双向循环链表的区别, 下面有介绍到!)
插入和删除是否受元素位置的影响:
1 ArrayList 采用数组存储, 所以插入和删除元素的时间复杂度受元素位置的影响. 比如: 执行 add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾, 这种情况时间复杂度就是 O(1). 但是如果要在指定位置 i 插入和删除元素的话 (add(int index, E element)) 时间复杂度就为 O(n-i). 因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位 / 向前移一位的操作.
2 LinkedList 采用链表存储, 所以插入, 删除元素时间复杂度不受元素位置的影响, 都是近似 O(1)而数组为近似 O(n).
是否支持快速随机访问: LinkedList 不支持高效的随机元素访问, 而 ArrayList 支持. 快速随机访问就是通过元素的序号快速获取元素对象 (对应于 get(int index) 方法).
内存空间占用: ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间, 而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)
Map:
Map 是双列集合, 即存储元素的时候是键值对的形式在 Map 中存储的, 一个 Entry<K,V > 结构的键值对映射, 一个键对 应一个值, 不允许出现重复的键,
HashMap
HashMap 的类继承关系:
HashMap 继承自 AbstractMap 同样一个抽象类的出现是为了实现一些子类通用的方法, 一些个性化的方法还需要子类 去实现
HashMap 内部是使用了散列表 + 红黑树进行存储数据的, 即数组 + 链表 + 红黑树
HashMap 的特点
HashMap 使用位运算将 HashMap 中数组的大小一定是 2 的 N 次方, 保证了在取出元素时候通过与运算能更高效 和更精确的定位数组下标
即使两个不一样的元素也可能会出现同样的 hashCode,HashMap 使用拉链法设计解决了 Hash 冲突问题, 同一个散列槽 (在我们这里就是数组的每一个槽) 中的所有元素放到一个链表中
HashMap 在某一个槽上的链表长度大于等于 8 的时候并且 HashMap 中数组的长度大于等于 64 会进行树化, 将 链表转换成红黑树以提升查询效率
在增删改查元素的时候平均时间复杂度为 O(1)非常高效
HashMap 在插入的时候允许空键空值
HashMap 是非同步的, 多线程同时操作的时候会发生并发修改异常
HashMap 的迭代方式
通过 keySet||valueSet 进行遍历
- // 获取到所有的 key 然后依次进行获取
- Set<Integer> keySet = map.keySet(); Integer val = 0;
- for (Integer key : keySet) {
- val = map.get(key);
- System.out.print("");
- }
通过 entrySet 对 map 进行遍历
- Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
- for (Map.Entry<Integer, Integer> entry : entrySet) {
- System.out.print("");
- }
使用内部迭代
- Map<Object,Object> objectObjectMap = new HashMap<>();
- objectObjectMap.forEach( (o1, o2) ->System.out.println(o1.toString()+o2));
- // 内部迭代底层依然是使用 entrySet 进行迭代, 效率不如直接使用外部迭代
- default void forEach(BiConsumer<? super K, ? super V> action) {
- Objects.requireNonNull(action);
- for (Map.Entry<K, V> entry : entrySet()) {
- K k;
- V v; try {
- k = entry.getKey();
- v = entry.getValue();
- } catch(IllegalStateException ise) {
- // this usually means the entry is no longer in the map. throw new ConcurrentModificationException(ise);
- }
- action.accept(k, v);
- }
- }
几种迭代方式的性能差异
LinkedHashMap:
LinkedHashMap 是 HashMap 的一个子类, 内部维护了一个双向链表保证了元素插入的顺序
HashMap 的类继承关系
LinkedHashMap 的数据结构
LinkedHashMap 的特点
LinkedHashMap 是 HashMap 的子类, 其增删改查的平均时间复杂度依然是 O(1)
LinkedHashMap 的节点占用了更多的空间, 包括指向前一个节点的指针 before 和指向后一个节点的 after 指针
LinkedHashMap 默认使用插入顺序进行遍历, 也可以使用访问顺序, 将 accessOrder 置为 true 即可
LinkedHashMap 的迭代方式
使用 keySet 进行遍历, keySet 返回的是一个 LinkedKeySet,LinkedKeySet 的遍历方式是按照插入时候的顺序
使用 entrySet 进行遍历, 返回 LinkedEntrySet
使用内部迭代 forEach
- public void forEach(BiConsumer<? super K, ? super V> action) {
- if (action == null)
- throw new NullPointerException(); int mc = modCount;
- for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) action.accept(e.key, e.value);
- if (modCount != mc)
- throw new ConcurrentModificationException();
- }
- TreeMap
TreeMap 中的元素默认按照 keys 的自然排序排列.(对 Integer 来说, 其自然排序就是数字的升序; 对 String 来说, 其自然排序就是按照字母表排序)
TreeMap 的定义如下:
- public class TreeMap<K,V>
- extends AbstractMap<K,V>
- implements NavigableMap<K,V>, Cloneable, java.io.Serializable
TreeMap 继承 AbstractMap, 实现 NavigableMap,Cloneable,Serializable 三个接口. 其中 AbstractMap 表明 TreeMap 为一个 Map 即支持 key-value 的集合, NavigableMap(更多)则意味着它支持一系列的导航方法, 具备针对给定搜索目标返回最接近匹配项的导航方法 .
TreeMap 中同时也包含了如下几个重要的属性:
- // 比较器, 因为 TreeMap 是有序的, 通过 comparator 接口我们可以对 TreeMap 的内部排序进行精密的控制
- private final Comparator<? super K> comparator;
- //TreeMap 红 - 黑节点, 为 TreeMap 的内部类
- private transient Entry<K,V> root = null;
- // 容器大小
- private transient int size = 0;
- //TreeMap 修改次数
- private transient int modCount = 0;
- // 红黑树的节点颜色 -- 红色
- private static final boolean RED = false;
- // 红黑树的节点颜色 -- 黑色
- private static final boolean BLACK = true;
对于叶子节点 Entry 是 TreeMap 的内部类, 它有几个重要的属性:
- // 键
- K key;
- // 值
- V value;
- // 左孩子
- Entry<K,V> left = null;
- // 右孩子
- Entry<K,V> right = null;
- // 父亲
- Entry<K,V> parent;
- // 颜色
- boolean color = BLACK;
数据结构: 基于红黑树的一种实现, 红黑树是自平横的二叉搜索树. 二叉搜索树是排序好的二叉树.
Set
Set 集合存储元素的特点就是, set 存储元素都是无序并且不可重复的, 比较常用的两种有 HashSet 和 TreeSet
HashSet:
HashSet 的类继承关系
Hashset 的顶级接口是 Collection 接口, 属于单列集合, 即每次存储一个元素
HashSet 的数据结构
- private transient HashMap<E,Object> map;// 内部维护了一个 map, 其底层实现靠的就是 HashMap, 键用于存放值
- // Dummy value to associate with an Object in the backing Map
- private static final Object PRESENT = new Object();// 这个空的 Object 对象作为所有的默认 Value
- /**
- *Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
- *default initial capacity (16) and load factor (0.75).
- */
- public HashSet() {
- map = new HashMap<>();
- }
- // add 方法其实就是调用了 map 的 put, 并传入一个空的 value
- public boolean add(E e) {
- return map.put(e, PRESENT)==null;
- }
因为 Set 的元素和 HashMap 中的键是有相同的特征的, HashSet 充分利用了 HashMap 的功能
HashSet 的特点:
存储元素时会去重, 即集合中的元素都是不可重复的
HashSet 没有 get 方法, 其实道理也很显而易见, 因为元素是无序的所以不能根据下标来访问元素
HashSet 的本质就是 HashMap
HashSet 的迭代方式:
使用迭代器进行迭代, 其实本质上返回的就是 HashMap 的 keySet
- public Iterator<E> iterator() {
- return map.keySet().iterator();
- }
使用 forEach 进行内部迭代, 性能不如直接使用迭代器
- set.forEach(k->System.out.println(k));
- TreeSet
TreeSet 是基于 TreeMap 实现的, TreeSet 的元素支持 2 种排序方式: 自然排序或者根据提供的 Comparator 进行排序.
继承关系:
TreeSet 的特点
TreeSet 中存储的元素是有序且不可重复的, 所谓有序就是按照元素自身的排序顺序, 或者使用者自定义比较 方式
和 HashSet 类似 TreeSet 的底层实现就是 TreeMap
- public TreeSet() {
- this(new TreeMap<E,Object>());
- }
来源: https://www.cnblogs.com/liruilong/p/12591118.html