真正的学会，不是为了面试学的那一点原理，而是应用在真实的代码之中
我们在实际工作中，应用最多的List，应该是ArrayList、LinkedList，我们先上一张图，回顾一下。
image.png
接下来，我们聊一些图中没有内容（图中内容可以自己看看源码，深入了解一下）
一、底层是数组结构的ArrayList为什么查询快？
大多数人是这么回答的，因为连续的内存地址，通过下标访问，所以快！没有错，但再深入一些呢？
再深入些就涉及到了CPU多级缓存和缓存行的概念。为了解决CPU运算速度与内存读写速度不匹配，引入了高速缓存，一般有一级缓存、二级缓存、三级缓存。每个缓存都是由缓存行（Cache Line）组成，缓存行大小是64KB。当CPU从主内存拉取数据时，会把相邻的数据一块存入一个Cache Line，所以当数组中的一个值被加载到高速缓存时，会自动加载数组中其他的值。所以你能快速的遍历这个数组。利用Cache Line 和 不利用 Cache Line 特性的效率大概会差1倍多呢。
如果多个线程操作同一个Cache Line，就会造成伪共享，这个后续讲阻塞队列的时候再聊。
二、数组和链表两种数据结构，对垃圾回收的影响？
数组分配内存时，需要连续的内存空间，如果数组太大，可能会存在内存碎片，导致触发垃圾回收或者分配失败，数组太小会导致不够用，会重新分配更大的内存，然后进行数据拷贝，非常耗时。但合适的数组大小，在对其操作时，不会频繁的触发垃圾回收，减少Java的垃圾回收对系统性能的影响。
链表每次添加一项数据，都会创建一个对象，给对象分配内存，而且每个对象还要存储前驱和后驱的节点指针，耗内存较多。而且对链表频繁的操作，造成内存频繁的申请和释放，导致内存碎片和触发垃圾回收，会对系统性能导致非常不稳定。一般的解决方法都是通过缓存或对象池来解决。比如Apache Common Collection 下的 NodeCachingLinkedList。
三、写代码时，对List操作的一些工具类和技巧
- 利用guava的工厂类初始化集合
//构建ArrayList
Lists.newArrayList();
//构建LinkedList
Lists.newLinkedList();
//构建指定大小的ArrayList
Lists.newArrayListWithCapacity(100);
//构建读写分离的List
Lists.newCopyOnWriteArrayList();
- 对集合进行交集、并集、差集、反转、分割、删除等操作
List<String> list1 = Lists.newArrayList("2", "1");
List<String> list2 = Lists.newArrayList("2", "5", "6");
//list1和list2的交集
list1.retainAll(list2);
// 并集
list1.addAll(list2);
// 去重复并集
list2.removeAll(list1);
list1.addAll(list2);
//差集
list1.removeAll(list2);
//通过guava方法反转
Lists.reverse(list1);
//按指定条数分割
List<List<String>> list3 = Lists.partition(list, 2);
//删除某元素
list1.removeIf(it -> it.equals("2"));
- 对集合进行排序
List<Integer> list = Lists.newArrayList(1, 4, 5, 10, 2, 6);
//通过对象的值
list.sort(Comparator.comparingInt(Integer::intValue));
//实现Comparator接口,自定义排序，一般对象元素使用
list.sort((o1, o2) -> o1 > o2 ? 1 : o1.equals(o2) ? 0 : -1);
//通过Collections工具类,默认排序，或者对象实现Comparable接口
Collections.sort(list);
//通过Collections工具类,自定义排序，一般对象元素使用
Collections.sort(list, (o1, o2) -> o1 > o2 ? 1 : o1.equals(o2) ? 0 : -1);
- lambda表达式对集合操作
List<Integer> list = Lists.newArrayList(1, 4, 5, 10, 2, 6);
//遍历，效率很高
list.stream().forEach(it -> System.out.println(it));
//并行流，底层应用ForkJoin线程池，提高效率
list.parallelStream().forEach(it -> System.out.println(it));
//过滤
list.stream().filter(it -> it > 3).collect(Collectors.toList());
list.stream().filter(it -> it > 3).count();
//对元素操作
list.stream().map(it -> it * 2).collect(Collectors.toList());
//还有map转换，group分组等等功能，功能强大自行百度
- 如果返回空集合，不要再new对象
//直接通过工具类返回空集合，避免对象的创建，该 List 为不可变：
return Collections.EMPTY_LIST;
四、Collections.sort 的底层排序算法
JDK1.8以后默认采用Timsort排序，Timsort 是一种混合稳定的排序算法，源自合并排序和插入排序，旨在较好地处理真实世界中各种各样的数据。
Java版首先会根据数组长度，采用Binarysort（折半插入排序法）对长度小于32（MIN_MERGE）直接进行排序返回结果；对于长度大于等于32的数组，先分区，再对单个分区进行采用Binarysort排序，最后合并分区并排序。感兴趣的可以去看看源码。
四、通过LinkedList和HashMap撸一个LRUMap
LRU（Least recently used，最近最少使用）是一种常用的缓存淘汰方法，算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。像Redis的缓存策略中就有LRU策略。
LRU算法用到两个个数据结构，一个是map 一个是链表。map用来存储数据，做O(1)的查询，链表用来记录访问顺序，对数据进行前置，增加和删除。
该算法也存在其他问题：1、性能问题，每次读也要操作链表，找到命中，移动到表头，所有操作还要加锁或者使用cas无锁模式，2、缓存污染问题，偶发性的、周期性的批量操作会使临时数据涌入缓存，挤出热点数据，导致LRU热点命中率急剧下降，缓存污染情况比较严重。其他缓存算法还有LFU，和LRU优化算法等，各种算法搞的头疼啊。现在放代码！比较简单啊，写的不好见谅。
public class LRUMap<K, V> {
/**
* 默认大小
*/
private static final int DEFAULT_MAX_SIZE = 100;
/**
* 最大大小
*/
private int maxSize;
/**
* 数据缓存
*/
private Map<K, V> cacheMap = null;
/**
* 记录访问记录
*/
private LinkedList<K> accessRecordsLinkedList = null;
public LRUMap(final int maxSize) {
cacheMap = new HashMap<>(maxSize);
accessRecordsLinkedList = new LinkedList<>();
this.maxSize = maxSize;
}
public LRUMap() {
cacheMap = new HashMap<>(DEFAULT_MAX_SIZE);
accessRecordsLinkedList = new LinkedList<>();
this.maxSize = DEFAULT_MAX_SIZE;
}
/**
* 查询
*
* @param key
* @return
*/
public V get(K key) {
V value = this.cacheMap.get(key);
if (null != value) {
moveToHead(key);
}
return value;
}
/**
* 添加数据
*
* @param key
* @param value
*/
public void put(K key, V value) {
if (null != cacheMap.get(key)) {
//如果存在此key,就直接移动到链表头部
moveToHead(key);
} else {
if (accessRecordsLinkedList.size() >= maxSize) {
//链表获取最后元素并移除
K lastKey = this.accessRecordsLinkedList.pollLast();
//map删除该数据
this.cacheMap.remove(lastKey);
}
//添加到头部
accessRecordsLinkedList.addFirst(key);
}
//缓存数据
this.cacheMap.put(key, value);
}
/**
* 移动到头部
*
* @param key
*/
private void moveToHead(K key) {
this.accessRecordsLinkedList.removeIf(it -> it.equals(key));
this.accessRecordsLinkedList.addFirst(key);
}
public static void main(String[] args) {
LRUMap<String, String> lruMap = new LRUMap<>(3);
lruMap.put("1", "3");
lruMap.put("2", "3");
lruMap.get("1");
lruMap.put("4", "3");
lruMap.put("5", "3");
System.out.println(JSON.toJSONString(lruMap.cacheMap));
}
}
五、如何判断链表有环
这个问题，在面试中问的频率非常高，实现可以用HastSet，但空间复杂度是O(n) ，一般考察的是通过双指针实现，没有额外的空间，空间复杂度O(1)。上代码。
/**
* 链表节点
*/
private static class Node {
private int data;
private Node next;
Node(int data) {
this.data = data;
}
}
/**
* 判断是否有环
* @param head 头节点
* @return
*/
public static boolean isCycle(Node head) {
Node p1 = head;
Node p2 = head;
while (p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next.next;
if (p1 == p2) {
return true;
}
}
return false;
}
常见的冒泡和快排，以及优化方案，我后续补上，欢迎留言补充，到时候有好的奇淫巧技，我再补充上去。
网友评论