集合
List、Set、Map
集合中的最上层接口只有2类：Map和Collection，List和Set是Collection的下一层。
LIst
Queue
Set
Map
HashMap
存储数据的流程
- 对key的hash后获得数组index;2.数组位置为空，初始化容量为16
- 数组位置为空，初试化容量为16
- hash后没有碰撞，就放入数组
- 有碰撞且节点已存在，则替换掉原来的对象
- 有碰撞且节点已经是树结构，则挂载到树上
- 有碰撞且节点已经是链表结构，则添加到链表末尾，并判断链表是否需要转换为树结构（链表结点大于8就转换）
- 完成put操作后，判断是否需要resize()操作
hashMap不安全原因
- 在JDK1.7中，当并发执行扩容操作时会造成环形链和数据丢失的情况。源码是1.7时的 transfer函数，自己点进去看
- 在JDK1.8中，在并发执行put操作时会发生数据覆盖的情况。源码是1.8时的resize函数，自己点进去看
HashMap和Hashtable
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
Vetor和CopyOnWriteList
list安全类是如下两个：Vetor、CopyOnWriteList； Collections.synchronizedLis是JDK包装实现线程安全的工具类
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
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());
}
}
}
快速失败和安全失败
迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 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和遍历转换
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));
}
}
总结
感谢你看到这里，文章有什么不足还请指正，觉得文章对你有帮助的话记得给我点个赞，每天都会分享java相关技术文章或行业资讯，欢迎大家关注和转发文章！
欢迎关注公众号：前程有光，领取一线大厂Java面试题总结+各知识点学习思维导+一份300页pdf文档的Java核心知识点总结！