真正学会Java集合之List

拼搏现实的明天。 2023-02-16 04:16 38阅读 0赞

真正的学会，不是为了面试学的那一点原理，而是应用在真实的代码之中

*  List 知识脑图梳理
 *  底层是数组结构的 ArrayList 为什么查询快
 *  数组和链表两种数据结构，对垃圾回收的影响
 *  写代码时，对 List 操作的一些工具类和技巧
 *  Collections.sort 的底层排序算法
 *  通过 LinkedList 和 HashMap 撸一个 LRUMap
 *  如何判断链表有环

我们在实际工作中，应用最多的 List，应该是 ArrayList、LinkedList，我们先上一张图，回顾一下。

![在这里插入图片描述][b4526050-a87c-11ea-8a9d-2519084b9804]

接下来，我们聊一些图中没有内容（图中内容可以自己看看源码，深入了解一下）

### 一、底层是数组结构的 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 对象**

//直接通过工具类返回空集合，避免对象的创建    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;    }

常见的冒泡和快排，以及优化方案，我后续补上，欢迎留言补充，到时候有好的奇淫巧技，我再补充上去。也希望你可以关注并订阅我其他的 chat

阅读全文: [http://gitbook.cn/gitchat/activity/5edc75cc6c5a6b7909824e6d][http_gitbook.cn_gitchat_activity_5edc75cc6c5a6b7909824e6d]

您还可以下载 CSDN 旗下精品原创内容社区 GitChat App ，阅读更多 GitChat 专享技术内容哦。

![FtooAtPSkEJwnW-9xkCLqSTRpBKX][]

[b4526050-a87c-11ea-8a9d-2519084b9804]: https://images.gitbook.cn/b4526050-a87c-11ea-8a9d-2519084b9804
[http_gitbook.cn_gitchat_activity_5edc75cc6c5a6b7909824e6d]: http://gitbook.cn/gitchat/activity/5edc75cc6c5a6b7909824e6d?utm_source=csdn_blog
[FtooAtPSkEJwnW-9xkCLqSTRpBKX]: https://images.gitbook.cn/FtooAtPSkEJwnW-9xkCLqSTRpBKX