真正的学会，不是为了面试学的那一点原理，而是应用在真实的代码之中
- List 知识脑图梳理
- 底层是数组结构的 ArrayList 为什么查询快
- 数组和链表两种数据结构，对垃圾回收的影响
- 写代码时，对 List 操作的一些工具类和技巧
- Collections.sort 的底层排序算法
- 通过 LinkedList 和 HashMap 撸一个 LRUMap
- 如何判断链表有环
我们在实际工作中，应用最多的 List，应该是 ArrayList、LinkedList，我们先上一张图，回顾一下。
接下来，我们聊一些图中没有内容（图中内容可以自己看看源码，深入了解一下）
一、底层是数组结构的 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 list1 = Lists.newArrayList("2", "1"); List 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 list3 = Lists.partition(list, 2); //删除某元素 list1.removeIf(it -> it.equals("2"));- 对集合进行排序
List 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 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 对象
//直接通过工具类返回空集合，避免对象的创建 return Collections.EMPTY_LIST;JDK1.8 以后默认采用 Timsort 排序，Timsort 是一种混合稳定的排序算法，源自合并排序和插入排序，旨在较好地处理真实世界中各种各样的数据。
Java 版首先会根据数组长度，采用 Binarysort（折半插入排序法）对长度小于 32（MIN_MERGE）直接进行排序返回结果；对于长度大于等于 32 的数组，先分区，再对单个分区进行采用 Binarysort 排序，最后合并分区并排序。感兴趣的可以去看看源码。
四、通过 LinkedList 和 HashMap 撸一个 LRUMapLRU（Least recently used，最近最少使用）是一种常用的缓存淘汰方法，算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。像 Redis 的缓存策略中就有 LRU 策略。
LRU 算法用到两个个数据结构，一个是 map 一个是链表。map 用来存储数据，做 O(1)的查询，链表用来记录访问顺序，对数据进行前置，增加和删除。
该算法也存在其他问题：1、性能问题，每次读也要操作链表，找到命中，移动到表头，所有操作还要加锁或者使用 cas 无锁模式，2、缓存污染问题，偶发性的、周期性的批量操作会使临时数据涌入缓存，挤出热点数据，导致 LRU 热点命中率急剧下降，缓存污染情况比较严重。其他缓存算法还有 LFU，和 LRU 优化算法等，各种算法搞的头疼啊。现在放代码！比较简单啊，写的不好见谅。
public class LRUMap { /** * 默认大小 */ private static final int DEFAULT_MAX_SIZE = 100; /** * 最大大小 */ private int maxSize; /** * 数据缓存 */ private Map cacheMap = null; /** * 记录访问记录 */ private LinkedList 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 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; }常见的冒泡和快排，以及优化方案，我后续补上，欢迎留言补充，到时候有好的奇淫巧技，我再补充上去。也希望你可以关注并订阅我其他的 chat
阅读全文: http://gitbook.cn/gitchat/activity/5edc75cc6c5a6b7909824e6d
您还可以下载 CSDN 旗下精品原创内容社区 GitChat App ，阅读更多 GitChat 专享技术内容哦。
