Java巩固

Java容器

Posted by Cfeng on August 21, 2019
  • 容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。

Collection

Set接口

  1. TreeSet：基于红黑树实现（自平衡的排序二叉树），支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。
  2. HashSet：基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
  3. LinkedHashSet：具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序。

List接口

  1. ArrayList：基于动态数组实现，支持随机访问。
  2. Vector：和 ArrayList 类似，但它是线程安全的。
  3. LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。

Queue接口

  1. LinkedList：可以用它来实现双向队列。
  2. PriorityQueue：基于堆结构实现，可以用它来实现优先队列。

Map

  1. TreeMap：基于红黑树实现。自平衡的排序二叉树）
  2. HashMap：JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
  3. HashTable：数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。它是线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
  4. LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。

List,Set,Map三者的区别

  1. List(对付顺序的好帮手): List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象
  2. Set(注重独一无二的性质): 不允许重复的集合。不会有多个元素引用相同的对象。
  3. Map(用Key来搜索的专家): 使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。

如何选用集合

主要根据集合的特点来选用，比如我们需要根据键值获取到元素值时就选用Map接口下的集合，需要排序时选择TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选用ConcurrentHashMap.当我们只需要存放元素值时，就选择实现Collection接口的集合，需要保证元素唯一时选择实现Set接口的集合比如TreeSet或HashSet，不需要就选择实现List接口的比如ArrayList或LinkedList，然后再根据实现这些接口的集合的特点来选用

ArrayList

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}

ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。
它继承于 AbstractList，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。

ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
ArrayList 实现了RandomAccess 接口， RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
ArrayList 实现了Cloneable 接口，即覆盖了函数 clone()，能被克隆。
ArrayList 实现java.io.Serializable 接口，这意味着ArrayList支持序列化，能通过序列化去传输。

扩容
添加元素时用size与当前数组大小比较(在一个私有的add方法中)，来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity » 1)，也就是旧容量的 1.5 倍。如果之前为空，则扩充为默认值10，如果需求空间比10大，则扩充至需求空间。

扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

删除
需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)

三种遍历方式

System.out.print("通过迭代器遍历:");
Iterator<Integer> it = arrayList.iterator();
while(it.hasNext()){
    System.out.print(it.next() + " ");
}
System.out.println();

// 第二种：通过索引值遍历
System.out.print("通过索引值遍历:");
for(int i = 0; i < arrayList.size(); i++){
    System.out.print(arrayList.get(i) + " ");
}
System.out.println();

// 第三种：for循环遍历
System.out.print("for循环遍历:");
for(Integer number : arrayList){
    System.out.print(number + " ");
}

转化为数组

// toArray用法
// 第一种方式(最常用)
Integer[] integer = arrayList.toArray(new Integer[0]);

// 第二种方式(容易理解)
Integer[] integer1 = new Integer[arrayList.size()];
arrayList.toArray(integer1);

CopyOnWriteArrayList

是ArrayList的线程安全的变体

读写分离
写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。
写操作需要加锁，防止并发写入时导致写入数据丢失。
写操作结束之后需要把原始数组指向新的复制数组。

public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);
        es[len] = e;
        setArray(es);
        return true;
    }
}
public E get(int index) {
    return elementAt(getArray(), index);
}
@SuppressWarnings("unchecked")
static <E> E elementAt(Object[] a, int index) {
    return (E) a[index];
}

适用场景 CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。
但是 CopyOnWriteArrayList 有其缺陷：
内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。
所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

LinkedList

基于双向链表实现，使用 Node 存储链表节点信息。

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

与 ArrayList 的比较
ArrayList 基于动态数组实现，LinkedList 基于双向链表实现；
ArrayList 支持随机访问，LinkedList 不支持；
LinkedList 在任意位置添加删除元素更快。

Hashmap

非线程安全
HashMap 主要用来存放键值对，它基于哈希表的Map接口实现，是常用的Java集合之一。
JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.
JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。

红黑树：
红黑树就是一种平衡的二叉查找树

  1. 节点是红色或者黑色
  2. 根节点是黑色
  3. 每个叶子的节点都是黑色的空节点（NULL）
  4. 每个红色节点的两个子节点都是黑色的。
  5. 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
(n - 1) & hash ： 因为n为2的幂，所以该式子同理 hash % n

拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可
jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。当节点小于6时又变为链表

扩容：
设 HashMap 的 table 长度为 M，需要存储的键值对数量为 N，如果哈希函数满足均匀性的要求，那么每条链表的长度大约为 N/M，因此平均查找次数的复杂度为 O(N/M)。
默认大小为16，每次键值对数量=HashMap大小*loadFactor（装载因子）时，扩大一倍。

ConcurrentHashMap

JDK1.7
ConcurrentHashMap 和 HashMap 实现上类似，最主要的差别是 ConcurrentHashMap 采用了分段锁（Segment），每个分段锁维护着几个桶（HashEntry），多个线程可以同时访问不同分段锁上的桶，从而使其并发度更高（并发度就是 Segment 的个数）。
默认的并发级别为 16，也就是说默认创建 16 个 Segment。

JDK1.8
使用了 CAS 操作来支持更高的并发度，在 CAS 操作失败时使用内置锁 synchronized。

CAS：
其包含3个参数：
V表示要更新的变量
E表示预期值
N表示新值
如果V值等于E值，则将V的值设为N。若V值和E值不同，则说明已经有其他线程做了更新，则当前线程什么都不做。 通俗的理解就是CAS操作需要我们提供一个期望值，当期望值与当前线程的变量值相同时，说明还没线程修改该值，当前线程可以进行修改，也就是执行CAS操作，但如果期望值与当前线程不符，则说明该值已被其他线程修改，此时不执行更新操作，但可以选择重新读取该变量再尝试再次修改该变量，也可以放弃操作。
由于CAS操作属于乐观派，它总认为自己可以成功完成操作，当多个线程同时使用CAS操作一个变量时，只有一个会胜出，并成功更新，其余均会失败，但失败的线程并不会被挂起，仅是被告知失败，并且允许再次尝试，当然也允许失败的线程放弃操作，这点从图中也可以看出来。基于这样的原理，CAS操作即使没有锁，同样知道其他线程对共享资源操作影响，并执行相应的处理措施。同时从这点也可以看出，由于无锁操作中没有锁的存在，因此不可能出现死锁的情况，也就是说无锁操作天生免疫死锁。

CATALOG
    FEATURED TAGS
    数据结构 读书笔记 笔试 剑指Offer 算法 操作系统 Java基础 计算机网络 学习之路 Java SSM框架 每日leetcode Java巩固 spring cloud