学习Java集合
集合
List、Set、Map
集合中的最上层接口只有2类：Map和Collection，List和Set是Collection的下一层。
| 三者名称 | 特性 | 安全类 | 安全原理 |
|---|---|---|---|
| List | 有序、可重复 | CopyOnWriteArrayList | 读写分离，写时复制 |
| Set | 无需、不可重复 | CopyOnWriteArraySet | 读写分离，写时复制 |
| Map | 键值对形式存储 | ConcurrentMap | 没哈希冲突就CAS，有哈希冲突就Syn加锁 |
LIst
| LIst类 | 底层数据结构 | 特性 | 安全性 |
|---|---|---|---|
| ArrayList | 数据 | 增删慢，查询快， | 不安全，安全需要CopyOnWriteArrayList |
| Vector | 数组 | 增删慢，查询快 | 安全，底层是对每一个结点都加Syn |
| LinkedList | 双向链表 | 增删快，查询慢 | 不安全，安全需要CopyOnWriteLinkedList |
Queue
| Queue | 解释 |
|---|---|
| ArrayBlockingQueue | 数组结构组成的有界阻塞队列 |
| LinkedBlockingQueue | 由链表组成的有界阻塞队列（大小默认是21亿，不推荐默认使用） |
| LinkedBlockingDeque | 由链表结构组成的双向阻塞队列 |
| PriorityBlockingQueue | 支持优先级排序的无界阻塞队列 |
| DelayBlockingQueue | 使用优先级队列实现的延迟无界队列 |
| SynchronousQueue | 不存储元素的阻塞队列=单个元素的队列 |
| LinkedTransferQueue | 由链表结构组成的无界阻塞队列 |
Set
| Set | 底层 | 特性 |
|---|---|---|
| HashSet | HashMap<key,PRESENT> | 无序不重复 |
| TreeSet | 二叉树 | 排序不重复 |
| LinkedHashSet | LinkedHashMap<key,PRESENT> | 可前后遍历，不重复 |
Map
| Map | 底层 | 安全性 |
|---|---|---|
| HashMap | 数组+链表/红黑树 | Map不安全 |
| ConcurrentMap | 数组+链表/红黑树 | 安全，原理是冲突syn+不冲突CAS |
| TreeMap | 二叉树 | 不安全 |
| LinkedHashMap | 双向链表 | 不安全 |
HashMap
| HashMap | 描述 |
|---|---|
| 底层数据结构 | 数组+链表/红黑树 |
| 存储数据流程 | 如下所示 |
| 长度 | 默认16，装载因子为0.75 |
| 阈值 | 扩容成红黑树的阈值为8 |
存储数据的流程
- 对key的hash后获得数组index;2.数组位置为空，初始化容量为16
- 数组位置为空，初试化容量为16
- hash后没有碰撞，就放入数组
- 有碰撞且节点已存在，则替换掉原来的对象
- 有碰撞且节点已经是树结构，则挂载到树上
- 有碰撞且节点已经是链表结构，则添加到链表末尾，并判断链表是否需要转换为树结构（链表结点大于8就转换）
- 完成put操作后，判断是否需要resize()操作
hashMap不安全原因
- 在JDK1.7中，当并发执行扩容操作时会造成环形链和数据丢失的情况。源码是1.7时的 transfer函数，自己点进去看
- 在JDK1.8中，在并发执行put操作时会发生数据覆盖的情况。源码是1.8时的resize函数，自己点进去看
HashMap和Hashtable
| 特性 | HashMap | Hashtable |
|---|---|---|
| 安全性 | 不安全，分为1.7和1.8 | 单个线程安全，原因是加了同步锁 |
| hashcode | 对key的hashcode重新计算 | 直接使用key的HashCode |
| key,value | 都可以为null | 都不能为null（注意，idea不会提示报错，但是运行出现空指针异常，源码有提示） |
| 长度 | 默认16，扩容翻倍 | 默认11，扩容+1 |
key,value为空的问题：
public static void main(String[] args) {
HashMap<Integer, Integer> hashmap = new HashMap<>();
hashmap.put(null, null);// hashmap两个都可以存null
Hashtable<Integer, Integer> hashtable = new Hashtable<>();
hashtable.put(null, null);//hashtable任一个都不能存null，但idea不会报错，运行会出现空指针异常
} HashMap的长度为什么是2的幂次方？
答：提高数组利用率，减少冲突（碰撞）的次数，提高HashMap查询效率
// 源码计算index的操作：n是table.length if ((p = tab[i = (n - 1) & hash]) == null)
ConcurrentHashMap
线程安全的底层原理：没有哈希冲突就大量CAS插入+如果有哈希冲突就Syn加锁
TreeMap
treeMap底层使用红黑树，会按照Key来排序
- 如果是字符串，就会按照字典序来排序
- 如果是自定义类，就要使用2种方法指定比较规则
- 实现Compareable接口，但是需要重新定义比较规则就要修改源码，麻烦
- 创建实例时候，传入一个比较器Comparator，重新定义规则不需要修改源码，推荐使用
public class TreeMapDemo {
public static void main(String[] args) {
// treeMap中自定义类需要指定比较器
// 方式一：自定义类实现Comparable接口
TreeMap<User, User> treeMap1 = new TreeMap<>();
// 方式二：创建实例指定比较器Comparator
TreeMap<User, User> treeMap2 = new TreeMap<>(new Comparator<User>() {
@Override
public int compare(User o1, User o2) {
// 定义比较规则
return 0;
}
});
}
}
public class User implements Comparable {
private String id;
private String username;
@Override
public int compareTo(Object obj) {
// 这里定义比较规则
return 0;
}
} ArrayList和LinkedList
| 特性 | ArrayList | LinkedList |
|---|---|---|
| 底层 | 动态数组，查询快，插入慢 | 双向链表，查询慢，插入快 |
| 安全 | 不安全 | 不安全 |
| 接口 | 都是List接口的实现类，存储有序，可重复 | 都是List接口的实现类，存储有序，可重复 |
Vetor和CopyOnWriteList
list安全类是如下两个：Vetor、CopyOnWriteList； Collections.synchronizedLis是JDK包装实现线程安全的工具类
| Vector | Collections.synchronizedList | CopyOnWriteList | |
|---|---|---|---|
| 线程安全原理 | synchronized加载方法上 | 内部类封装SynchronizedList方法 | 写加锁，读不加锁，通过volatile保证可见性 |
public synchronized int capacity() {
return elementData.length;
}
// Vetor锁都加在方法上
public synchronized int size() {
return elementCount;
}
public synchronized boolean isEmpty() {
return elementCount == 0;
}
...
} static class SynchronizedList<E>
extends SynchronizedCollection<E>
implements List<E> {
private static final long serialVersionUID = -7754090372962971524L;
final List<E> list;
// Collections.synchronizedList:内部类SynchronizedList，锁加载内部类里面
SynchronizedList(List<E> list) {
super(list);
this.list = list;
}
SynchronizedList(List<E> list, Object mutex) {
super(list, mutex);
this.list = list;
}
....
} // CopyOnWriteList 写加锁
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
// CopyOnWriteList是复制数组保证线程安全
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
// CopyOnWriteList 读不加锁，原数组通过 transient volatile保证不可系列化和可见性
private transient volatile Object[] array;
final Object[] getArray() {
return array;
}
public E get(int index) {
return get(getArray(), index);
} LinkedHashMap和LinkedHashSet
答：LinkedHashMap可以记录下元素的插入顺序和访问顺序
- LinkedHashMap内部的Entry继承于HashMap.Node，这两个类都实现了Map.Entry<K,V>
- 底层链表是双向链表，Node不光有value，next，还有before和after属性，保证了各个元素的插入顺序
- 通过构造方法public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)， accessOrder传入true可以实现LRU缓存算法（访问顺序）
LRU算法
最近最少使用算法: 根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
public class LRUTest {
// 0.指定map长度size=5
private static final int size = 5;
public static void main(String[] args) {
// 1. LinkedHashMap三大参数，重写removeEldestEntry
Map<String, String> map = new LinkedHashMap<String, String>(size, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
return size() > size;
}
};
// 2.添加5个数，使得map满
map.put("1", "1");
map.put("2", "2");
map.put("3", "3");
map.put("4", "4");
map.put("5", "5");
System.out.println("map:" + map.toString());
// 3.指定map满了，再put就会移除表头第一个元素:1=1
map.put("6", "6");
System.out.println("map:" + map.toString());
// 4.get取出的元素，表示是常用的，放回到表尾
map.get("3");
System.out.println("map:" + map.toString());
}
} 执行结果：
map:{1=1, 2=2, 3=3, 4=4, 5=5}
map:{2=2, 3=3, 4=4, 5=5, 6=6}
map:{2=2, 4=4, 5=5, 6=6, 3=3} 手写LRU算法
public class LRUCache {
// 力扣146同一题
class DoubleNode {
int key;
int value;
DoubleNode pre;
DoubleNode next;
DoubleNode(int key, int value) {
this.key = key;
this.value = value;
}
DoubleNode() {
}
}
private HashMap<Integer, DoubleNode> cache = new HashMap<>();
private int size;
private int capacity;
private DoubleNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
this.head = new DoubleNode();
this.tail = new DoubleNode();
// 创建伪头部和伪尾部，减少添加和删除的逻辑
head.next = tail;
tail.pre = head;
}
public int get(int key) {
// 1.获取get元素
DoubleNode node = cache.get(key);
// 2.get元素不存就返回-1
if (node == null) {
return -1;
}
// 3.get元素就移动至头部，规定常用元素移动至头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
// 1.获取put元素
DoubleNode node = cache.get(key);
// 2.put元素不存在
if (node == null) {
// 生成它
DoubleNode nowNode = new DoubleNode(key, value);
// 放进cache
cache.put(key, nowNode);
// 添加进头部
addToHead(nowNode);
// 长度++
size++;
// 判断是否超过指定长度
if (size > capacity) {
DoubleNode tail = removeTail();
cache.remove(tail.key);
size--;
}
} else {
// 3.node存在就更新value，然后移动至头部
node.value = value;
moveToHead(node);
}
}
private void addToHead(DoubleNode node) {
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
private DoubleNode removeTail() {
DoubleNode del = tail.pre;
removeNode(del);
return del;
}
private void removeNode(DoubleNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void moveToHead(DoubleNode node) {
removeNode(node);
addToHead(node);
}
} Iterator和ListIterator
| Iterator | ListIterator | |
|---|---|---|
| 使用集合 | List、set | 只能是List |
| 前后遍历 | 只能想后遍历 | 前后遍历都行 |
public class IteratorDemo {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
} 快速失败和安全失败
| fail-fast | fail-safe | |
|---|---|---|
| 报错 | 失败/异常，会立刻报错 | 失败/异常，直接忽略，不会报错 |
| 异常 | 抛出CorrentModificationException | 不会抛出异常 |
| 适用包 | java.util下的集合类 | java.util.concurrent下的集合类 |
| 原理 | 迭代器检查modCount和expectedModCount | CopyOnWriteXX写加锁，读不加锁，两者不冲突 |
迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedModCount值，是的话就返回遍历；否则抛出异常，终止遍历
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
...
// modCount记录当前线程更改状态
++modCount;
...
return null;
} 数组和List和遍历转换
| 数组 | List | |
|---|---|---|
| 遍历 | Arrays.toString（arr） | 直接遍历 |
| 相互转换 | 不推荐Arrays.asList(arr)。推荐Collections.singletonList(arr); | arrayList.toArray(new Integer[3]) |
public class ArrayAndList {
public static void main(String[] args) {
// 1.数组遍历:Arrays.toString
int[] arr = {1, 2, 3};
System.out.println(Arrays.toString(arr));
// 2.数组转成list，泛型说明不推荐使用，多此一举
List<int[]> ints1 = Arrays.asList(arr);
List<int[]> ints = Collections.singletonList(arr);
for (int[] anInt : ints) {
System.out.println(Arrays.toString(anInt));
}
System.out.println("------------");
// 3.list遍历：直接遍历即可
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
System.out.println(arrayList);
// 4.list转换成数组，list名.toArray(指定数组类型和长度)
Integer[] integers = arrayList.toArray(new Integer[3]);
System.out.println(Arrays.toString(integers));
}
} 
科大讯飞公司福利 116人发布
