搜索[提高]结果-低调大师优秀个人博客

精选列表

搜索[提高]，共10000篇文章

提高github下载速度的方法「100%有效」可达到2MB/s

提高下载子模块的速度有的项目里用到了第三方代码仓库，但是在你使用 clone 指令的时候这些子模块 submodule 并不会自动下载，因为他们在另外的地址中存放。

2020-04-29

Nutanix推出创新性解决方案，帮助客户提高远程办公效率

【51CTO.com原创稿件】谈到VDI，我想大家并不陌生，这种专门提供远程办公虚拟桌面的应用服务不但能够很好的提高办公效率，而且还能够更好的保护数据安全，让远程办公变得更加便利。

2020-03-23

滴滴开源小程序框架 Mpx ，致力于提高小程序开发体验

滴滴WebApp团队近日宣布开源 Mpx ，这是一款致力于提高小程序开发体验的增强型小程序框架。

2018-12-12

【Java入门提高篇】Day34 Java容器类详解（十五）WeakHashMap详解

在Java容器详解系列文章的最后，介绍一个相对特殊的成员：WeakHashMap，从名字可以看出它是一个Map。它的使用上跟HashMap并没有什么区别，所以很多地方这里就不做过多介绍了，可以翻看一下前面HashMap中的内容。本篇主要介绍它与HashMap的不同之处。 WeakHashMap特殊之处在于WeakHashMap里的entry可能会被垃圾回收器自动删除，也就是说即使你没有调用remove()或者clear()方法，它的entry也可能会慢慢变少。所以多次调用比如isEmpty，containsKey，size等方法时可能会返回不同的结果。接下来希望能带着这么几个问题来进行阅读： 1、WeakHashMap中的Entry为什么会自动被回收。 2、WeakHashMap与HashMap的区别是什么。 3、WeakHashMap的引用场景有哪些。 WeakHashMap探秘从说明可以看出，WeakHashMap的特殊之处便在于它的Entry与众不同，里面的Entry会被垃圾回收器自动回收，那么问题来了，为什么会被自动回收呢？HashMap里的Entry并不会被自动回收，除非把它从Map中移除掉。其实这个秘密就在于弱引用，WeakHashMap中的key是间接保存在弱引用中的，所以当key没有被继续使用时，就可能会在GC的时候被回收掉。只有key对象是使用弱引用保存的，value对象实际上仍旧是通过普通的强引用来保持的，所以应该确保value不会直接或者间接的保持其对应key的强引用，因为这样会阻止key被回收。如果对于引用类型不熟悉的话，可以先阅读这篇文章。下面来从源码角度看看具体是如何实现这个特性的。继承结构 WeakHashMap并不是继承自HashMap，而是继承自AbstractMap，跟HashMap的继承结构差不多。存储结构 WeakHashMap中的数据结构是数组+链表的形式，这一点跟HashMap也是一致的，但不同的是，在JDK8中，当发生较多key冲突的时候，HashMap中会由链表转为红黑树，而WeakHashMap则一直使用链表进行存储。成员变量 // 默认初始容量，必须是2的幂 private static final int DEFAULT_INITIAL_CAPACITY = 16; // 最大容量 private static final int MAXIMUM_CAPACITY = 1 << 30; // 默认装载因子 private static final float DEFAULT_LOAD_FACTOR = 0.75f; // Entry数组，长度必须为2的幂 Entry<K,V>[] table; // 元素个数 private int size; // 阈值 private int threshold; // 装载因子 private final float loadFactor; // 引用队列 private final ReferenceQueue<Object> queue = new ReferenceQueue<>(); // 修改次数 int modCount; 跟HashMap的成员变量几乎一致，这里多了一个ReferenceQueue，用来存放那些已经被回收了的弱引用对象。如果想知道ReferenceQueue是如何工作的，可以参考这篇文章。构造函数 WeakHashMap中也有四个构造函数： public WeakHashMap(int initialCapacity, float loadFactor) { ... } public WeakHashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public WeakHashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } public WeakHashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); putAll(m); } 可以看到后三个，都是调用的第一个构造函数，下面再来看一下第一个构造函数的内容： // 校验initialCapacity if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Initial Capacity: "+ initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 校验loadFactor if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal Load factor: "+ loadFactor); int capacity = 1; // 将容量设置为大于initialCapacity的最小2的幂 while (capacity < initialCapacity) capacity <<= 1; table = newTable(capacity); this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); 再看看newTable函数。 private Entry<K,V>[] newTable(int n) { return (Entry<K,V>[]) new Entry<?,?>[n]; } 这里其实只是简单的创建一个Entry数组。 Entry剖析接下来看看WeakHashMap中的核心角色——Entry。上面已经看到了，WeakHashMap中的table是一个Entry数组： Entry<K,V>[] table; 来看看Entry长什么样： private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> { ... } Entry继承自WeakReference，继承关系图如下：再来看看Entry中的内容： // 成员变量 V value; final int hash; Entry<K,V> next; // 构造函数 Entry(Object key, V value, ReferenceQueue<Object> queue, int hash, Entry<K,V> next) { super(key, queue); this.value = value; this.hash = hash; this.next = next; } 细心的你可能会发现，哎？key哪里去了，成员变量里没有key。别着急，看看构造函数就可以发现，它调用了父类的构造函数。 super(key, queue); 这里调用的WeakReference的构造函数，将key传入Reference中，保存在referent成员变量中。对Reference和WeakReference不熟悉的话可以参考这篇文章和这篇文章。再看看其它几个方法： @SuppressWarnings("unchecked") public K getKey() { // 这里调用了Reference的get方法，从中取出referent对象 // WeakHashMap中，key如果为null会使用NULL_KEY来替代 return (K) WeakHashMap.unmaskNull(get()); } public V getValue() { return value; } public V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>)o; K k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { V v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public int hashCode() { K k = getKey(); V v = getValue(); // 这里只是简单的把key和value的hashcode做一个异或处理 return Objects.hashCode(k) ^ Objects.hashCode(v); } public String toString() { return getKey() + "=" + getValue(); } 这里稍微说一下getKey方法，调用了WeakHashMap.unmaskNull，之所以要调用这个方法，其实是因为WeakHashMap中对key为null时的特殊处理，会将其指向一个特殊的内部变量： private static final Object NULL_KEY = new Object(); 与其对应的两个方法便是： private static Object maskNull(Object key) { return (key == null) ? NULL_KEY : key; } static Object unmaskNull(Object key) { return (key == NULL_KEY) ? null : key; } 所以，其他WeakHashMap中的Entry最大的不同就是继承自WeakReference，并把key保存在了WeakReference中。可以说WeakHashMap的特性绝大部分都是WeakReference的功劳。常用方法主要的方法有这些： void clear() Object clone() boolean containsKey(Object key) boolean containsValue(Object value) Set<Entry<K, V>> entrySet() V get(Object key) boolean isEmpty() Set<K> keySet() V put(K key, V value) void putAll(Map<? extends K, ? extends V> map) V remove(Object key) int size() Collection<V> values() 这里选其中的三个最常用的方法进行解析： put方法 public V put(K key, V value) { // 处理null值 Object k = maskNull(key); // 计算hash int h = hash(k); // 获取table Entry<K,V>[] tab = getTable(); // 计算下标 int i = indexFor(h, tab.length); // 查找Entry for (Entry<K,V> e = tab[i]; e != null; e = e.next) { if (h == e.hash && eq(k, e.get())) { V oldValue = e.value; if (value != oldValue) e.value = value; return oldValue; } } modCount++; Entry<K,V> e = tab[i]; tab[i] = new Entry<>(k, value, queue, h, e); // 如果元素个数超过阈值，则进行扩容 if (++size >= threshold) resize(tab.length * 2); return null; } 这里涉及到的方法比较多，不慌不慌，一个一个来。先来看看hash方法： final int hash(Object k) { int h = k.hashCode(); // 这里做了二次散列，来扩大低位的影响 h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } hash方法对key的hashcode进行了二次散列，主要是为了扩大低位的影响。因为Entry数组的大小是2的幂，在进行查找的时候，进行掩码处理，如果不进行二次散列，那么低位对index就完全没有影响了，如果不清楚也没有关系，之后在get方法里会有说明。至于为什么要选20,12,7,4。emmm，大概是效果奇佳吧（一本正经的胡说八道，有兴趣的话可以自行研究）。再看看indexFor函数，这里就是将数组长度减1后与hashcode做一个位与操作，因为length必定是2的幂，所以减1后就变成了掩码，再进行与操作就能直接得到hashcode mod length的结果了，但是这样操作效率会更高。 private static int indexFor(int h, int length) { return h & (length-1); } 再来看看getTable方法： private Entry<K,V>[] getTable() { // 清除被回收的Entry对象 expungeStaleEntries(); return table; } private void expungeStaleEntries() { for (Object x; (x = queue.poll()) != null; ) { // 循环获取引用队列中的对象 synchronized (queue) { @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) x; // 查找对应的位置 int i = indexFor(e.hash, table.length); // 找到之前的Entry Entry<K,V> prev = table[i]; Entry<K,V> p = prev; // 在链表中寻找 while (p != null) { Entry<K,V> next = p.next; if (p == e) { if (prev == e) table[i] = next; else prev.next = next; // 将对应的value置为null，帮助GC回收 e.value = null; size--; break; } prev = p; p = next; } } } } 所以每次调用getTable的时候，都会将table中key已经被回收掉的Entry移除掉。 resize方法： void resize(int newCapacity) { // 获取当前table Entry<K,V>[] oldTable = getTable(); int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // 新建一个table Entry<K,V>[] newTable = newTable(newCapacity); // 将旧table中的内容复制到新table中 transfer(oldTable, newTable); table = newTable; if (size >= threshold / 2) { threshold = (int)(newCapacity * loadFactor); } else { expungeStaleEntries(); transfer(newTable, oldTable); table = oldTable; } } // 新建Entry数组 private Entry<K,V>[] newTable(int n) { return (Entry<K,V>[]) new Entry<?,?>[n]; } private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) { for (int j = 0; j < src.length; ++j) { Entry<K,V> e = src[j]; src[j] = null; while (e != null) { Entry<K,V> next = e.next; Object key = e.get(); if (key == null) { e.next = null; e.value = null; size--; } else { int i = indexFor(e.hash, dest.length); e.next = dest[i]; dest[i] = e; } e = next; } } } get方法 public V get(Object key) { // 对null值特殊处理 Object k = maskNull(key); // 取key的hash值 int h = hash(k); // 取当前table Entry<K,V>[] tab = getTable(); // 获取下标 int index = indexFor(h, tab.length); Entry<K,V> e = tab[index]; // 链表中查找元素 while (e != null) { if (e.hash == h && eq(k, e.get())) return e.value; e = e.next; } return null; } 在查找元素的时候调用了一个eq方法： private static boolean eq(Object x, Object y) { return x == y || x.equals(y); } remove方法 public V remove(Object key) { // 对null值特殊处理 Object k = maskNull(key); // 取key的hash int h = hash(k); // 取当前table Entry<K,V>[] tab = getTable(); // 计算下标 int i = indexFor(h, tab.length); Entry<K,V> prev = tab[i]; Entry<K,V> e = prev; while (e != null) { Entry<K,V> next = e.next; // 查找对应Entry if (h == e.hash && eq(k, e.get())) { modCount++; size--; if (prev == e) tab[i] = next; else prev.next = next; // 如果找到，返回对应Entry的value return e.value; } prev = e; e = next; } return null; } 使用栗子 public class WeakHashMapTest { public static void main(String[] args){ testWeakHashMap(); } private static void testWeakHashMap() { // 创建3个String对象用来做key String w1 = new String("key1"); String w2 = new String("key2"); String w3 = new String("key3"); // 新建WeakHashMap Map weakHashMap = new WeakHashMap(); // 添加键值对 weakHashMap.put(w1, "v1"); weakHashMap.put(w2, "v2"); weakHashMap.put(w3, "v3"); // 打印出weakHashMap System.out.printf("weakHashMap:%s\n", weakHashMap); // containsKey(Object key) :是否包含键key System.out.printf("contains key key1 : %s\n",weakHashMap.containsKey("key1")); System.out.printf("contains key key4 : %s\n",weakHashMap.containsKey("key4")); // containsValue(Object value) :是否包含值value System.out.printf("contains value v1 : %s\n",weakHashMap.containsValue("v1")); System.out.printf("contains value 0 : %s\n",weakHashMap.containsValue(0)); // remove(Object key) ：删除键key对应的键值对 weakHashMap.remove("three"); System.out.printf("weakHashMap: %s\n", weakHashMap); // ---- 测试 WeakHashMap 的自动回收特性 ---- // 将w1设置null。 // 这意味着“弱键”w1再没有被其它对象引用，调用gc时会回收WeakHashMap中与“w1”对应的键值对 w1 = null; // 内存回收。这里，会回收WeakHashMap中与“w1”对应的键值对 System.gc(); // 遍历WeakHashMap Iterator iter = weakHashMap.entrySet().iterator(); while (iter.hasNext()) { Map.Entry en = (Map.Entry)iter.next(); System.out.printf("next : %s - %s\n",en.getKey(),en.getValue()); } // 打印WeakHashMap的实际大小 System.out.printf("after gc WeakHashMap size:%s\n", weakHashMap.size()); } } 输出如下： weakHashMap:{key1=w1, key2=w2, key3=w3} contains key key1 : true contains key key4 : false contains value w1 : true contains value 0 : false weakHashMap: {key1=w1, key2=w2, key3=w3} next : key2 - w2 next : key3 - w3 after gc WeakHashMap size:2 可以看到，w1对应的Entry被回收掉了，这就是WeakHashMap的最重要特性，当然，实际使用的时候一般不会这样使用，应用场景由于WeakHashMap可以自动清除Entry，所以比较适合用于存储非必需对象，用作缓存非常合适。 public final class ConcurrentCache<K,V> { private final int size; private final Map<K,V> eden; private final Map<K,V> longterm; public ConcurrentCache(int size) { this.size = size; this.eden = new ConcurrentHashMap<>(size); this.longterm = new WeakHashMap<>(size); } public V get(K k) { V v = this.eden.get(k); if (v == null) { synchronized (longterm) { v = this.longterm.get(k); } if (v != null) { this.eden.put(k, v); } } return v; } public void put(K k, V v) { if (this.eden.size() >= size) { synchronized (longterm) { this.longterm.putAll(this.eden); } this.eden.clear(); } this.eden.put(k, v); } } 在put方法里，在插入一个键值对时，先检查eden缓存的容量是不是超过了阈值，如果没有超就直接放入eden缓存，如果超了就将eden中所有的键值对都放入longterm（这里longterm类似于老年代，eden类似于年轻代），再将eden清空并插入相应键值对。在get方法中，也是优先从eden中找对应的value，如果没有则进入longterm缓存中查找，找到后就加入eden缓存并返回。这样设计的好处是，能将相对常用的对象都能在eden缓存中找到，不常用的则存入longterm缓存，并且由于WeakHashMap能自动清除Entry，所以不用担心longterm中键值对过多而导致OOM。 WeakHashMap还有这样一个不错的应用场景，配合事务进行使用，存储事务过程中的各类信息。可以使用如下结构： WeakHashMap<String,Map<K,V>> transactionCache; 这里key为String类型，可以用来标志区分不同的事务，起到一个事务id的作用。value是一个map，可以是一个简单的HashMap或者LinkedHashMap，用来存放在事务中需要使用到的信息。在事务开始时创建一个事务id，并用它来作为key，事务结束后，将这个强引用消除掉，这样既能保证在事务中可以获取到所需要的信息，又能自动释放掉map中的所有信息。小结 WeakHashMap是一个会自动清除Entry的Map WeakHashMap的操作与HashMap完全一致 WeakHashMap内部数据结构是数组+链表 WeakHashMap常被用作缓存

2018-10-09

一行代码让你的python运行速度提高100倍

“一行代码让python的运行速度提高100倍”这绝不是哗众取宠的论调。我们来看一下这个最简单的例子，从1一直累加到1亿。

2018-09-19

【Java入门提高篇】Day33 Java容器类详解（十五）PriorityQueue详解

今天要介绍的是基础容器类（为了与并发容器类区分开来而命名的名字）中的另一个成员——PriorityQueue，它的大名叫做优先级队列，想必即使没有用过也该有所耳闻吧，什么？没。。没听过？emmm。。。那就更该认真看看了。通过本篇你将了解到： 1、PriorityQueue是什么？ 2、PriorityQueue的内部结构是什么？ 3、二叉堆、大顶堆、小顶堆分别是什么？有什么特性？ 4、小顶堆是如何实现的，如何用数组表示？ 5、小顶堆的删除、插入操作是如何进行的？ 6、PriorityQueue的源码解析。 7、PriorityQueue的应用场景。一、PriorityQueue简介 PriorityQueue也是Queue的一个继承者，相比于一般的列表，它的特点便如它的名字一样，出队的时候可以按照优先级进行出队，所以不像LinkedList那样只能按照插入的顺序出队，PriorityQueue是可以根据给定的优先级顺序进行出队的。这里说的给定优先级顺序既可以是内部比较器，也可以是外部比较器。PriorityQueue内部是根据小顶堆的结构进行存储的，所谓小顶堆的意思，便是最小的元素总是在最上面，每次出队总是将堆顶元素移除，这样便能让出队变得有序，至于什么是小顶堆，后面会有详细介绍。比如说，比较常见的场景就是任务队列，队列动态插入，后面的任务优先级高的需要被先执行，那么使用优先级队列就可以比较好的实现这样的需求。下面我们模拟一下这个场景： public class PriorityQueueTest { public static void main(String[] args){ // 传入外部比较器， //PriorityQueue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority)); //PriorityQueue<Task> taskQueue = new PriorityQueue<>((t1, t2) -> t1.getPriority() - t2.getPriority()); PriorityQueue<Task> taskQueue = new PriorityQueue<>(new Comparator<Task>() { @Override public int compare(Task t1, Task t2) { return t1.getPriority() - t2.getPriority(); } }); // 添加六个任务 taskQueue.add(new Task(1, "learn java")); taskQueue.add(new Task(3, "learn c++")); taskQueue.add(new Task(4, "learn c#")); taskQueue.add(new Task(2, "learn python")); taskQueue.add(new Task(2, "learn php")); taskQueue.add(new Task(5, "learn js")); // 出队 while (!taskQueue.isEmpty()){ System.out.println(taskQueue.poll()); } } } class Task{ /** * 任务优先级 */ private int priority; /** * 任务名称 */ private String taskName; public Task() { } public Task(int priority, String taskName) { this.priority = priority; this.taskName = taskName; } public int getPriority() { return priority; } public void setPriority(int priority) { this.priority = priority; } public String getTaskName() { return taskName; } public void setTaskName(String taskName) { this.taskName = taskName; } @Override public String toString() { return "Task{" + "priority=" + priority + ", taskName='" + taskName + '\'' + '}'; } } 输出如下： Task{priority=1, taskName='learn java'} Task{priority=2, taskName='learn python'} Task{priority=2, taskName='learn php'} Task{priority=3, taskName='learn c++'} Task{priority=4, taskName='learn c#'} Task{priority=5, taskName='learn js'} 可以看到，输出的时候是按照我们设定的优先级顺序进行输出的，由于默认的是小顶堆，所以这里Priority值小的会被先输出。二、PriorityQueue的内部结构上面已经提到了，PriorityQueue的内部结构其实是按照小顶堆的结构进行存储的，那么什么是小顶堆呢？说到小顶堆，还是先从堆开始介绍吧。堆和栈一样是一种很基础的数据结构，在维基百科中的介绍如下：堆（英语：Heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。用图来表示的话就像这样：说完了堆，再来聊聊它的进化版——二叉堆，同样引用维基百科中的介绍：二叉堆（英语：binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。其中，最大堆也叫做大顶堆或者大根堆，最小堆也叫做小顶堆或者小根堆。上面的图一其实就是一个大顶堆，而图二则是小顶堆。PriorityQueue是通过数组表示的小顶堆实现的，既然如此，PriorityQueue的排序特性自然与小顶堆的特性一致，下面便介绍小顶堆如何使用数组进行表示以及插入删除时的调整。下面是一个由10，16，20，22，18，25，26，30，24，23构成的小顶堆：将其从第一个元素开始依次从上到下，从左到右给每个元素添加一个序号，从0开始，这样就得到了相应元素在数组中的位置，而且这个序号是很有规则的，第k个元素的左孩子的序号为2k+1，右孩子的序号为2k+2，这样就很容易根据序号直接算出对应孩子的位置，时间复杂度为o(1)。这也就是为什么可以用数组来存储堆结构的原因了。再来看看小顶堆是如何插入元素的，假设我们插入一个元素15：插入元素的调整其实很简单，就是先插入到最后，然后再依次与其父节点进行比较，如果小于其父节点，则互换，直到不需要调整或者父节点为null为止。那再来看看移除元素：嗯，过程其实也很简单，先用最后的元素当替补，然后再从上往下进行调整。三、PriorityQueue源码解析小顶堆已经介绍完了，那PriorityQueue就没什么内容可讲了，嗯，那散了吧好了好了，不开玩笑了，接下来让我们一起来看看源码中是如何实现的。先来继承结构： PriorityQueue继承自AbstractQueue，像这样的Abstract开头的抽象类，想必应该不陌生了，就是继承自指定接口然后进行了一些默认实现。来看看PriorityQueue的内部成员： // 默认初始化容量 private static final int DEFAULT_INITIAL_CAPACITY = 11; /** * 优先级队列是使用平衡二叉堆表示的: 节点queue[n]的两个孩子分别为 * queue[2*n+1] 和 queue[2*(n+1)]. 队列的优先级是由比较器或者 * 元素的自然排序决定的，对于堆中的任意元素n，其后代d满足：n<=d * 如果堆是非空的，则堆中最小值为queue[0]。 */ transient Object[] queue; /** * 队列中元素个数 */ private int size = 0; /** * 比较器 */ private final Comparator<? super E> comparator; /** * 修改次数 */ transient int modCount = 0; 可以看到内部使用的是一个Object数组进行元素的存储，并对该数组进行了详细的注释，所以不管是根据子节点找父节点，还是根据父节点找子节点都肥肠的方便。再来看看它的构造函数，有点多，一共有六个构造函数： /** * 使用默认的容量（11）来构造一个空的优先级队列，使用元素的自然顺序进行排序（此时元素必须实现comparable接口） */ public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } /** * 使用指定容量来构造一个空的优先级队列，使用元素的自然顺序进行排序（此时元素必须实现comparable接口） * 但如果指定的容量小于1则会抛出异常 */ public PriorityQueue(int initialCapacity) { this(initialCapacity, null); } /** * 使用默认的容量（11）构造一个优先级队列，使用指定的比较器进行排序 */ public PriorityQueue(Comparator<? super E> comparator) { this(DEFAULT_INITIAL_CAPACITY, comparator); } /** * 使用指定容量创建一个优先级队列，并使用指定比较器进行排序。 * 但如果指定的容量小于1则会抛出异常 */ public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) { if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; } /** * 使用指定集合的所有元素构造一个优先级队列， * 如果该集合为SortedSet或者PriorityQueue类型，则会使用相同的顺序进行排序， * 否则，将使用元素的自然排序（此时元素必须实现comparable接口），否则会抛出异常 * 并且集合中不能有null元素，否则会抛出异常 */ @SuppressWarnings("unchecked") public PriorityQueue(Collection<? extends E> c) { if (c instanceof SortedSet<?>) { SortedSet<? extends E> ss = (SortedSet<? extends E>) c; this.comparator = (Comparator<? super E>) ss.comparator(); initElementsFromCollection(ss); } else if (c instanceof PriorityQueue<?>) { PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c; this.comparator = (Comparator<? super E>) pq.comparator(); initFromPriorityQueue(pq); } else { this.comparator = null; initFromCollection(c); } } /** * 使用指定的优先级队列中所有元素来构造一个新的优先级队列. 将使用原有顺序进行排序。 */ @SuppressWarnings("unchecked") public PriorityQueue(PriorityQueue<? extends E> c) { this.comparator = (Comparator<? super E>) c.comparator(); initFromPriorityQueue(c); } /** * 根据指定的有序集合创建一个优先级队列，将使用原有顺序进行排序 */ @SuppressWarnings("unchecked") public PriorityQueue(SortedSet<? extends E> c) { this.comparator = (Comparator<? super E>) c.comparator(); initElementsFromCollection(c); } 从集合中构造优先级队列的时候，调用了几个初始化函数： private void initFromPriorityQueue(PriorityQueue<? extends E> c) { if (c.getClass() == PriorityQueue.class) { this.queue = c.toArray(); this.size = c.size(); } else { initFromCollection(c); } } private void initElementsFromCollection(Collection<? extends E> c) { Object[] a = c.toArray(); // If c.toArray incorrectly doesn't return Object[], copy it. if (a.getClass() != Object[].class) a = Arrays.copyOf(a, a.length, Object[].class); int len = a.length; if (len == 1 || this.comparator != null) for (int i = 0; i < len; i++) if (a[i] == null) throw new NullPointerException(); this.queue = a; this.size = a.length; } private void initFromCollection(Collection<? extends E> c) { initElementsFromCollection(c); heapify(); } initFromPriorityQueue即从另外一个优先级队列构造一个新的优先级队列，此时内部的数组元素不需要进行调整，只需要将原数组元素都复制过来即可。但是从其他非PriorityQueue的集合中构造优先级队列时，需要先将元素复制过来后再进行调整，此时调用的是heapify方法： private void heapify() { // 从最后一个非叶子节点开始从下往上调整 for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); } // 划重点了，这个函数即对应上面的元素删除时从上往下调整的步骤 private void siftDown(int k, E x) { if (comparator != null) // 如果比较器不为null，则使用比较器进行比较 siftDownUsingComparator(k, x); else // 否则使用元素的compareTo方法进行比较 siftDownComparable(k, x); } private void siftDownUsingComparator(int k, E x) { // 使用half记录队列size的一半，如果比half小的话，说明不是叶子节点 // 因为最后一个节点的序号为size - 1，其父节点的序号为(size - 2) / 2或者(size - 3 ) / 2 // 所以half所在位置刚好是第一个叶子节点 int half = size >>> 1; while (k < half) { // 如果不是叶子节点，找出其孩子中较小的那个并用其替换 int child = (k << 1) + 1; Object c = queue[child]; int right = child + 1; if (right < size && comparator.compare((E) c, (E) queue[right]) > 0) c = queue[child = right]; if (comparator.compare(x, (E) c) <= 0) break; // 用c替换 queue[k] = c; k = child; } // queue[k] = x; } // 同上，只是比较的时候使用的是元素的compareTo方法 private void siftDownComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>)x; int half = size >>> 1; // 如果是非叶子节点则继续循环 while (k < half) { int child = (k << 1) + 1; Object c = queue[child]; int right = child + 1; if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) c = queue[child = right]; if (key.compareTo((E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = key; } 这里可能一眼看过去有点难以理解，嗯，那就多看两眼吧。 siftDown方法是这里面比较重要的方法之一，有两个参数，一个是序号k，另一个是元素x，这个方法的作用，便是把x从k开始往下调整，使得在节点k在其子树的每相邻层中，父节点都小于其子节点。所以heapify的作用就比较明显了，从最后一个非叶子节点开始，从下往上依次调整其子树，使得最终得到的树里，根节点是最小的。这里要先理解一下为什么heapify中i的初始值要设置为(size >>> 1) - 1。因为这是最后一个非叶子节点的位置，不信的话可以随便画几个图验证一下，至于在siftDownUsingComparator方法中，int half = size >>> 1;这里half则是第一个叶子节点的位置，小于这个序号的节点都是非叶子节点，这里也可以画图验证，当然，注释中我已经做了解释。说了这么多，也许还是不太明白，以集合{14,7,12,6,9,4,17,23,10,15,3}为例画个图吧：嗯，这样最小的元素就被顶上去了，有没有觉得有点像冒泡排序，嗯，确实有点像。 siftDown说完了，再来看一眼siftUp吧，这里操作是十分类似的。 private void siftUp(int k, E x) { if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); } @SuppressWarnings("unchecked") private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = key; } @SuppressWarnings("unchecked") private void siftUpUsingComparator(int k, E x) { while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (comparator.compare(x, (E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = x; } 嗯，相信如果理解了siftDown的话，这里应该就不难理解了吧，如果还有疑问，欢迎留言。再来看看几个常用的方法： public boolean add(E e) { return offer(e); } public boolean offer(E e) { if (e == null) throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) grow(i + 1); size = i + 1; if (i == 0) queue[0] = e; else siftUp(i, e); return true; } // 扩容函数 private void grow(int minCapacity) { int oldCapacity = queue.length; // 如果当前容量比较小（小于64）的话进行双倍扩容，否则扩容50% int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // 如果发现扩容后溢出了，则进行调整 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } public boolean contains(Object o) { return indexOf(o) != -1; } private int indexOf(Object o) { if (o != null) { // 查找时需要进行全局遍历，比搜索二叉树的查找效率要低 for (int i = 0; i < size; i++) if (o.equals(queue[i])) return i; } return -1; } public E poll() { if (size == 0) return null; int s = --size; modCount++; E result = (E) queue[0]; E x = (E) queue[s]; queue[s] = null; if (s != 0) siftDown(0, x); return result; } 这里对照一下最开始说的小顶堆的插入和移除就能比较好的理解了。最后源码中还有一个remove方法，需要稍微说明一下： // 这里不是移除堆顶元素，而是移除指定元素 public boolean remove(Object o) { // 先找到该元素的位置 int i = indexOf(o); if (i == -1) return false; else { removeAt(i); return true; } } // 移除指定序号的元素 private E removeAt(int i) { // assert i >= 0 && i < size; modCount++; // s为最后一个元素的序号 int s = --size; if (s == i) queue[i] = null; else { // moved记录最后一个元素的值 E moved = (E) queue[s]; queue[s] = null; // 用最后一个元素代替要移除的元素，并向下进行调整 siftDown(i, moved); // 如果向下调整后发现moved还在该位置，则再向上进行调整 if (queue[i] == moved) { siftUp(i, moved); if (queue[i] != moved) return moved; } } return null; } 当移除的不是堆顶元素的时候，同样先用最后一个元素代替，然后先从被移除的位置开始向下调整，如果发现没有改动，则再向上调整。四、PriorityQueue的应用场景最后，来聊聊PriorityQueue的应用场景，由于内部是用数组实现的小顶堆，所以堆适用的场景它都适用，比如典型的从n个元素中取出最小（最大）的前k个，这样的场景适用PriorityQueue就能以比较小的空间代价和还算ok的时间代价进行实现，另外，优先级队列适用场景的特点便是需要动态插入元素，并且元素有优先级，需要根据一定的规则进行优先级排序。下面以从10000个整数中取出最大的10个整数为例进行介绍。 public class Test { public static void main(String[] args){ ArrayList<Integer> integers = new ArrayList<>(10000); Random random = new Random(); for (int i = 0; i < 10000; i++) { Integer integer = random.nextInt(); if (!integers.contains(integer)) integers.add(integer); } Integer[] largest = getLargest10(integers); for (Integer i : largest){ System.out.print(i + " "); } System.out.println(); // 验证一下是否是最大的前10个 integers.sort(Comparator.comparingInt(Integer::intValue)); ArrayList<Integer> largest2 = new ArrayList<>(10); for (int i = integers.size() - 1; i >= integers.size() - 10; i--){ largest2.add(integers.get(i)); } // 在largest数组中查找 System.out.println(Arrays.asList(largest).containsAll(largest2)); } public static Integer[] getLargest10(ArrayList<Integer> integers){ PriorityQueue<Integer> queue = new PriorityQueue<>(10); for (Integer integer : integers){ queue.add(integer); if (queue.size() > 10){ queue.poll(); } } return queue.toArray(new Integer[10]); } } 输出如下，由于是取的随机数，所以每个人的输出都会不一样。 2143974860 2143998490 2144350843 2145111627 2144739333 2145674658 2144667271 2145543903 2147209906 2145466260 true 最后，我们来回答一下开头的问题： 1、PriorityQueue是什么？PriorityQueue是优先级队列，取出元素时会根据元素的优先级进行排序。 2、PriorityQueue的内部结构是什么？PriorityQueue内部是一个用数组实现的小顶堆。 3、二叉堆、大顶堆、小顶堆分别是什么？有什么特性？二叉堆是完全二叉树或者近完全二叉树，大顶堆即所有父节点大于子节点，小顶堆即所有父节点小于子节点。 4、小顶堆是如何实现的，如何用数组表示？小顶堆是用二叉树实现的，用数组表示时，父节点n的左孩子为2n+1，右孩子的序号为2n+2。 5、小顶堆的删除、插入操作是如何进行的？小顶堆删除堆顶元素后用最后一个元素替补，然后从上往下调整，插入一个元素时，先放到最后的位置，然后再从下往上调整。 6、PriorityQueue的源码解析。如上。 7、PriorityQueue的应用场景。适用于需要动态插入元素，且元素有优先级顺序的场景。到此，本篇圆满结束。如果觉得还不错的话，记得动动小手点个赞，也欢迎关注博主，你们的支持是我写出更好博客的动力。有兴趣对Java进行更深入学习和交流的小伙伴，欢迎加入QQ群交流：529253292

2018-09-08

【Java入门提高篇】Day32 Java容器类详解（十四）ArrayDeque详解

今天来介绍一个不太常见也不太常用的类——ArrayDeque，这是一个很不错的容器类，如果对它还不了解的话，那么就好好看看这篇文章吧。看完本篇，你将会了解到： 1、ArrayDeque是什么？ 2、ArrayDeque如何使用？ 3、ArrayDeque的内部结构是怎样的？ 4、ArrayDeque的各个方法是如何实现的？ 5、ArrayDeque是如何扩容的？ 6、ArrayDeque的容量有什么限制？ 7、ArrayDeque和LinkedList相比有什么优势？ 8、ArrayDeque的应用场景是什么？一、ArrayDeque简介 ArrayDeque是JDK容器中的一个双端队列实现，内部使用数组进行元素存储，不允许存储null值，可以高效的进行元素查找和尾部插入取出，是用作队列、双端队列、栈的绝佳选择，性能比LinkedList还要好。听到这里，不熟悉ArrayDeque的你是不是有点尴尬？JDK中竟然还有这么好的一个容器类？别慌，现在了解还来得及，趁响指还没有弹下去，快上车吧，没时间解释了。来看一个ArrayDeque的使用小栗子： public class DequeTest { public static void main(String[] args){ // 初始化容量为4 ArrayDeque<String> arrayDeque = new ArrayDeque<>(4); //添加元素 arrayDeque.add("A"); arrayDeque.add("B"); arrayDeque.add("C"); arrayDeque.add("D"); arrayDeque.add("E"); arrayDeque.add("F"); arrayDeque.add("G"); arrayDeque.add("H"); arrayDeque.add("I"); System.out.println(arrayDeque); // 获取元素 String a = arrayDeque.getFirst(); String a1 = arrayDeque.pop(); String b = arrayDeque.element(); String b1 = arrayDeque.removeFirst(); String c = arrayDeque.peek(); String c1 = arrayDeque.poll(); String d = arrayDeque.pollFirst(); String i = arrayDeque.pollLast(); String e = arrayDeque.peekFirst(); String h = arrayDeque.peekLast(); String h1 = arrayDeque.removeLast(); System.out.printf("a = %s, a1 = %s, b = %s, b1 = %s, c = %s, c1 = %s, d = %s, i = %s, e = %s, h = %s, h1 = %s", a,a1,b,b1,c,c1,d,i,e,h,h1); System.out.println(); // 添加元素 arrayDeque.push(e); arrayDeque.add(h); arrayDeque.offer(d); arrayDeque.offerFirst(i); arrayDeque.offerLast(c); arrayDeque.offerLast(h); arrayDeque.offerLast(c); arrayDeque.offerLast(h); arrayDeque.offerLast(i); arrayDeque.offerLast(c); System.out.println(arrayDeque); // 移除第一次出现的C arrayDeque.removeFirstOccurrence(c); System.out.println(arrayDeque); // 移除最后一次出现的C arrayDeque.removeLastOccurrence(c); System.out.println(arrayDeque); } } 输出如下： [A, B, C, D, E, F, G, H, I] a = A, a1 = A, b = B, b1 = B, c = C, c1 = C, d = D, i = I, e = E, h = H, h1 = H [I, E, E, F, G, H, D, C, H, C, H, I, C] [I, E, E, F, G, H, D, H, C, H, I, C] [I, E, E, F, G, H, D, H, C, H, I] 可以看到，从ArrayDeque中取出元素的姿势可谓是五花八门，不过别慌，稍后会对这些方法进行一一讲解，现在只需要知道，get、peek、element方法都是获取元素，但是不会将它移除，而pop、poll、remove都会将元素移除并返回，add和push、offer都是插入元素，它们的不同点在于插入元素的位置以及插入失败后的结果。二、ArrayDeque的内部结构 ArrayDeque的整体继承结构如下： ArrayDeque是继承自Deque接口，Deque继承自Queue接口，Queue是队列，而Deque是双端队列，也就是可以从前或者从后插入或者取出元素，也就是比队列存取更加方便一点，单向队列只能从一头插入，从另一头取出。再来看看ArrayDeque的内部结构，其实从名字就可以看出来，ArrayDeque自然是基于Array的双端队列，内部结构自然是数组： //存储元素的数组 transient Object[] elements; // 非private访问限制，以便内部类访问 /** * 头部节点序号 */ transient int head; /** * 尾部节点序号，（指向最后一点节点的后一个位置） */ transient int tail; /** * 双端队列的最小容量，必须是2的幂 */ private static final int MIN_INITIAL_CAPACITY = 8; 这里可以看到，元素都存储在Object数组中，head记录首节点的序号，tail记录尾节点后一个位置的序号，队列的容量最小为8，而且必须为2的幂。看到这里，有没有想到HashMap的元素个数限制也必须为2的幂，嗯，这里同HashMap一样，自有妙用，后面会有分析。三、ArrayDeque的常用方法从队列首部插入/取出从队列尾部插入/取出失败抛出异常失败返回特殊值失败抛出异常失败返回特殊值插入 addFirst(e) push() offerFirst(e) addLast(e) offerLast(e) 移除 removeFirst() pop() pollFirst() removeLast() pollLast() 获取 getFirst() peekFirst() getLast() peekLast() 嗯，几乎绝大多数常用方法都在这里了，基本上可以分成两类，一类是以add，remove，get开头的方法，这类方法失败后会抛出异常，一类是以offer，poll，peek开头的方法，这类方法失败之后会返回特殊值，如null。大部分方法基本上都是可以根据命名来推断其作用，如addFirst，当然就是从队列头部插入，removeLast，便是从队列尾部移除，get和peek只获取元素而不移除，getFirst方法调用时，如果队列为空，会抛出NoSuchElementException异常，而peekFirst在队列为空时调用则返回null。一下摆出这么多方法有些难以接受？别慌别慌，接下来让我们从源码的角度一起来看看这些方法，用图说话，来解释我们最开始那个栗子中到底发生了哪些事情。四、ArrayDeque源码分析先来看看构造函数： /** * 构造一个初始容量为16的空队列 */ public ArrayDeque() { elements = new Object[16]; } /** * 构造一个能容纳指定大小的空队列 */ public ArrayDeque(int numElements) { allocateElements(numElements); } /** * 构造一个包含指定集合所有元素的队列 */ public ArrayDeque(Collection<? extends E> c) { allocateElements(c.size()); addAll(c); } 所以之前栗子中， ArrayDeque<String> arrayDeque = new ArrayDeque<>(4); 调用的是第二个构造函数，里面有这么一个函数allocateElements，让我们来看看它的实现： 1 private void allocateElements(int numElements) { 2 elements = new Object[calculateSize(numElements)]; 3 } 4 5 private static int calculateSize(int numElements) { 6 int initialCapacity = MIN_INITIAL_CAPACITY; 7 if (numElements >= initialCapacity) { 8 initialCapacity = numElements; 9 initialCapacity |= (initialCapacity >>> 1); 10 initialCapacity |= (initialCapacity >>> 2); 11 initialCapacity |= (initialCapacity >>> 4); 12 initialCapacity |= (initialCapacity >>> 8); 13 initialCapacity |= (initialCapacity >>> 16); 14 initialCapacity++; 15 16 if (initialCapacity < 0) 17 initialCapacity >>>= 1; 18 } 19 return initialCapacity; 20 } allocateElements方法主要用于给内部的数组分配合适大小的空间，calculateSize方法用于计算比numElements大的最小2的幂次方，如果指定的容量大小小于MIN_INITIAL_CAPACITY（值为8），那么将容量设置为8，否则通过多次无符号右移进行最小2次幂计算。先将initialCapacity赋值为numElements，接下来，进行5次无符号右移，下面将以一个小栗子介绍这样运算的妙处。在Java中，int类型是占4字节，也就是32位。简单起见，这里以一个8位二进制数来演示前三次操作。假设这个二进制数对应的十进制为89，整个过程如下：可以看到最后，除了第一位，其他位全部变成了1，然后这个结果再加一，即得到大于89的最小的2次幂，怎么样，很巧妙吧，也许你会想，为什么右移的数值要分别是1，2，4，8，16呢？嗯，好问题。其实仔细观察就会发现，先右移在进行或操作，其实我们只需要关注第一个不为0的位即可，下面以64为例再演示一次：所以，事实上，在这系列操作中，其他位只是配角，我们只需要关注第一个不为0的位即可，假设其为第n位，先右移一位然后进行或操作，得到的结果，第n位和第n-1位肯定为1，这样就有两个位为1了，然后进行右移两位，再进行或操作，那么第n位到第n-3位一定都为1，然后右移4位，依次类推。int为32位，因此，最后只需要移动16位即可。1+2+4+8+16 = 31，所以经过这一波操作，原数字对应的二进制，操作得到的结果将是从其第一个不为0的位开始，往后的位均为1。然后： initialCapacity++; 再自增一下，目标完成。观察到还有下面这一小节代码： if (initialCapacity < 0) initialCapacity >>>= 1; 其实它是为了防止进行这一波操作之后，得到了负数，即原来第31位为1，得到的结果第32位将为1，第32位为符号位，1代表负数，这样的话就必须回退一步，将得到的数右移一位（即2 ^ 30）。嗯，那么这一部分就先告一段落了。来看看之前的那些函数。 public boolean add(E e) { addLast(e); return true; } /** * 在队列头部插入元素，如果元素为null，则抛出异常 */ public void addFirst(E e) { if (e == null) throw new NullPointerException(); elements[head = (head - 1) & (elements.length - 1)] = e; if (head == tail) doubleCapacity(); } /** * 在队列尾部插入元素，如果元素为null，则抛出异常 */ public void addLast(E e) { if (e == null) throw new NullPointerException(); elements[tail] = e; if ( (tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity(); } add的几个函数比较简单，在头部或者尾部插入元素，如果直接调用add方法，则是在尾部插入，这时直接在对应位置塞入该元素即可。 elements[tail] = e; 然后把tail记录其后一个位置，如果tail记录的位置已经是数组的最后一个位置了怎么办？嗯，这里又有一个巧妙的操作，跟HashMap中的取模是一样的： tail = (tail + 1) & (elements.length - 1) 因为elements.length是2的幂次方，所以减一后就变成了掩码，tail如果记录的是最后一个位置，即elements.length - 1，tail + 1 则等于elements.length，与elements.length - 1 做与操作后，就变成了0，嗯，没错，这样就变成了一个循环数组，如果tail与head相等，则表示没有剩余空间可以存放更多元素了，则调用doubleCapacity进行扩容： private void doubleCapacity() { assert head == tail; int p = head; int n = elements.length; int r = n - p; // number of elements to the right of p int newCapacity = n << 1; if (newCapacity < 0) throw new IllegalStateException("Sorry, deque too big"); Object[] a = new Object[newCapacity]; System.arraycopy(elements, p, a, 0, r); System.arraycopy(elements, 0, a, r, p); elements = a; head = 0; tail = n; } 扩容其实也是很简单粗暴的，先记录一下原来head的位置，然后把容量变为原来的两倍，然后把head之后的元素复制到新数组的开头，把剩余的元素复制到新数组之后。以之前的栗子为例，新建的ArrayDeque实例容量为8，然后我们调用add插入元素，插入H之后，tail指向第一个位置，与head重合，就会触发扩容。 arrayDeque.add("A"); arrayDeque.add("B"); arrayDeque.add("C"); arrayDeque.add("D"); arrayDeque.add("E"); arrayDeque.add("F"); arrayDeque.add("G"); arrayDeque.add("H"); arrayDeque.add("I"); 看图应该就比较清楚了，然后来看看获取元素的几个方法： // 获取元素 String a = arrayDeque.getFirst(); String a1 = arrayDeque.pop(); String b = arrayDeque.element(); String b1 = arrayDeque.removeFirst(); String c = arrayDeque.peek(); String c1 = arrayDeque.poll(); String d = arrayDeque.pollFirst(); String i = arrayDeque.pollLast(); String e = arrayDeque.peekFirst(); String h = arrayDeque.peekLast(); String h1 = arrayDeque.removeLast(); System.out.printf("a = %s, a1 = %s, b = %s, b1 = %s, c = %s, c1 = %s, d = %s, i = %s, e = %s, h = %s, h1 = %s", a,a1,b,b1,c,c1,d,i,e,h,h1); System.out.println(); getFirst方法直接取head位置的元素，如果为null则抛出异常。 public E getFirst() { @SuppressWarnings("unchecked") E result = (E) elements[head]; if (result == null) throw new NoSuchElementException(); return result; } getLast也是类似，取出tail所在位置的前一个位置，这里也做了掩码操作。 public E getLast() { @SuppressWarnings("unchecked") E result = (E) elements[(tail - 1) & (elements.length - 1)]; if (result == null) throw new NoSuchElementException(); return result; } element方法直接调用的是getFirst方法： public E element() { return getFirst(); } remove方法有三个： public E remove() { return removeFirst(); } public E removeFirst() { E x = pollFirst(); if (x == null) throw new NoSuchElementException(); return x; } public E removeLast() { E x = pollLast(); if (x == null) throw new NoSuchElementException(); return x; } remove方法其实是调用的对应的poll方法，poll方法也有三个： public E poll() { return pollFirst(); } public E pollFirst() { int h = head; @SuppressWarnings("unchecked") E result = (E) elements[h]; // 如果结果为null则返回null if (result == null) return null; elements[h] = null; // Must null out slot head = (h + 1) & (elements.length - 1); return result; } public E pollLast() { int t = (tail - 1) & (elements.length - 1); @SuppressWarnings("unchecked") E result = (E) elements[t]; if (result == null) return null; elements[t] = null; tail = t; return result; } 其实也很简单，都是先取出对应的元素，如果为null则返回null，否则取出对应的元素并对head或tail进行调整。 pop方法调用的是removeFirst方法，removeFIrst方法调用的是pollFirst方法，所以方法看起来这么多，实际上最后真正调用的就那么几个。 public E pop() { return removeFirst(); } peek方法是取出元素但是不移除，也有三个方法： public E peek() { return peekFirst(); } @SuppressWarnings("unchecked") public E peekFirst() { // elements[head] is null if deque empty return (E) elements[head]; } @SuppressWarnings("unchecked") public E peekLast() { return (E) elements[(tail - 1) & (elements.length - 1)]; } 这里没有做任何校验，所以如果如果取到的元素是null，返回的也是null。再来看看插入元素的其它几个方法： public boolean offer(E e) { return offerLast(e); } public boolean offerLast(E e) { addLast(e); return true; } public boolean offerFirst(E e) { addFirst(e); return true; } public void push(E e) { addFirst(e); } offer方法直接调用的是add方法。 emmm，都是相互调用，为啥要设置那么多方法呢？其实主要是为了模拟不同的数据结构，如栈操作：pop，push，peek，队列操作：add，offer，remove，poll，peek，element，双端队列操作：addFirst，addLast，getFirst，getLast，peekFirst，peekLast，removeFirst，removeLast，pollFirst，pollLast。不过确实稍微多了一点。之前的栗子里还有用到两个方法，removeFirstOccurrence和removeLastOccurrence，前者是移除首次出现的位置，后者是移除最后一次出现的位置。 public boolean removeFirstOccurrence(Object o) { if (o == null) return false; int mask = elements.length - 1; int i = head; Object x; while ( (x = elements[i]) != null) { if (o.equals(x)) { delete(i); return true; } i = (i + 1) & mask; } return false; } public boolean removeLastOccurrence(Object o) { if (o == null) return false; int mask = elements.length - 1; int i = (tail - 1) & mask; Object x; while ( (x = elements[i]) != null) { if (o.equals(x)) { delete(i); return true; } i = (i - 1) & mask; } return false; } 其实都是通过循环遍历的方式进行查找一个是从head开始往后查找，一个是从tail开始往前查找。最后，我们再来看看它的迭代器类。 public Iterator<E> iterator() { return new DeqIterator(); } private class DeqIterator implements Iterator<E> { private int cursor = head; private int fence = tail; private int lastRet = -1; public boolean hasNext() { return cursor != fence; } public E next() { if (cursor == fence) throw new NoSuchElementException(); @SuppressWarnings("unchecked") E result = (E) elements[cursor]; if (tail != fence || result == null) throw new ConcurrentModificationException(); lastRet = cursor; cursor = (cursor + 1) & (elements.length - 1); return result; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); if (delete(lastRet)) { cursor = (cursor - 1) & (elements.length - 1); fence = tail; } lastRet = -1; } public void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); Object[] a = elements; int m = a.length - 1, f = fence, i = cursor; cursor = f; while (i != f) { @SuppressWarnings("unchecked") E e = (E)a[i]; i = (i + 1) & m; if (e == null) throw new ConcurrentModificationException(); action.accept(e); } } } 在迭代器类中，cursor记录的是head的位置，fence记录的是tail的位置，lastRet记录的是调用next返回的元素的序号，如果调用了remove方法，lastRet会置为-1，这里没有像其它容器那样使用modCount来实现fast-fail机制，而是通过在next方法中进行修改判断。 // 如果移除了尾部元素，会导致 tail != fence // 如果移除了头部元素，会导致 result == null if (tail != fence || result == null) throw new ConcurrentModificationException(); 当然，这种检测比较弱，如果先移除一个尾部元素，然后再添加一个尾部元素，那么tail依旧和fence相等，这种情况就检测不出来了。在调用remove方法的时候，调用了一个delete方法，这是ArrayDeque类中的一个私有方法。 private boolean delete(int i) { // 先做不变性检测，判断是否当前结构满足删除需求 checkInvariants(); final Object[] elements = this.elements; // mask即掩码 final int mask = elements.length - 1; final int h = head; final int t = tail; // front代表i到头部的距离 final int front = (i - h) & mask; // back代表i到尾部的距离 final int back = (t - i) & mask; // 再次校验，如果i到头部的距离大于等于尾部到头部的距离，表示当前队列已经被修改了，通过最开始检测后，i是不应该满足该条件的 if (front >= ((t - h) & mask)) throw new ConcurrentModificationException(); // 为移动尽量少的元素做优化，如果离头部比较近，则将该位置到头部的元素进行移动，如果离尾部比较近，则将该位置到尾部的元素进行移动 if (front < back) { if (h <= i) { System.arraycopy(elements, h, elements, h + 1, front); } else { // Wrap around System.arraycopy(elements, 0, elements, 1, i); elements[0] = elements[mask]; System.arraycopy(elements, h, elements, h + 1, mask - h); } elements[h] = null; head = (h + 1) & mask; return false; } else { if (i < t) { // Copy the null tail as well System.arraycopy(elements, i + 1, elements, i, back); tail = t - 1; } else { // Wrap around System.arraycopy(elements, i + 1, elements, i, mask - i); elements[mask] = elements[0]; System.arraycopy(elements, 1, elements, 0, t); tail = (t - 1) & mask; } return true; } } 所以这个delete还是花了一点心思的，不仅做了两次校验，还对元素移动进行了优化。嗯，到此为止，源码部分就差不多了。那么现在再回到最开始提的问题。 1、ArrayDeque是什么？ArrayDeque是一个用循环数组实现的双端队列。 2、ArrayDeque如何使用？通过add，offer，poll等方法进行操作。 3、ArrayDeque的内部结构是怎样的？内部结构是一个循环数组。 4、ArrayDeque的各个方法是如何实现的？嗯，见上文。 5、ArrayDeque是如何扩容的？扩容成原来的两倍，然后将原来的内容复制到新数组中。 6、ArrayDeque的容量有什么限制？容量必须为2的幂次方，最小为8，默认为16. 7、ArrayDeque和LinkedList相比有什么优势？ArrayDeque通常来说比LinkedList更高效，因为可以在常量时间通过序号对元素进行定位，并且省去了对元素进行包装的空间和时间成本。 8、ArrayDeque的应用场景是什么？在很多场景下可以用来代替LinkedList，可以用做队列或者栈。到此，本篇圆满结束。如果觉得还不错的话，记得动动小手点个赞，也欢迎关注博主，你们的支持是我写出更好博客的动力。有兴趣对Java进行更深入学习和交流的小伙伴，欢迎加入QQ群交流：529253292

2018-09-06

【Java入门提高篇】Day31 Java容器类详解（十三）TreeSet详解

上一篇很水的介绍完了TreeMap，这一篇来看看更水的TreeSet。本文将从以下几个角度进行展开： 1、TreeSet简介和使用栗子 2、TreeSet源码分析本篇大约需食用10分钟，各位看官请随意享用。一、TreeSet简介 TreeSet是Set家族中的又一名懒将，跟其他两位一样，与对应的Map关系密不可分我们先来回顾一下其他两个Set类，HashSet借助于HashMap拥有快速元素插入和查找的特性，LinkedHashSet借助于LinkedHashMap拥有快速插入查找以及使元素保持插入顺序的特性，TreeSet则是借助于TreeMap拥有使内部元素保持有序的特性，当然，所有的Set集合类都有元素去重的特性。当然，要区别一下的是，TreeSet中的有序是指可以按照内部比较器或者外部比较器的顺序对插入的元素进行排序，也就是每次插入后都会调整顺序以保持内部元素整体有序，而LinkedHashSet只能保持元素的插入顺序。 Talkischeap，showme your code.嗯，还是来看代码吧： public class TreeSetTest { public static void main(String[] args){ TreeSet<String> treeSet = new TreeSet<>(); treeSet.add("Frank"); treeSet.add("Alice"); treeSet.add("Bob"); treeSet.add("Allen"); treeSet.add("Ada"); treeSet.add("Adora"); System.out.println(treeSet); LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>(); linkedHashSet.add("Frank"); linkedHashSet.add("Alice"); linkedHashSet.add("Bob"); linkedHashSet.add("Allen"); linkedHashSet.add("Ada"); linkedHashSet.add("Adora"); System.out.println(linkedHashSet); } } 输出如下： [Ada, Adora, Alice, Allen, Bob, Frank] [Frank, Alice, Bob, Allen, Ada, Adora] 可以看到TreeSet给插入的元素自动排序了。那么可不可以放入我们自定义的类元素呢？当然是可以的，不然要它何用 public class TreeSetTest { public static void main(String[] args){ List<Goods> goods = new ArrayList<>(); goods.add(new Goods("Iphone4S",500.00)); goods.add(new Goods("Iphone5",800.00)); goods.add(new Goods("Iphone6S",2500.00)); goods.add(new Goods("Iphone7S",4500.00)); goods.add(new Goods("Iphone8",6500.00)); goods.add(new Goods("IphoneX",8500.00)); System.out.println(goods); TreeSet<Goods> treeSet = new TreeSet<>(); treeSet.addAll(goods); System.out.println(treeSet); LinkedHashSet<Goods> linkedHashSet = new LinkedHashSet<>(); linkedHashSet.addAll(goods); System.out.println(linkedHashSet); } public static class Goods{ private String name; private Double price; public Goods(String name, Double price) { this.name = name; this.price = price; } public String getName() { return name; } public void setName(String name) { this.name = name; } public Double getPrice() { return price; } public void setPrice(Double price) { this.price = price; } @Override public String toString() { return "Goods{" + "name='" + name + '\'' + ", price=" + price + '}'; } } } 输出如下： Exception in thread "main" java.lang.ClassCastException: com.frank.chapter22.TreeSetTest$Goods cannot be cast to java.lang.Comparable [Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='IphoneX', price=8500.0}] at java.util.TreeMap.compare(TreeMap.java:1294) at java.util.TreeMap.put(TreeMap.java:538) at java.util.TreeSet.add(TreeSet.java:255) at java.util.AbstractCollection.addAll(AbstractCollection.java:344) at java.util.TreeSet.addAll(TreeSet.java:312) at com.frank.chapter22.TreeSetTest.main(TreeSetTest.java:25) 欢迎来到大型翻车现场。。。别慌别慌，问题不大。TreeSet与TreeMap一样，是需要元素实现Comparable接口或者传入一个外部比较器的。为什么String可以不用？看看String的实现吧，人家可是实现了Comparable接口的。所以有两种方式解决，一种是让Goods类实现Comparable接口，另一种是传入一个外部比较器，我们先来看第一种： public class TreeSetTest { public static void main(String[] args){ List<Goods> goods = new ArrayList<>(); goods.add(new Goods("Iphone7S",4500.00)); goods.add(new Goods("Iphone4S",500.00)); goods.add(new Goods("Iphone5",800.00)); goods.add(new Goods("IphoneX",8500.00)); goods.add(new Goods("Iphone6S",2500.00)); goods.add(new Goods("Iphone8",6500.00)); goods.add(new Goods("Iphone8",6500.00)); System.out.println(goods); TreeSet<Goods> treeSet = new TreeSet<>(); treeSet.addAll(goods); System.out.println(treeSet); LinkedHashSet<Goods> linkedHashSet = new LinkedHashSet<>(); linkedHashSet.addAll(goods); System.out.println(linkedHashSet); } public static class Goods implements Comparable{ private String name; private Double price; public Goods(String name, Double price) { this.name = name; this.price = price; } public String getName() { return name; } public void setName(String name) { this.name = name; } public Double getPrice() { return price; } public void setPrice(Double price) { this.price = price; } @Override public String toString() { return "Goods{" + "name='" + name + '\'' + ", price=" + price + '}'; } @Override public int compareTo(Object o) { if (!(o instanceof Goods)){ return -1; } Goods goods = (Goods) o; return this.price.compareTo(goods.getPrice()); } } } 为了看出效果，把几个商品的顺序调整了一下，输出如下： [Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone8', price=6500.0}] [Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='IphoneX', price=8500.0}] [Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone8', price=6500.0}] 这里我们按价格进行了升序排列，接下来使用外部比较器的方式进行价格的倒序排列： public class TreeSetTest { public static void main(String[] args){ List<Goods> goods = new ArrayList<>(); goods.add(new Goods("Iphone7S",4500.00)); goods.add(new Goods("Iphone4S",500.00)); goods.add(new Goods("Iphone5",800.00)); goods.add(new Goods("IphoneX",8500.00)); goods.add(new Goods("Iphone6S",2500.00)); goods.add(new Goods("Iphone8",6500.00)); goods.add(new Goods("Iphone8",6500.00)); System.out.println(goods); // 1、使用Lamada表达式 //TreeSet<Goods> treeSet = new TreeSet<>((g1,g2) -> g2.getPrice().compareTo(g1.getPrice())); // 2、使用匿名内部类 TreeSet<Goods> treeSet = new TreeSet<>(new Comparator<Goods>() { @Override public int compare(Goods o1, Goods o2) { return o2.getPrice().compareTo(o1.getPrice()); } }); treeSet.addAll(goods); System.out.println(treeSet); LinkedHashSet<Goods> linkedHashSet = new LinkedHashSet<>(); linkedHashSet.addAll(goods); System.out.println(linkedHashSet); } public static class Goods{ private String name; private Double price; public Goods(String name, Double price) { this.name = name; this.price = price; } public String getName() { return name; } public void setName(String name) { this.name = name; } public Double getPrice() { return price; } public void setPrice(Double price) { this.price = price; } @Override public String toString() { return "Goods{" + "name='" + name + '\'' + ", price=" + price + '}'; } } } 在传入外部比较器的时候，也有很多种姿势，这里还是选了匿名内部类的方式进行传入，因为这里只需要使用一次，Lamada表达式还没有做介绍，这里就先不讲了，欣赏一下就好，先领略一下它的强大。 [Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone8', price=6500.0}] [Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='Iphone4S', price=500.0}] [Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone8', price=6500.0}] 这样，就完成了倒序排列了，很简单吧。二、TreeSet源码分析先来看看TreeSet的继承关系图：跟TreeMap的继承机构差不多，NavigableSet接口中存在大量的导航方法，可以帮助更快定位想要查找的元素，AbstractSet提供Set的部分默认实现，这样只需要实现其它方法即可。可以看到，TreeSet中的方法并不是很多，除了导航方法之外，就是几个最常用的方法了，如add，addAll，remove，contains。接下来让我们一起看看这几个方法是如何实现的：先来看看内部成员和构造函数： /** * 内部默默无闻工作的Map */ private transient NavigableMap<E,Object> m; // map中共用的一个value private static final Object PRESENT = new Object(); //默认构造方法，根据其元素的自然顺序进行排序 public TreeSet() { this(new TreeMap<E,Object>()); } //构造一个包含指定 collection 元素的新 TreeSet，它按照其元素的自然顺序进行排序。 public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); } //构造一个新的空 TreeSet，它根据指定比较器进行排序。 public TreeSet(Collection<? extends E> c) { this(); addAll(c); } //构造一个与指定有序 set 具有相同映射关系和相同排序的新 TreeSet。 public TreeSet(SortedSet<E> s) { this(s.comparator()); addAll(s); } TreeSet(NavigableMap<E,Object> m) { this.m = m; } add方法，嗯，够简明扼要。 public boolean add(E e) { return m.put(e, PRESENT)==null; } addAll： public boolean addAll(Collection<? extends E> c) { // 先检测集合是否继承了SortedSet接口，内部map是否为TreeMap // 并且检测使用的比较器是否与内部Map的比较器一致 // 如果一致的话则使用TreeMap的addAllForTreeSet方法进行批量插入 // addAllForTreeSet方法可以在常量时间对有序元素进行插入 if (m.size()==0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) { SortedSet<? extends E> set = (SortedSet<? extends E>) c; TreeMap<E,Object> map = (TreeMap<E, Object>) m; Comparator<?> cc = set.comparator(); Comparator<? super E> mc = map.comparator(); if (cc==mc || (cc != null && cc.equals(mc))) { map.addAllForTreeSet(set, PRESENT); return true; } } // 如果不满足条件，则使用父类的addAll方法进行添加 return super.addAll(c); } 嗯，这里会先激进优化，不行再用笨办法一个个添加，因为如果是将大量元素插入TreeMap中相对而言还是比较耗时耗力的，每次插入一个元素都可能导致整体结构的调整，而如果插入的元素刚好是有序的，那么就可以对这个过程进行一次很不错的优化。 public boolean remove(Object o) { return m.remove(o)==PRESENT; } public boolean contains(Object o) { return m.containsKey(o); } remove和contains方法也很简单。而且还带一点粗暴到此，本篇就结束了，其实也没太多内容，因为TreeSet本身也没有太多东西。当然，了解它的内部结构目的是为了更好的使用它。在遇到问题时，每个知识点就是你手中的一张牌，能不能打好这手牌，先要看你这牌好不好，牌不好的话，再聪明也难翻盘。 . 真正重要的东西，用眼睛是看不见的。

2018-09-01

【Java入门提高篇】Day30 Java容器类详解（十二）TreeMap详解

今天来看看Map家族的另一名大将——TreeMap。前面已经介绍过Map家族的两名大将，分别是HashMap，LinkedHashMap。HashMap可以高效查找和存储元素，LinkedHashMap可以在高效查找的基础上对元素进行有序遍历，那么TreeMap又有什么特点呢？别急别急，看完这篇你就知道了。本篇主要从以下几个方面对TreeMap进行介绍： 1、TreeMap的特性以及使用栗子 2、TreeMap继承结构简介 3、TreeMap源码分析本篇预计食用10分钟，请各位食客合理分配时间。一、TreeMap的特性以及使用栗子 1. 键值不允许重复2. 默认会对键进行排序，所以键必须实现Comparable接口或者使用外部比较器3. 查找、移除、添加操作的时间复杂度为log(n)4.底层使用的数据结构是红黑树没错，又是让你欲仙欲死的红黑树，不过不要慌，跟之前介绍HashMap时的红黑树是一毛一样的，所以这一篇里，不打算再做介绍啦，如果对红黑树的内容有些遗忘了，可以动动小手，往前面翻一翻。先来看一个TreeMap的使用小栗子。 public class TreeMapTest { public static void main(String[] args){ TreeMap<String, Integer> grades = new TreeMap<>(); grades.put("Frank", 100); grades.put("Alice", 95); grades.put("Mary", 90); grades.put("Bob", 85); grades.put("Jack", 90); System.out.println(grades); System.out.println(grades.subMap("Bob", "Jack")); System.out.println(grades.subMap("Bob", true, "Jack", true)); System.out.println(grades.ceilingEntry("Bob")); System.out.println(grades.ceilingKey("Bob")); System.out.println(grades.higherEntry("Bob")); System.out.println(grades.higherKey("Bob")); System.out.println(grades.headMap("Bob")); System.out.println(grades.headMap("Bob", true)); System.out.println(grades.tailMap("Bob")); System.out.println(grades.tailMap("Bob", true)); System.out.println(grades.containsKey("Bob")); System.out.println(grades.containsValue(90)); System.out.println(grades.descendingMap()); System.out.println(grades.descendingKeySet()); } } 输出如下： {Alice=95, Bob=85, Frank=100, Jack=90, Mary=90} {Bob=85, Frank=100} {Bob=85, Frank=100, Jack=90} Bob=85 Bob Frank=100 Frank {Alice=95} {Alice=95, Bob=85} {Bob=85, Frank=100, Jack=90, Mary=90} {Bob=85, Frank=100, Jack=90, Mary=90} true true {Mary=90, Jack=90, Frank=100, Bob=85, Alice=95} [Mary, Jack, Frank, Bob, Alice] 可以看到，放入TreeMap中的元素默认按键值升序排列，这里的键值类型为String，使用String的CompareTo方法进行比较和排序。subMap返回当前Map的子Map，headMap和tailMap也是如此，二、TreeMap继承结构简介 TreeMap继承自AbstractMap，实现了NavigableMap接口，继承关系图如下：对于AbstractMap相信大家已经不陌生了，HashMap也是继承自AbstractMap，里面有对Map接口的一些默认实现。这里我们可以看到两个新的接口——SortedMap和NavigableMap。SortedMap接口继承自Map接口，从名字就能看出。SortedMap相比Map接口，憎加了排序的功能，内部的方法也不多，简单了解一下就好了 NavigableMap接口继承自SortedMap接口，主要提供一下导航方法：说了这么多没啥营养的，接下来还是讲讲真正的干货吧。三、TreeMap源码分析 JDK 1.8中的TreeMap源码有两千多行，还是比较多的。所以本文并不打算逐句分析所有的源码，而是挑选几个常用的内部类和方法进行分析。这些方法实现的功能分别是查找、遍历、插入、删除等，其他的方法小伙伴们有兴趣可以自己分析。TreeMap实现的核心部分是关于红黑树的实现，其绝大部分的方法基本都是对底层红黑树增、删、查操作的一个封装。就像前面所说，只要弄懂了红黑树原理，TreeMap 就没什么秘密了。关于红黑树的原理，可以参考前面关于HashMap红黑树的文章，本篇文章不会对此展开讨论。 TreeMap的主要数据结构是红黑树，而这红黑树结构的承载者便是内部类Entry，先来看看这个Entry类： static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; Entry<K,V> left; Entry<K,V> right; Entry<K,V> parent; boolean color = BLACK; /** * 构造函数*/ Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; } public K getKey() { return key; } public V getValue() { return value; } public V setValue(V value) { V oldValue = this.value; this.value = value; return oldValue; } public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>)o; return valEquals(key,e.getKey()) && valEquals(value,e.getValue()); } public int hashCode() { int keyHash = (key==null ? 0 : key.hashCode()); int valueHash = (value==null ? 0 : value.hashCode()); return keyHash ^ valueHash; } public String toString() { return key + "=" + value; } } 其实内部的结构也很简单，主要有key，value和三个分别指向左孩子，右孩子，父节点的引用，以及用来标识颜色的color成员变量。再来看看TreeMap中的几个重要的成员变量： /** * 外部比较器 */ private final Comparator<? super K> comparator; private transient Entry<K,V> root; /** * 键值对数量 */ private transient int size = 0; private transient int modCount = 0; private static final boolean RED = false; private static final boolean BLACK = true; /** * 键值对集合 */ private transient EntrySet entrySet; /** * 键的集合 */ private transient KeySet<K> navigableKeySet; /** * 倒序Map */ private transient NavigableMap<K,V> descendingMap; comparator用于对map中的键进行排序，root指向红黑树的根节点，size表示键值对的数量，modCount相信已经不陌生了，表示内部结构被修改的次数，RED和BLACK是两个内部常量，即红黑两种颜色，false表示红，true表示黑。entrySet是键值对的集合，navigableKeySet是键的集合，最后一个descendingMap是当前map的一个倒序map。在TreeMap中有很多内部类，可以先看图了解一下：前前后后一共18个内部类，不过不要慌，其实里面跟迭代器相关的类就占了一半多（10个），跟子Map相关的类占4个，剩下4个就是跟内部集合相关的了。接下来还是一起来看看那些最常用的方法吧： // 插入元素 public V put(K key, V value) { TreeMap.Entry<K,V> t = root; if (t == null) { // 检查类型以及key是否为null // 如果外部比较器为null，且key也为null则会抛出空指针异常 // 如果TreeMap未设置外部比较器，且传入的对象未实现Comparable接口 // 则会抛出ClassCastException异常 compare(key, key); // type (and possibly null) check // 如果根节点不存在，则用传入的键值对信息生成一个根节点 root = new TreeMap.Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; TreeMap.Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; if (cpr != null) { do { // 如果外部比较器不为空，则依次与各节点进行比较 parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) // 小于则与左孩子比较 t = t.left; else if (cmp > 0) // 大于则与右孩子比较 t = t.right; else // 找到相等的key则替换其value return t.setValue(value); // 一直循环，直到待比较的节点为null } while (t != null); } else { // 如果外部比较器为null // 如果key为null则抛出空指针 if (key == null) throw new NullPointerException(); // 如果key未实现comparable接口则会抛出异常 @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { // 跟上面逻辑类似，只是用key的compareTo方法进行比较，而不是用外部比较器的compare方法 parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } // 生成键值对 TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent); // 连接到当前map的左孩子位置或者右孩子位置 if (cmp < 0) parent.left = e; else parent.right = e; // 插入后的调整 fixAfterInsertion(e); size++; modCount++; return null; } 其实这里的逻辑跟HashMap中TreeNode的插入逻辑十分类似，也是先找到要插入的位置，然后再进行结构调整。这里的结构调整即红黑树的结构调整，在前面HashMap中已经详细介绍过了，这里就不重复介绍了，调整过程是完全一样的。 /** * 插入后的调整 */ private void fixAfterInsertion(TreeMap.Entry<K,V> x) { // 将插入的节点初始化为红色节点 x.color = RED; // 如果x不为null且x不是根节点，且x的父节点是红色，此时祖父节点一定为黑色 while (x != null && x != root && x.parent.color == RED) { // 如果x的父节点为祖父节点的左孩子 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // y指向x的叔叔节点 TreeMap.Entry<K,V> y = rightOf(parentOf(parentOf(x))); // 如果叔叔节点也是红色，则进行变色处理 if (colorOf(y) == RED) { // 父节点变成黑色 setColor(parentOf(x), BLACK); // 叔叔节点变成黑色 setColor(y, BLACK); // 祖父节点变成黑色 setColor(parentOf(parentOf(x)), RED); // 将x指向祖父节点，继续往上调整 x = parentOf(parentOf(x)); } else { // 如果叔叔节点是黑色节点 // 如果x是父节点的右孩子 if (x == rightOf(parentOf(x))) { // 将x指向其父节点 x = parentOf(x); // 左旋 rotateLeft(x); } // 将x的父节点置为黑色 setColor(parentOf(x), BLACK); // 将x的祖父节点置为红色 setColor(parentOf(parentOf(x)), RED); // 将祖父节点右旋 rotateRight(parentOf(parentOf(x))); } } else { // 这里类似操作 TreeMap.Entry<K,V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == leftOf(parentOf(x))) { x = parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } root.color = BLACK; } 说完了插入，再来看看删除操作。 // 删除节点 public V remove(Object key) { // 先找到该key对应的键值对 TreeMap.Entry<K,V> p = getEntry(key); if (p == null) // 如果未找到则返回null return null; V oldValue = p.value; // 找到后删除该键值对 deleteEntry(p); return oldValue; } final TreeMap.Entry<K,V> getEntry(Object key) { // 为了性能，卸载了比较器的版本 if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; TreeMap.Entry<K,V> p = root; // 使用compareTo方法进行查找 while (p != null) { int cmp = k.compareTo(p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } return null; } // 使用比较器的getEntry版本。从getEntry分离以获得性能。 // （对于大多数方法而言，这不值得做，这些方法较少依赖于比较器性能，但在这里是值得的。） final TreeMap.Entry<K,V> getEntryUsingComparator(Object key) { @SuppressWarnings("unchecked") K k = (K) key; Comparator<? super K> cpr = comparator; // 使用比较器进行二分查找 if (cpr != null) { TreeMap.Entry<K,V> p = root; while (p != null) { int cmp = cpr.compare(k, p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } } return null; } /** * 删除节点，并调整红黑树以保持它的平衡 */ private void deleteEntry(TreeMap.Entry<K,V> p) { modCount++; size--; // 如果p的左右孩子均不为空，则找到p的后继节点，并且将p指向该后继节点 if (p.left != null && p.right != null) { TreeMap.Entry<K,V> s = successor(p); p.key = s.key; p.value = s.value; p = s; } // p has 2 children // 修复替补节点 // 用替补节点替换待删除的节点后，需要对其原来所在位置结构进行修复 TreeMap.Entry<K,V> replacement = (p.left != null ? p.left : p.right); if (replacement != null) { replacement.parent = p.parent; if (p.parent == null) root = replacement; else if (p == p.parent.left) p.parent.left = replacement; else p.parent.right = replacement; p.left = p.right = p.parent = null; // 如果p的颜色是黑色，则进行删除后的修复 if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { root = null; } else { if (p.color == BLACK) fixAfterDeletion(p); if (p.parent != null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; } } } /** * 返回指定节点的后继节点 */ static <K,V> TreeMap.Entry<K,V> successor(TreeMap.Entry<K,V> t) { if (t == null) return null; else if (t.right != null) { TreeMap.Entry<K,V> p = t.right; // 如果右子树不为空，则找到右子树的最左节点作为后继节点 while (p.left != null) p = p.left; return p; } else { TreeMap.Entry<K,V> p = t.parent; TreeMap.Entry<K,V> ch = t; // 如果右子树为空且当前节点为其父节点的左孩子，则直接返回 // 如果为其父节点的右孩子，则一直往上找，直到找到根节点或者当前节点为其父节点的左孩子时，用其做为后继节点 while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } } /** * 进行删除后的结构修复 * @param x */ private void fixAfterDeletion(TreeMap.Entry<K,V> x) { while (x != root && colorOf(x) == BLACK) { // 如果x是父节点的左孩子 if (x == leftOf(parentOf(x))) { // sib指向x的兄弟节点 TreeMap.Entry<K,V> sib = rightOf(parentOf(x)); // 如果sib是红色，则进行变色处理 if (colorOf(sib) == RED) { // 兄弟节点改为黑色 setColor(sib, BLACK); // 父节点改为红色 setColor(parentOf(x), RED); // 父节点左旋 rotateLeft(parentOf(x)); // sib指向x的父节点的右孩子 sib = rightOf(parentOf(x)); } // 如果sib的左孩子和右孩子都是黑色，则进行变色处理 if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { // 将sib置为红色 setColor(sib, RED); // x指向其父节点 x = parentOf(x); } else { // 如果sib的右孩子是黑色而左孩子是红色，则变色右旋 if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } // 变色左旋 setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; } } else { // symmetric // 跟上面操作类似 TreeMap.Entry<K,V> sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK); } 嗯，对比一下HashMap的删除操作，核心步骤是完全一样的，所以可以对照前面的HashMap红黑树详解进行食用。到此，这一篇就很水的讲完啦= = 最近这段时间烦心事比较多，对发展方向也考虑了很多，想做的事情很多，反而让我止步不前，不过很多事情是急不来的，还是好好写写博客，多做总结分享吧。机会只留给有准备的人。真正重要的东西，用眼睛是看不见的。

2018-08-27

【Java入门提高篇】Day29 Java容器类详解（十一）LinkedHashSet详解

当当当当当当当，本来打算出去浪来着，想想还是把这个先一起写完吧，毕竟这篇的主角跟我一样是一个超级偷懒的角色——LinkedHashSet，有多偷懒？看完你就知道了。本篇将从以下几个方面对LinkedHashSet进行介绍： 1、LinkedHashSet中的特性 2、LinkedHashSet源码分析 3、LinkedHashSet应用场景本篇预计需要食用10分钟，快的话五分钟也够了，完全取决于各位看官心情。 LinkedHashSet中的特性前面已经介绍过了HashSet，本篇要介绍的LinkedHashSet正是它的儿子，作为HashSet的唯一法定继承人，可以说是继承了HashSet的全部优点——懒，并且将其发挥到了极致，这一点在之后的源码分析里可以看到。 LinkedHashSet继承了HashSet的全部特性，元素不重复，快速查找，快速插入，并且新增了一个重要特性，那就是有序，可以保持元素的插入顺序，所以可以应用在对元素顺序有要求的场景中。先来看一个小栗子： public class LinkedHashSetTest { public static void main(String[] args){ LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>(); HashSet<String> hashSet = new HashSet<>(); for (int i = 0; i < 10; i++) { linkedHashSet.add("I" + i); hashSet.add("I" + i); } System.out.println("linkedHashSet遍历："); for (String string : linkedHashSet){ System.out.print(string + " "); } System.out.println(); System.out.println("hashSet遍历："); for (String string : hashSet){ System.out.print(string + " "); } } } linkedHashSet遍历： I0 I1 I2 I3 I4 I5 I6 I7 I8 I9 hashSet遍历： I9 I0 I1 I2 I3 I4 I5 I6 I7 I8 可以看到，在HashSet中存储的元素遍历是无序的，而在LinkedHashSet中存储的元素遍历是有序的。嗯，它和HashSet就这唯一的区别了。 LinkedHashSet源码分析那么问题来了，LinkedHashSet中的元素为什么会是有序的呢？难道也跟LinkedHashMap一样用了链表把元素都拴起来了？别着急，让我们一起来看看源码。 public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { private static final long serialVersionUID = -2851667679971038690L; /** * 使用指定初始容量和装载因子构造一个空的LinkedHashSet实例 */ public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); } /** * 使用指定的初始容量和默认的装载因子构造一个空的LinkedHashSet实例 */ public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); } /** * 使用默认的初始容量和默认的装载因子构造一个空的LinkedHashSet实例 */ public LinkedHashSet() { super(16, .75f, true); } /** * 构造一个与指定集合有相同元素的空LinkedHashSet实例，使用默认的装载因子和能够容纳下指定集合所有元素的合适的容量。 */ public LinkedHashSet(Collection<? extends E> c) { super(Math.max(2*c.size(), 11), .75f, true); addAll(c); } /** * 可分割式迭代器 */ @Override public Spliterator<E> spliterator() { return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED); } } 你没看错，这应该是所有容器类中最短小精悍的了，这也就是开头为什么说这家伙懒到家的原因了。可是，LinkedHashSet中并没有覆盖add方法，只是加了几个构造函数和一个迭代器，其他全部和HashSet一毛一样，为什么它就能有序呢？？玄机就藏在这个构造函数中，这几个构造函数其实都是调用了它父类（HashSet）的一个构造函数： HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } 嗯，这个构造函数跟其他构造函数唯一的区别就在于，它创建的是一个LinkedHashMap对象，所以元素之所以有序，完全是LinkedHashMap的功劳。该构造函数是默认访问权限的，所以在HashSet中是不能直接调用的，留给子类去调用或覆盖（讲道理使用protected权限不是更合理吗）。 LinkedHashSet应用场景现在假设这样的场景，现在我有一堆商品，商品有名称和价格，但是里面有重复商品，我希望把重复的商品（名称和价格都一样的）过滤掉，只保留一个，并且希望输出后的顺序跟原来的顺序一致。嗯，这时候LinkedHashSet就派上用场了。（废话，那是你特意给主角加的戏）商品的结构是这样的： public class Commodity { private String name; private Double price; public Commodity(String name, Double price) { this.name = name; this.price = price; } public String getName() { return name; } public void setName(String name) { this.name = name; } public Double getPrice() { return price; } public void setPrice(Double price) { this.price = price; } @Override public String toString() { return "Commodity{" + "name='" + name + '\'' + ", price=" + price + '}'; } } 来用LinkedHashSet解决一下这个需求： public class CommodityTest { public static void main(String[] args){ //有7个商品，A和E、D和G信息完全一样，希望能过滤掉，只保留一个，C和F虽然名称一样，但是价格不同，希望保留 Commodity commodityA = new Commodity("Iphone6S", 6666.66); Commodity commodityB = new Commodity("Iphone7", 7777.77); Commodity commodityC = new Commodity("Iphone8", 8888.88); Commodity commodityD = new Commodity("IphoneX", 9999.99); Commodity commodityE = new Commodity("Iphone6S", 6666.66); Commodity commodityF = new Commodity("Iphone8", 6666.66); Commodity commodityG = new Commodity("IphoneX", 9999.99); LinkedHashSet<Commodity> commodities = new LinkedHashSet<>(); commodities.add(commodityA); commodities.add(commodityB); commodities.add(commodityC); commodities.add(commodityD); commodities.add(commodityE); commodities.add(commodityF); commodities.add(commodityG); for (Commodity commodity : commodities){ System.out.println(commodity); } } } 输出如下： Commodity{name='Iphone6S', price=6666.66} Commodity{name='Iphone7', price=7777.77} Commodity{name='Iphone8', price=8888.88} Commodity{name='IphoneX', price=9999.99} Commodity{name='Iphone6S', price=6666.66} Commodity{name='Iphone8', price=6666.66} Commodity{name='IphoneX', price=9999.99} 翻...翻...翻车了？虽然输出的顺序与插入的顺序是一致的最后一个IphoneX和Iphone6S并没有被去掉，怎么回事呢？说好的可以去重呢？嗯，别慌，我既然可以让车翻过来，那就有办法让它再翻回去。想要利用LinkedHashSet自动去重性质，那么我们就要先理解它是怎样去重的，其实和HashSet是一样的，往里面添加元素的时候，其实是这样的： public boolean add(E e) { return map.put(e, PRESENT)==null; } 所以当该元素在map中存在的时候，map.put方法就会返回旧值，此时add方法会返回false，在查找map中put元素的时候，会先调用hashCode方法得到该元素的hashCode值，然后查看table中是否存在该hashCode值，如果存在则调用equals方法重新确定是否存在该元素，如果存在，则更新value值，否则将新的元素添加到HashMap中，如果没有覆盖过hashcode方法，那么就会使用对象默认的hashcode，这个值跟对象成员变量的具体值就没有直接关联了，所以我们需要覆盖hashcode方法和equals方法。 public class Commodity { private String name; private Double price; public Commodity(String name, Double price) { this.name = name; this.price = price; } public String getName() { return name; } public void setName(String name) { this.name = name; } public Double getPrice() { return price; } public void setPrice(Double price) { this.price = price; } @Override public String toString() { return "Commodity{" + "name='" + name + '\'' + ", price=" + price + '}'; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Commodity commodity = (Commodity) o; return Objects.equals(name, commodity.name) && Objects.equals(price, commodity.price); } @Override public int hashCode() { return Objects.hash(name, price); } } 这里用的equals方法和hashCode方法是很通用的，在其他地方也可以使用类似的写法，现在再来重新跑一下程序看下： Commodity{name='Iphone6S', price=6666.66} Commodity{name='Iphone7', price=7777.77} Commodity{name='Iphone8', price=8888.88} Commodity{name='IphoneX', price=9999.99} Commodity{name='Iphone8', price=6666.66} 好的，现在已经达到我们想要的效果了。任务完成，午饭加个蛋。真正重要的东西，用眼睛是看不见的。

2018-08-10

【Java入门提高篇】Day28 Java容器类详解（十）LinkedHashMap详解

今天来介绍一下容器类中的另一个哈希表———》LinkedHashMap。这是HashMap的关门弟子，直接继承了HashMap的衣钵，所以拥有HashMap的全部特性，并青出于蓝而胜于蓝，有着一些HashMap没有的特性。接下来就一起来看看这个关门弟子到底有多大能耐。本文将从以下几点对LinkedHashMap进行介绍： 1、LinkedHashMap简介与简单使用 2、LinkedHashMap的结构以及与HashMap的对比 3、LinkedHashMap的插入和删除 4、LinkedHashMap的源码分析 5、基于LinkedHashMap实现LRU缓存 6、总结本文预计需食用二十分钟，请各位食客合理分配时间。（别慌别慌，虽然LinkedHashMap也是哈希表，但跟HashMap比起来，内容还是要少很多的，因为很多内容在HashMap中已经讲解过了，2333） LinkedHashMap简介与简单使用先来看看LinkedHashMap的继承结构： LinkedHashMap属于Map大家族的一员，直接继承自HashMap，所以有着HashMap的全部特性，如高效查找元素，同时，LinkedHashMap保持了内部元素的顺序，有两种顺序模式，保持元素插入顺序或者访问顺序，因此适用于需保持元素顺序的场景。另外，由于LinkedHashMap有保持元素访问顺序的模式，所以也常被用作LRU缓存（Least-Recently-Used Cache，即最近最少使用缓存策略，后面会有介绍）。 LinkedHashMap的结构以及与HashMap的对比 LinkedHashMap中的结构相比HashMap更加复杂，首先它有着HashMap相同的结构，元素用数组+链表的形式存储，除此之外，所有元素还使用了双链表进行连接，相当于HashMap和LinkedList两种结构的结合体，也正是因为元素之间使用了链表连接，所有才能让其中的元素可以保持某种顺序。但也增加了维护这个链表的开销，每次进行增加和删除元素时，除了需要调整HashMap的结构，还需要调整链表结构，不过链表调整的开销并不大，除了数据量特别大的场景，一般情况下可以小到忽略不计。另一方面，由于所有元素使用链表相连，所以遍历的效率略高于HashMap，因为HashMap遍历时，需要每个桶中先遍历到链表尾部，然后再遍历到下一个桶，当元素不多而空桶数量很多时，就会有很多次的无效访问，所以理论上来说，LinkedHashMap的遍历效率是要比HashMap高的。说了这么多，好像LinkedHashMap处处要比HashMap好，为啥不都用LinkedHashMap呢？这个问题就跟LinkedList和ArrayList对比一样，两者都有其适用的场景，并没有绝对的孰优孰劣之分，所以还是要具体情况具体分析。好了，先来看看LinkedHashMap中的节点：谜一样的继承关系，看完这个图，你也许会想，贵圈真乱，父类中的TreeNode继承自子类中的Entry，子类中的Entry又继承自父类中的Node。先别慌，这样做自然有它的道理，先来回顾一下Node的结构，Node是HashMap中的普通节点类，内部结构是这样的： static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; /** * 指向下一个节点的引用 */ Node<K,V> next; ......省略部分代码 } 最上面的那个Entry是Map接口中的一个内部接口，只是规定了Entry该有的方法，并没有成员变量。在LinkedHashMap中，Entry内部类是这样的： static class Entry<K,V> extends Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } 增加了before和after引用，这样便可以和其他Entry一起组成一个双链表，节点不仅存储了键值对信息，还可以使用next，before，after来链接前后节点，next引用仅用于HashMap结构中链接同一个桶中的后一个元素，而before和after引用则是用来链接LinkedHashMap中的所有元素，将其链接成一个双链表的形式。接下来看一个跟HashMap结构的对比图就很清晰了：那再来回到之前的问题，为什么TreeNode要继承自LinkedHashMap中的Entry而不是直接继承自Node呢，毕竟在HashMap中并不需要使用到这样的链表性质，增加after和before两个引用只会浪费空间，首先，自然是为了复用代码，如果TreeNode直接继承自Node，则失去了链表的特性，LinkedHashMap继承HashMap后，则需要再使用另一个内部类来继承TreeNode来使得其具有链表特性，并且相关方法均需要重写，大大的增加了工作量，并且代码的可维护性会下降很多，另外，HashMap只会在桶中元素达到一定数量的时候才会将节点转换TreeNode，在哈希表散列良好的情况下，TreeNode是很少被使用到的，所以这一点点的空间浪费是值得的。 LinkedHashMap可以看成由两部分的组成，一部分与HashMap结构完全一致，另一部分则是一个双链表，由于LinkedHashMap是直接继承自HashMap的，所以哈希表的结构维护就在HashMap中的代码里进行，在LinkedHashMap中仅进行双链表的维护。这样也能很好的划分职能，使得代码结构也更加清晰。下面来通过代码感受一下两者的区别： public class Test { public static void main(String[] args){ Map<String,Integer> linkedHashMap = new LinkedHashMap<>(); Map<String,Integer> hashMap = new HashMap<>(); for (int i = 0; i < 10; i++) { linkedHashMap.put("I" + i, i * i); hashMap.put("I" + i, i * i); } System.out.println("hashMap 遍历："); foreach(hashMap); System.out.println("linkedHashMap遍历："); foreach(linkedHashMap); } private static void foreach(Map map){ for (Object key : map.keySet()){ System.out.println("key:" + key.toString() + " value:" + map.get(key).toString()); } } } hashMap 遍历： key:I9 value:81 key:I0 value:0 key:I1 value:1 key:I2 value:4 key:I3 value:9 key:I4 value:16 key:I5 value:25 key:I6 value:36 key:I7 value:49 key:I8 value:64 linkedHashMap遍历： key:I0 value:0 key:I1 value:1 key:I2 value:4 key:I3 value:9 key:I4 value:16 key:I5 value:25 key:I6 value:36 key:I7 value:49 key:I8 value:64 key:I9 value:81 两个哈希表插入同样的元素，使用同样的方式进行遍历，HashMap得到的是无序的结果，而LinkedHashMap得到的是跟插入顺序一致的结果。而产生这样区别的根源就在于LinkedHashMap中的那个双链表。接下来我们通过LinkedHashMap的插入删除过程来了解双链表的维护过程。 LinkedHashMap的插入和删除如果你没有看过代码，你也许会想，LinkedHashMap应该是通过重写put和remove方法来实现的，但事实上LinkedHashMap并没有覆盖插入和删除方法，这一点可以通过观察LinkedHashMap代码结构发现：那么回到前面的栗子，既然没有覆盖put方法，调用LinkedHashMap中的put方法为什么会跟HashMap中的put方法得到的结果不一样呢？让我们再来看看put方法的实现： public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);//newNode方法在LinkedHashMap中被覆盖 else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e);//关键方法A return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict);//关键方法B return null; } put方法调用的是putVal方法，在putVal方法的最后几行里，有这么两个方法值得注意， afterNodeAccess(e); afterNodeInsertion(evict); 分别是在元素被访问之后和元素被插入之后调用，而这两个回调方法，在HashMap中并没有具体实现，只有一个空壳，留个LinkedHashMap来覆盖。 // Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node<K,V> p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K,V> p) { } //在节点被移除后进行双链表的调整，移除调整其实很简单，就是把要移除的节点前一个节点的after引用指向后一个节点，把后一个节点的before引用指向前一个节点 void afterNodeRemoval(Node<K,V> e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; } //在节点被插入后进行双链表的调整，插入节点时会判断是否需要移除链表头节点，默认实现是不移除的，可以通过继承LinkedHashMap并覆盖removeEldestEntry方法来改变该特性 void afterNodeInsertion(boolean evict) { LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } //在节点被访问之后进行双链表的调整（仅仅在accessOrder为true时进行，把当前访问的元素移动到链表尾部） void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } } 再来看看在LinkedHashMap中被覆盖的newNode方法： Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); //新建节点，然后链接到双链表的尾部 linkNodeLast(p); return p; } private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } } 现在再来梳理一下逻辑，插入节点的时候，会调用覆盖过的newNode方法，将插入的元素链接的链表尾部，删除节点的时候，将该节点的前后节点相连即可，当节点被访问时，可以将其放到链表尾部（该特性后面会讲解）。如果对于双链表的插入删除还是不太了解，可以回头看看前面关于LinkedList的说明，里面有关于双链表结构调整的详细讲解。（理直气壮的偷懒） LinkedHashMap的源码分析先来看看它的几个内部类，节点类Entry在前面已经介绍过了，剩下的几个类有四个是迭代器类，三个是键、值以及键值对的集合类。先看看迭代器类，在LinkedHashMap中，也在内部实现了自己的迭代器，内部迭代器都继承自LinkedHashIterator类，该类代码如下： abstract class LinkedHashIterator { LinkedHashMap.Entry<K,V> next; LinkedHashMap.Entry<K,V> current; int expectedModCount; LinkedHashIterator() { next = head; expectedModCount = modCount; current = null; } public final boolean hasNext() { return next != null; } final LinkedHashMap.Entry<K,V> nextNode() { LinkedHashMap.Entry<K,V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); current = e; next = e.after; return e; } public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } } 这是一个抽象类，实现了迭代器的主要方法，hashNext，remove，nextNode方法，相当于一个类模板，其他迭代器类只需要继承该类然后添加一个next方法即可。 final class LinkedKeyIterator extends LinkedHashIterator implements Iterator<K> { public final K next() { return nextNode().getKey(); } } final class LinkedValueIterator extends LinkedHashIterator implements Iterator<V> { public final V next() { return nextNode().value; } } final class LinkedEntryIterator extends LinkedHashIterator implements Iterator<Map.Entry<K,V>> { public final Map.Entry<K,V> next() { return nextNode(); } } 怎么样，是不是贼简单。剩下三个集合视图类结构基本一致，跟HashMap中的对应集合视图其实基本是一毛一样的，不信可以对比一下： // HashMap中的EntrySet final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator<Map.Entry<K,V>> iterator() { return new EntryIterator(); } public final boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Node<K,V> candidate = getNode(hash(key), key); return candidate != null && candidate.equals(e); } public final boolean remove(Object o) { if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Object value = e.getValue(); return removeNode(hash(key), key, value, true, true) != null; } return false; } public final Spliterator<Map.Entry<K,V>> spliterator() { return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer<? super Map.Entry<K,V>> action) { Node<K,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) action.accept(e); } if (modCount != mc) throw new ConcurrentModificationException(); } } } //LinkedHashMap中的EntrySet final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> { public final int size() { return size; } public final void clear() { LinkedHashMap.this.clear(); } public final Iterator<Map.Entry<K,V>> iterator() { return new LinkedEntryIterator(); } public final boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Node<K,V> candidate = getNode(hash(key), key); return candidate != null && candidate.equals(e); } public final boolean remove(Object o) { if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Object value = e.getValue(); return removeNode(hash(key), key, value, true, true) != null; } return false; } public final Spliterator<Map.Entry<K,V>> spliterator() { return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED | Spliterator.DISTINCT); } public final void forEach(Consumer<? super Map.Entry<K,V>> action) { if (action == null) throw new NullPointerException(); int mc = modCount; for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) action.accept(e); if (modCount != mc) throw new ConcurrentModificationException(); } } 仅仅是在迭代器方法中返回各自的内部迭代器实例而已。其余逻辑基本一致。 LinkedKeySet和LinkedValues也很简单： final class LinkedKeySet extends AbstractSet<K> { public final int size() { return size; } public final void clear() { LinkedHashMap.this.clear(); } public final Iterator<K> iterator() { return new LinkedKeyIterator(); } public final boolean contains(Object o) { return containsKey(o); } public final boolean remove(Object key) { return removeNode(hash(key), key, null, false, true) != null; } public final Spliterator<K> spliterator() { return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED | Spliterator.DISTINCT); } public final void forEach(Consumer<? super K> action) { if (action == null) throw new NullPointerException(); int mc = modCount; for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) action.accept(e.key); if (modCount != mc) throw new ConcurrentModificationException(); } } final class LinkedValues extends AbstractCollection<V> { public final int size() { return size; } public final void clear() { LinkedHashMap.this.clear(); } public final Iterator<V> iterator() { return new LinkedValueIterator(); } public final boolean contains(Object o) { return containsValue(o); } public final Spliterator<V> spliterator() { return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED); } public final void forEach(Consumer<? super V> action) { if (action == null) throw new NullPointerException(); int mc = modCount; for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) action.accept(e.value); if (modCount != mc) throw new ConcurrentModificationException(); } } 看完内部类，我们再来看看它的几个构造函数： /** * 构造一个空的保持插入顺序的LinkedHashMap实例，使用指定的初始容量和装载因子 */ public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } /** * 构造一个空的保持插入顺序的LinkedHashMap实例，使用指定的初始容量和默认的装载因子（0.75） */ public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } /** * 构造一个空的保持插入顺序的LinkedHashMap实例，使用默认的初始容量（16）和默认的装载因子（0.75） */ public LinkedHashMap() { super(); accessOrder = false; } /** * 使用指定Map的所有映射构造一个保持插入顺序的LinkedHashMap实例，使用默认的装载因子和可以容纳指定map中所有映射的合适的容量。 */ public LinkedHashMap(Map<? extends K, ? extends V> m) { super(); accessOrder = false; putMapEntries(m, false); } /** * 使用指定初始容量，指定装载因子和指定顺序模式来创建一个空的LinkedHashMap实例。 */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } 跟HashMap中的构造函数也几无二致，除了一点，那就是多了一个特殊的成员变量，accessOrder，这个变量是干嘛的呢，其实是一个表示LinkedHashMap中元素存储顺序的标志，前面也提到过，LinkedHashMap中元素其实是可以按两种顺序进行存储的，一种是元素的插入顺序，另一种便是元素的访问顺序，如果accessOrder为true，则使用访问顺序，即最近访问的元素位于链表最后，如果accessOrder为false，则使用插入顺序，即最后被插入的元素位于链表最后。默认是使用插入顺序，当然，也可以通过最后一个构造函数来使用指定顺序。如果你足够细心的话，还会发现有这么一个方法： void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; // 根据条件判断是否移除最近最少被访问的节点 if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } // 移除最近最少被访问条件之一，通过覆盖此方法可实现不同策略的缓存 protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; } removeEldestEntry方法在默认情况下是返回false的，所以在插入节点的时候，默认是不会删除之前节点的，但我们可以通过继承来改变这一特性。基于LinkedHashMap实现LRU缓存首先还是对LRU缓存做一个相对简单的介绍： LRU（Leastrecentlyused，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。其实是一个缓存淘汰策略，当缓存数量达到一个阈值时，优先淘汰最近最少被访问的数据。当我们使用LinkedHashMap来实现LRU缓存时，可以通过覆写removeEldestEntry方法可以实现自定义策略的 LRU 缓存。比如我们可以根据节点数量判断是否移除最近最少被访问的节点，或者根据节点的存活时间判断是否移除该节点等。下面栗子所实现的缓存是基于判断节点数量是否超限的策略。在构造缓存对象时，传入最大节点数。当插入的节点数超过最大节点数时，移除最近最少被访问的节点。实现代码如下： public class LRUCache<K, V> extends LinkedHashMap<K, V> { private static final int MAX_CACHE_SIZE = 100; private int limit; public LRUCache() { this(MAX_CACHE_SIZE); } public LRUCache(int cacheSize) { super(cacheSize, 0.75f, true); this.limit = cacheSize; } public V save(K key, V val) { return put(key, val); } public V getOne(K key) { return get(key); } public boolean exists(K key) { return containsKey(key); } /** * 判断节点数是否超限 * @param eldest * @return 超限返回 true，否则返回 false */ @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > limit; } @Override public String toString() { StringBuilder sb = new StringBuilder(); for (Map.Entry<K, V> entry : entrySet()) { sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue())); } return sb.toString(); } public static void main(String[] args){ LRUCache<String, Integer> cache = new LRUCache<>(3); for (int i = 0; i < 10; i++) { cache.save("I" + i, i * i); } System.out.println("插入10个键值对后，缓存内容为："); System.out.println(cache + "\n"); System.out.println("访问键值为I8的节点后，缓存内容为："); cache.getOne("I8"); System.out.println(cache + "\n"); System.out.println("插入键值为I1的键值对后，缓存内容："); cache.save("I1", 1); System.out.println(cache); } } 输出如下：插入10个键值对后，缓存内容为： I7:49 I8:64 I9:81 访问键值为I8的节点后，缓存内容为： I7:49 I9:81 I8:64 插入键值为I1的键值对后，缓存内容： I9:81 I8:64 I1:1 在上述代码中，缓存大小设置为3，当在缓存中插入10个键值对后，只有最后3个被保存下来了，其他的都被移除了。然后通过访问键值为I8的节点，使得该节点被移到双向链表的最后位置。当我们再次插入一个键值对时，键值为I7的节点就会被淘汰掉。总结本文从 LinkedHashMap 哈希表+链表维护的角度对 LinkedHashMap 的源码进行了分析，并在文章的结尾基于 LinkedHashMap 实现了一个简单的 Cache。在日常开发中，LinkedHashMap 的使用频率虽不及 HashMap，但它也是不可或缺的重要实现。在 Java 集合框架中，HashMap、LinkedHashMap 和 TreeMap 三个映射类基于不同的数据结构，并实现了不同的功能。HashMap 底层基于拉链式的散列结构，并在 JDK 1.8 中引入红黑树优化过长链表的问题。基于这样结构，HashMap 可提供高效的增删改查操作。LinkedHashMap 在其之上，通过维护一条双向链表，实现了散列数据结构的有序遍历。TreeMap 底层基于红黑树实现，利用红黑树的性质，实现了键值对排序功能。TreeMap相关内容将会在后面的文章里进行讲解。最后是又臭又长的源码注解，大家可以选择自己感兴趣的部分进行阅读，最好在IDE中进行阅读，这样可以很方便的进行跳转。 import java.util.*; import java.util.function.Consumer; import java.util.function.BiConsumer; import java.util.function.BiFunction; import java.io.IOException; /** * Map 接口的哈希表和链表实现，具有可预测的迭代顺序。此实现与 HashMap 的不同之处在于它维护了一个贯穿其所有条目的双向链表。 * 此链接列表定义迭代排序，通常是键插入映射的顺序（插入顺序）。请注意，如果将键重新插入到Map中，则插入顺序不会受到影响。 * （如果在m.containsKey时调用 m.put（k，v），则将键k 重新插入到map m 中,会在调用之前立即返回true 。） * * 这种实现使客户免于{@link HashMap}（以及{@link Hashtable}）提供的不确定的，通常是混乱的排序，并且不会导致类似{@link TreeMap}相关的成本增加。 * 无论原始Map的实现如何，它都可用于生成与原始Map具有相同顺序的Map副本： * * void foo(Map m) { * Map copy = new LinkedHashMap(m); * ... * } * * 如果模块在输入上获取map，复制它，然后返回其顺序由副本确定的结果，则此技术特别有用。（客户通常会欣赏按照提交的顺序返回的内容。） * * 提供了一个特殊的{@link #LinkedHashMap（int，float，boolean）构造函数}来创建一个链接的哈希映射，其迭代顺序是其条目最后一次访问的顺序， * 从最近最少访问到最近最多访问（按存取顺序）。这种地图非常适合构建LRU缓存。调用{@code put}，{@code putIfAbsent}，{@code get}， * {@code getOrDefault}，{@code compute}，{@code computeIfAbsent}，{@code computeIfPresent}或{@code merge}方法 * 导致访问相应的条目（假设它在调用完成后存在）。 {@code replace}方法仅在替换值时才会访问该条目。 {@code putAll}方法为指定映射中的 * 每个映射生成一个条目访问，按照指定映射的条目集迭代器提供键 - 值映射的顺序。没有其他方法可以生成条目访问。 * 特别是，对集合视图的操作不会影响支持映射的迭代顺序。 * * TODO LRU缓存 * * 可以重写{@link #removeEldestEntry（Map.Entry）}方法，以强制在将新映射添加到Map中时自动删除过时映射的策略。 * * 此类提供所有可选的Map操作，并允许null元素。与HashMap一样，假设哈希函数在桶之间正确地分散元素，它将为基本操作（添加，包含和删除）提供了恒定时间 * 性能，由于维护链表的额外费用，性能可能略低于HashMap的性能，但有一个例外： * 无论其容量如何，对LinkedHashMap的集合视图进行迭代需要与映射大小成比例的时间。而对HashMap的迭代可能更昂贵，需要与其容量成比例的时间。 * * 链接的哈希映射有两个影响其性能的参数：初始容量和加载因子。它们的定义与 HashMap 完全相同。 * 但请注意，对于此类，选择过高的初始容量值的惩罚不如 HashMap ，因为此类的迭代次数不受容量影响。 * * 请注意，此实现未同步。如果多个线程同时访问链接的哈希映射，并且至少有一个线程在结构上修改了映射，则<em>必须</ em>外部同步。 * 这通常通过在自然封装地图的某个对象上进行同步来实现。如果不存在此类对象， * 则应使用{@link Collections＃synchronizedMap Collections.synchronizedMap}方法“包装”映射。这最好在创建时完成， * 以防止意外地不同步访问地图： * Map m = Collections.synchronizedMap（new LinkedHashMap（...））; * * 结构修改是指任何添加或删除一个或多个映射的操作，或者在访问顺序链接的哈希映射的情况下，影响迭代顺序。 * 在插入有序链接散列映射中，仅更改与已包含在映射中的键相关联的值不是结构修改。在访问顺序链接哈希映射中，仅使用 get 查询地图是一种结构修改。 * * 由该类的所有集合视图方法<tt> iterator </ tt>方法返回的迭代器是 “fail-fast” 的： * 如果map在创建迭代器之后的任何时候进行结构修改，（除了通过迭代器自己的<tt> remove </ tt>方法之外）， * 迭代器将抛出{@link ConcurrentModificationException}。因此，在并发修改的情况下，迭代器快速而干净地失败， * 而不是在未来的未确定时间冒任意，非确定性行为的风险。 * * 请注意，迭代器的快速失败行为无法得到保证，因为一般来说，在存在非同步并发修改的情况下，不可能做出任何硬性保证。 * 失败快速的迭代器会尽最大努力抛出<tt> ConcurrentModificationException </ tt>。因此，编写依赖于此异常的程序以确保其正确性是错误的： * 迭代器的故障快速行为应仅用于检测错误。 * * 分裂器返回的分裂器所有此类的集合视图方法返回的集合的方法是后期绑定的，失败快速的和附加报告的{@link Spliterator #OrderED}。 * */ public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> { /** * 实现说明。此类的先前版本的内部结构略有不同。因为超类HashMap现在为其某些节点使用树节点，所以类Entry现在被视为中间节点类， * 也可以转换为树形式。这个类的名称Entry在其当前上下文中以多种方式混淆，但无法更改。否则，即使它未被导出到此包之外， * 已知一些现有的源代码依赖于对removeEldestEntry的调用中的符号解析角案例规则，该删除由于模糊使用而抑制了编译错误。 * 因此，我们保留名称以保留未修改的可编译性。节点类的更改还需要使用两个字段（头部，尾部）而不是指向标头节点的指针来维护列表之前/之后的双向链接。 * 此类以前还在访问，插入和删除时使用了不同类型的回调方法。 */ /** * 普通 LinkedHashMap 条目的HashMap.Node子类. */ static class Entry<K,V> extends Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } private static final long serialVersionUID = 3801124242820219131L; /** * 第一个条目 */ transient Entry<K,V> head; /** * 最后一个条目 */ transient Entry<K,V> tail; /** * 迭代顺序，true代表使用访问顺序进行迭代，false代表使用插入顺序进行迭代 */ final boolean accessOrder; // 内部工具方法 // 链接到链表尾部 private void linkNodeLast(Entry<K,V> p) { Entry<K,V> last = tail; tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } } // 用dst条目代替src条目 private void transferLinks(Entry<K,V> src, Entry<K,V> dst) { Entry<K,V> b = dst.before = src.before; Entry<K,V> a = dst.after = src.after; if (b == null) head = dst; else b.after = dst; if (a == null) tail = dst; else a.before = dst; } // 重载 HashMap 中的方法 void reinitialize() { super.reinitialize(); head = tail = null; } // 新建条目并链接到链表尾部 Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { Entry<K,V> p = new Entry<K,V>(hash, key, value, e); linkNodeLast(p); return p; } // 代替节点 Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { Entry<K,V> q = (Entry<K,V>)p; Entry<K,V> t = new Entry<K,V>(q.hash, q.key, q.value, next); transferLinks(q, t); return t; } TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next); linkNodeLast(p); return p; } TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { Entry<K,V> q = (Entry<K,V>)p; TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next); transferLinks(q, t); return t; } // 节点移除之后，将其从双链表中拆分出来 void afterNodeRemoval(Node<K,V> e) { // unlink Entry<K,V> p = (Entry<K,V>)e, b = p.before, a = p.after; p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; } // 节点插入之后判断是否需要将最早的元素进行删除 void afterNodeInsertion(boolean evict) { // possibly remove eldest Entry<K,V> first; // 要同时满足三个条件才能在插入元素后对最早插入条目进行删除 if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } // 在节点被访问之后，判断是否需要将被访问过的节点移动到双链表的最末尾 void afterNodeAccess(Node<K,V> e) { // move node to last Entry<K,V> last; // 当accessOrder成员变量为true并且该访问元素不是最后一个元素时，将其移动到双链表的末尾 if (accessOrder && (last = tail) != e) { Entry<K,V> p = (Entry<K,V>)e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } } // 重写hashmap的internalWriteEntries方法，进行输出流的写入 void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException { for (Entry<K,V> e = head; e != null; e = e.after) { s.writeObject(e.key); s.writeObject(e.value); } } /** * 构造一个空的保持插入顺序的LinkedHashMap实例，使用指定的初始容量和装载因子 */ public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } /** * 构造一个空的保持插入顺序的LinkedHashMap实例，使用指定的初始容量和默认的装载因子（0.75） */ public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } /** * 构造一个空的保持插入顺序的LinkedHashMap实例，使用默认的初始容量（16）和默认的装载因子（0.75） */ public LinkedHashMap() { super(); accessOrder = false; } /** * 使用指定Map的所有映射构造一个保持插入顺序的LinkedHashMap实例，使用默认的装载因子和可以容纳指定map中所有映射的合适的容量。 */ public LinkedHashMap(Map<? extends K, ? extends V> m) { super(); accessOrder = false; putMapEntries(m, false); } /** * 使用指定初始容量，指定装载因子和指定顺序模式来创建一个空的LinkedHashMap实例。 */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } /** * Returns <tt>true</tt> if this map maps one or more keys to the * specified value. * * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * specified value */ public boolean containsValue(Object value) { // TODO 与hashmap的遍历方式进行比较 // LinkedHashMap中遍历元素时都是使用链表的方式进行遍历 for (Entry<K,V> e = head; e != null; e = e.after) { V v = e.value; if (v == value || (value != null && value.equals(v))) return true; } return false; } /** * 获取指定key对应的value，不存在则返回null * 返回null时有两种可能，一种是该key没有对应的映射，另一种是该key对应的value是null，可以使用containsKey方法对这两种情况进行区分 */ public V get(Object key) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value; } /** * 获取指定key对应的value，如果不存在则返回默认值 */ public V getOrDefault(Object key, V defaultValue) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return defaultValue; if (accessOrder) afterNodeAccess(e); return e.value; } /** * 清除元素 */ public void clear() { super.clear(); head = tail = null; } /** * 如果此map应删除其最旧的条目，则返回true 。在将新条目插入Map后，put 和 putAll 将调用此方法。 * 它为实现者提供了在每次添加新条目时删除最旧条目的机会。如果映射表示高速缓存，则此选项非常有用：它允许映射通过删除过时条目来减少内存消耗。 * * 示例：此覆盖实现将允许map增长到100个条目， * 然后在每次添加新条目时删除最旧的条目，保持100个条目的稳定状态。 * * private static final int MAX_ENTRIES = 100; * protected boolean removeEldestEntry（Map.Entry eldest）{ * return size（）; MAX_ENTRIES; * } * * 此方法通常不会以任何方式修改地图，而是允许地图按其返回值的指示修改自身。此方法直接修改map是允许的，但如果它这样做， * 它必须返回false（表示map不应该尝试任何进一步的修改）。在此方法中修改地图后返回 true 的效果未指定。此实现仅返回 false * （因此此映射的行为类似于普通映射 - 永远不会删除最旧的元素）。 * * @param eldest map中最近插入的条目，或者如果这是访问顺序地图，则是最近访问的条目。这是将被删除的条目，此方法返回 true 。 * 如果在 put 或 putAll 调用之前映射为空，从而导致此调用，则这将是刚刚插入的条目;换句话说，如果map包含单个条目， * 则最老的条目也是最新的。 * * @return true 表示应从map中删除最年长的条目; false 表示应该保留。 */ protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; } /** * 返回包含该map所有key的{@link Set}视图。该集合由map支持，因此对map的更改将反映在集中，反之亦然。如果在对集合进行迭代时修改了映射 * （除了通过迭代器自己的remove 操作），迭代的结果是未定义的。该集支持元素删除，它通过 Iterator.remove ，Set.remove ， removeAll * ，从地map中删除相应的映射。 retainAll 和 clear 操作。它不支持 add 或 addAll 操作。它的{@link Spliterator}通常提供更快的顺序性能， * 但并行性能比{@code HashMap}差得多。 */ public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new LinkedKeySet(); keySet = ks; } return ks; } final class LinkedKeySet extends AbstractSet<K> { public final int size() { return size; } public final void clear() { this.clear(); } public final Iterator<K> iterator() { return new LinkedKeyIterator(); } public final boolean contains(Object o) { return containsKey(o); } public final boolean remove(Object key) { return removeNode(hash(key), key, null, false, true) != null; } public final Spliterator<K> spliterator() { return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED | Spliterator.DISTINCT); } public final void forEach(Consumer<? super K> action) { if (action == null) throw new NullPointerException(); int mc = modCount; for (Entry<K,V> e = head; e != null; e = e.after) action.accept(e.key); if (modCount != mc) throw new ConcurrentModificationException(); } } public Collection<V> values() { Collection<V> vs = values; if (vs == null) { vs = new LinkedValues(); values = vs; } return vs; } final class LinkedValues extends AbstractCollection<V> { public final int size() { return size; } public final void clear() { this.clear(); } public final Iterator<V> iterator() { return new LinkedValueIterator(); } public final boolean contains(Object o) { return containsValue(o); } public final Spliterator<V> spliterator() { return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED); } public final void forEach(Consumer<? super V> action) { if (action == null) throw new NullPointerException(); int mc = modCount; for (Entry<K,V> e = head; e != null; e = e.after) action.accept(e.value); if (modCount != mc) throw new ConcurrentModificationException(); } } /** * 返回包含该map中所有映射的Set视图，该set由map支持，因此对map的更改将反映在set中，反之亦然。如果在对集合进行迭代时修改了映射 * （除非通过迭代器自己的 remove 操作，或者对迭代器返回的映射条目执行 setValue 操作））迭代的结果是未定义的。该集支持元素删除， * 它通过 Iterator.remove Set.remove ， removeAll ，从地图中删除相应的映射。 retainAll 和 clear 操作。它不支持 add 或 * addAll 操作。它的{@link Spliterator}通常提供更快的顺序性能，但并行性能比{@code HashMap}差得多。 */ public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es; } final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> { public final int size() { return size; } public final void clear() { this.clear(); } public final Iterator<Map.Entry<K,V>> iterator() { return new LinkedEntryIterator(); } public final boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Node<K,V> candidate = getNode(hash(key), key); return candidate != null && candidate.equals(e); } public final boolean remove(Object o) { if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Object value = e.getValue(); return removeNode(hash(key), key, value, true, true) != null; } return false; } public final Spliterator<Map.Entry<K,V>> spliterator() { return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED | Spliterator.DISTINCT); } public final void forEach(Consumer<? super Map.Entry<K,V>> action) { if (action == null) throw new NullPointerException(); int mc = modCount; for (Entry<K,V> e = head; e != null; e = e.after) action.accept(e); if (modCount != mc) throw new ConcurrentModificationException(); } } // Map overrides public void forEach(BiConsumer<? super K, ? super V> action) { if (action == null) throw new NullPointerException(); int mc = modCount; for (Entry<K,V> e = head; e != null; e = e.after) action.accept(e.key, e.value); if (modCount != mc) throw new ConcurrentModificationException(); } public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { if (function == null) throw new NullPointerException(); int mc = modCount; for (Entry<K,V> e = head; e != null; e = e.after) e.value = function.apply(e.key, e.value); if (modCount != mc) throw new ConcurrentModificationException(); } // 迭代器 abstract class LinkedHashIterator { Entry<K,V> next; Entry<K,V> current; int expectedModCount; LinkedHashIterator() { next = head; expectedModCount = modCount; current = null; } public final boolean hasNext() { return next != null; } final Entry<K,V> nextNode() { Entry<K,V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); current = e; next = e.after; return e; } public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } } final class LinkedKeyIterator extends LinkedHashIterator implements Iterator<K> { public final K next() { return nextNode().getKey(); } } final class LinkedValueIterator extends LinkedHashIterator implements Iterator<V> { public final V next() { return nextNode().value; } } final class LinkedEntryIterator extends LinkedHashIterator implements Iterator<Map.Entry<K,V>> { public final Map.Entry<K,V> next() { return nextNode(); } } } 至此，本篇就算完结啦，一周一篇的小目标也算是完成了，周末要去浪浪浪了，哈哈哈哈。后续还会继续更新，欢迎继续关注！真正重要的东西，用眼睛是看不见的。

2018-08-09

【Java入门提高篇】Day27 Java容器类详解（九）LinkedList详解

这次介绍一下List接口的另一个践行者——LinkedList，这是一位集诸多技能于一身的List接口践行者，可谓十八般武艺，样样精通，栈、队列、双端队列、链表、双向链表都可以用它来模拟，话不多说，赶紧一起来看看吧。本篇将从以下几个方面对LinkedList进行解析： 1.LinkedList整体结构。 2.LinkedList基本操作使用栗子。 3.LinkedList与ArrayList的对比分析。 4.LinkedList整体源码分析。 LinkedList整体结构先来看看LinkedList中的结构，LinkedList跟ArrayList不一样，ArrayList中是动态维护了一个数组，所有的操作都是在该数据上进行操作，而LinkedList中其实是一个个的Node节点，每个Node节点首尾相连。如果你还记得前几篇的内容的话，就应该会想起HashMap中其实也是有Node节点的，但两者还是有比较多不一样的地方，先来看看LinkedList中的Node吧。 private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } 嗯，其实很简单，里面只有三个成员变量，item用来存储具体的元素信息，next指向下一个Node节点，prev指向上一个Node节点，node节点之间通过next和prev相连接，组成了一个双向链表的形式。嗯，看图说话应该就很好懂了，LinkedList正是由Node这样首尾相连组成了铁索连环的格局。而HashMap中的Node节点其实是一个单链表的节点，只有指向后一个节点的引用（next），并没有指向前一个节点的引用，回顾一下HashMap的Node节点代码便能发现这一点。 static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } ......省略部分代码 } LinkedList基本操作使用栗子接下来看看LinkedList中的一些基础操作，以下是一个小栗子： ublic class LinkedListTest { public static void main(String[] args){ // 定义要插入集合的字符串对象 String a = "A", b = "B", c = "C", d = "D", e = "E", f = "F", g = "G"; // 创建List集合 LinkedList<String> list = new LinkedList<>(); // add操作添加元素 list.add(a); list.add(b); list.add(c); list.add(f); // 迭代器遍历 System.out.println("修改前："); traverseListByIterator(list); // set操作 // 将索引位置为1的对象修改为对象g list.set(1, g); // 将索引位置为2的对象修改为对象d list.set(2, e); // 新建迭代器进行遍历（注意：迭代器是一次性使用的，遍历到列表尾部之后，无法重置，再次遍历时需要新建迭代器） System.out.println(); System.out.println("set修改后的集合中的元素是："); traverseListByIterator(list); // 创建ArrayList List<String> strings = new ArrayList<>(); strings.add(d); strings.add(a); strings.add(f); // addAll添加所有元素 list.addAll(strings); //foreach方式遍历 System.out.println("addAll修改后的集合中的元素是："); traverseListByForEach(list); // remove移除元素 String removeElement = list.remove(); System.out.println("移除的元素是：" + removeElement); System.out.println("remove修改后的集合中的元素是："); traverseListByForEach(list); // add插入元素（在第四个位置插入元素"gg"） list.add(3, "gg"); System.out.println("add插入元素后的集合中的元素是："); traverseListByForEach(list); } /** * foreach方式遍历列表 * @param list 待遍历的列表 */ private static <T> void traverseListByForEach(List<T> list){ for (T t : list){ System.out.print(t + " "); } System.out.println(); } /** * 迭代器方式遍历列表 * @param list 待遍历的列表 */ private static <T> void traverseListByIterator(List<T> list){ Iterator<T> iterator = list.iterator(); // 循环获取列表中的元素 while (iterator.hasNext()) { System.out.print(iterator.next() + " "); } } } 这里仅仅演示了LinkedList的链表操作，主要有add、addAll、remove、set等，几乎每个常用方法都有重载方法，比如只有一个参数的add方法，会直接将该元素插入到列表的尾部，而有两个参数的add方法，会将元素插入指定位置。 LinkedList与ArrayList的对比分析也许你会问，ArrayList不是也挺好用的吗，那些操作ArrayList也能做啊，为什么还要用LinkedList呢？这是一个好问题，ArrayList的最大特点就是能随机访问，因为元素在物理上是连续存储的，所以访问的时候，可以通过简单的算法直接定位到指定位置，所以不管队列的元素数量有多少，总能在O(1)的时间里定位到指定位置，但是连续存储也是它的缺点，导致要在中间插入一个元素的时候，所有之后的元素都要往后挪动。而LinkedList的插入只需要调整前后元素的引用即可。看图说话，ArrayList插入显然需要进行更多的赋值操作，特别是数组元素个数比较多的时候，会更加明显，如果刚好需要扩容的话，那就会更慢了。而LinkedList只需要将插入位置的前后元素的next或prev引用进行调整即可，而且也没有扩容问题，因为它本身就没有容量的概念，理论上可以无限添加元素。然后来实际对比一下效率差距： public abstract class TimeCounter { private String name; TimeCounter(String name){ this.name = name; } public void count(){long time = System.currentTimeMillis(); doSomething(); System.out.println(name + " 耗时：" + (System.currentTimeMillis() - time)); } protected abstract void doSomething(); } 先将这个计时抽象成一个模板，每个需要统计耗时的操作只需要继承该类，然后重写doSomeThing方法即可。 public class Test { public static void main(String[] args){ TimeCounter arrayListAddCounter = new TimeCounter("ArrayList add插入到末尾：") { private List<Integer> list = new ArrayList<>(); @Override protected void doSomething() { for (int i = 0; i < 100000; i++) { list.add( i); } } }; TimeCounter linkedListAddCounter = new TimeCounter("LinkedList add插入到末尾：") { private List<Integer> list = new LinkedList<>(); @Override protected void doSomething() { for (int i = 0; i < 100000; i++) { list.add( i); } } }; arrayListAddCounter.count(); linkedListAddCounter.count(); } } ArrayList add插入到末尾：耗时：11 LinkedList add插入到末尾：耗时：9 好像勉强符合预期，LinkedList比ArrayList略微快一点，其实如果在ArrayList容量足够的情况下，ArrayList的插入元素到末尾操作是要比LinkedList插入要快的，因为它只需要进行一次赋值即可，而LinkedList还需要先new一个新节点然后再接到链表的最后，这个new的过程看起来微不足道，但是一旦循环次数到达一定量级，开销是不可忽略的。例如把上面的循环次数从100000改成1000000，结果就会变成这样： ArrayList add插入到末尾：耗时：40 LinkedList add插入到末尾：耗时：768 这时候，创建节点的开销成了主要时间开销，效率甚至不如ArrayList。我们再换一个插入方式，上面是把元素插入到末尾，这次来把元素插入到首端看看： public class Test { public static void main(String[] args){ TimeCounter arrayListAddCounter = new TimeCounter("ArrayList add插入到首端：") { private List<Integer> list = new ArrayList<>(); @Override protected void doSomething() { for (int i = 0; i < 100000; i++) { list.add(0, i); } } }; TimeCounter linkedListAddCounter = new TimeCounter("LinkedList add插入到首端：") { private List<Integer> list = new LinkedList<>(); @Override protected void doSomething() { for (int i = 0; i < 100000; i++) { list.add(0, i); } } }; arrayListAddCounter.count(); linkedListAddCounter.count(); } } ArrayList add插入到首端：耗时：607 LinkedList add插入到首端：耗时：11 当每次都插入在首端时，ArrayList每次都需要进行元素移动，而且列表中元素越多，需要进行移动的次数也越多，在这种情况下，LinkedList是明显优于ArrayList的。所以说，其实这两者是各有所长各有所短的，一般情况下，选ArrayList就好，除非是需要进行循环操作的次数到达了万的量级的时候，才需要对两者进行选择。也许你会说，既然一般情况下，两者的效率差别不大，那直接用ArrayList就好了，说这么多干嘛呢。哈哈，如果是这样想，那就大错特错了。首先我们不仅需要知其然，还需要知其所以然，如果仅仅知道LinkedList比ArrayList插入效率高，但是却不知道为什么高，高多少，是远远不够的。其次，我们不能仅仅考虑正常情况，对于极端情况也需要有预防措施，对极端情况的思考，正是高手与新手的最大区别。下面再看看查找元素的比较： public class Test { public static void main(String[] args){ TimeCounter arrayListAddCounter = new TimeCounter("ArrayList get遍历元素：") { private List<Integer> list = new ArrayList<>(); { for (int i = 0; i < 100000; i++) { list.add(i); } } @Override protected void doSomething() { for (int i = 0; i < 100000; i++) { list.get(i); } } }; TimeCounter linkedListAddCounter = new TimeCounter("LinkedList get遍历元素：") { private List<Integer> list = new LinkedList<>(); { for (int i = 0; i < 100000; i++) { list.add(i); } } @Override protected void doSomething() { for (int i = 0; i < 100000; i++) { list.get(i); } } }; arrayListAddCounter.count(); linkedListAddCounter.count(); } } ArrayList get遍历元素：耗时：3 LinkedList get遍历元素：耗时：4484 ArrayList完胜，可以看出LinkedList中查找元素是一个十分耗时的操作，甚至比插入元素耗时还要长，因为每次get的时候都是从链表两端进行逐个查找，直到找到指定的位置。想要知道具体细节的话，那就耐心的看看下面的源码解析吧。 LinkedList整体源码分析先来看看LinkedList的整体结构：可以看到LinkedList有四个内部类，分别是Node、ListItr、DescendingIterator、LLSpliterator。Node类主要用于存放元素，先来看看Node： private static class Node<E> { //存放元素 E item; //指向下一个Node节点 Node<E> next; //指向上一个Node节点 Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } 这是可以说是最简单的类了，也构成了LinkedList的基础，LinkedList正是由一个个Node节点连接组成。再来看看ListItr类： //列表迭代器类 private class ListItr implements ListIterator<E> { private Node<E> lastReturned; private Node<E> next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } public boolean hasPrevious() { return nextIndex > 0; } public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } public void remove() { checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++; } public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } public void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); while (modCount == expectedModCount && nextIndex < size) { action.accept(next.item); lastReturned = next; next = next.next; nextIndex++; } checkForComodification(); } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } 这个类是LinkedList的迭代器类，主要用于顺序遍历LinkedList，在前面的栗子中有使用迭代器的hasNext方法和next方法，其实它们的实现都很简单，hasNext只是简单的比较下一个要访问的元素序号是否大于列表中的元素个数，next方法则是将next的引用赋值给lastReturned变量，然后将next指向其下一个节点并且将index加1。但跟普通迭代器不一样的地方在于这个迭代器不仅可以正序遍历，还可以使用previous方法进行倒序遍历，DescendingIterator便是使用了迭代器的previous方法进行便利的。 /** * 降序迭代器 */ private class DescendingIterator implements Iterator<E> { private final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } } 这个迭代器就比较简单了，只是包裹了一个ListItr实例，然后重载了Iterator的几个方法。LLSpliterator是用于并行流的可分割式迭代器，这里就不做过多介绍了。再来看看常用的几个方法的实现： /** * 添加指定元素到列表尾部 */ public boolean add(E e) { linkLast(e); return true; } /** * 把元素e链接成尾节点 */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } 当插入一个元素时，会new一个Node对象，并将该值放入Node节点中，然后挂到链表的尾部。 /** * 在列表指定位置插入指定元素 */ public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } /** * 插入一个元素到指定非空节点之前 */ void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; } add的重载版本，可以指定序号进行插入，将元素插入到链表中间，进行的操作过程可以联系前面的图进行理解。 /** * 返回指定位置的元素 */ public E get(int index) { checkElementIndex(index); return node(index).item; } /** * 返回指定元素序号的非空节点。 */ Node<E> node(int index) { // assert isElementIndex(index); //做了一个小优化，如果取的序号小于元素个数的一半，则从链表首端开始遍历，否则从链表尾部开始遍历 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } 可以看到get方法其实是从头部或者尾部进行遍历定位的，每次将x的引用向后/向前移动一位，当链表数据量比较大时，这个过程其实是很耗时间的，前面的对比中应该也能发现这一点。 /** * 取回并删除此列表的头部（第一个元素）。 */ public E remove() { return removeFirst(); } /** * 移除列表指定位置的元素，如果其后子序列存在，则将其元素左移，将它们的序号减一。 * 返回列表中移除的元素。 */ public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } /** * 移除并返回首节点 */ public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } /** * 移除首节点并返回该节点元素值 */ private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; } /** * 移除非空节点x */ E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; } remove方法也有两个重载版本，不带参数的remove方法仅仅移除并返回最后一个节点，而指定序号参数的remove方法则会移除并返回链表中指定位置的节点。此外链表还有可以用于队列的诸多方法：在尾部添加元素：(add, offer)，add()会在长度不够时抛出异常：IllegalStateException; offer()则不会,只返回false。查看头部元素 (element, peek)，返回头部元素，但不改变队列。element()会在没元素时抛出异常：NoSuchElementException; peek()返回null; 删除头部元素 (remove,poll)，返回头部元素，并且从队列中删除，remove()会在没元素时抛出异常：NoSuchElementException; poll()返回null; 即可以通过以上方法来实现单向队列的操作，也可以使用addFirst,addLast,removeFirst,removeLast方法来实现双向队列的操作。以下是一个简单队列的实现： public class MyQueue<T> { private LinkedList<T> list = new LinkedList<T>(); //清空队列 public void clear() { list.clear(); } //判断队列是否为空 public boolean isEmpty() { return list.isEmpty(); } //进队 public void enqueue(T o) { list.addLast(o); } //出队 public T dequeue(){ if(!list.isEmpty()) { return list.removeFirst(); } return null; } //获取队列长度 public int length() { return list.size(); } //查看队首元素 public T peek() { return list.getFirst(); } //测试队列 public static void main(String[] args) { MyQueue<String> queue = new MyQueue<String>(); System.out.println(queue.isEmpty()); queue.enqueue("a"); queue.enqueue("b"); queue.enqueue("c"); queue.enqueue("d"); queue.enqueue("e"); queue.enqueue("f"); System.out.println(queue.length()); System.out.println(queue.dequeue()); System.out.println(queue.dequeue()); System.out.println(queue.peek()); System.out.println(queue.dequeue()); queue.clear(); queue.enqueue("s"); queue.enqueue("t"); queue.enqueue("r"); System.out.println(queue.dequeue()); System.out.println(queue.length()); System.out.println(queue.peek()); System.out.println(queue.dequeue()); } } 嗯，其实就是借鸡生蛋的事情嘛，哈哈。再来看看用LinkedList的简单栈实现： public class MyStack<T> { private LinkedList<T> stack = new LinkedList<T>(); // 入栈 public void push(T v) { stack.addFirst(v); } // 出栈，但不删除 public T peek() { return stack.getFirst(); } // 出栈 public T pop() { return stack.removeFirst(); } // 栈是否为空 public boolean empty() { return stack.isEmpty(); } // 打印栈元素 public String toString() { return stack.toString(); } } 你看，其实很简单吧，LinkedList提供的大量的方法，可以很方便的进行链表、双向链表、队列、双端队列、栈等数据结构的实现，可以说非常好用了。下面是LinkedList的全部源码，行有余力的话可以选择你想要了解的部分进行阅读，如果有不懂的地方可以在本文后面留言，当然，也可以直接跳过，以后想要深入了解的时候再进行阅读也不迟。 /** * 双向链表实现了List接口和Deque接口，实现了多有可选List操作，并且允许放入所有的元素，包括null。 * * 所有的操作都表现得像双向链表，索引到列表中的操作将从开头或者结尾遍历列表，以较接近指定索引为准。 * * 注意，这个实现类不是线程安全的，如果多个线程同时访问一个链表，并且至少一个线程修改了链表的结构， * 则必须在外部实现同步。结构性修改指的是那些增加删除一个或多个元素的操作，仅设置元素的值不是结构修改。 * 这通常通过在封装列表的某个对象上进行同步来实现。 * * 如果没有这样的对象存在，则列表应该使用Collections#synchronizedList方法包装，最好在创建列表的时候进行， * 以防止意外的非同步引用对列表进行了修改。 * List list = Collections.synchronizedList(new LinkedList(...)); * * 该类的iterator方法和listIterator方法返回的迭代器是“fail-fast”的，如果列表在迭代器创建之后的任何时刻被进行 * 结构性的修改了，则调用迭代器自身的remove或者add方法时将会抛出ConcurrentModificationException异常，因此 * 当遇到并发修改时，迭代器会快速的失败，而不是在未来某个不确定的时刻进行武断冒险或不确定性的行为 * * 注意，通常来说，不能保证迭代器的fail-fast机制，在遇到非同步的并发修改时，不可能做出任何严格的保证。 * fail-fast 迭代器只能尽最大努力抛出ConcurrentModificationException异常，因此，如果程序依赖这个异常来 * 进行正确性判断是错误的，fail-fast机制仅应该用于检测异常。 * */ public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; /** * 指向第一个节点 * 恒等式: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * 指向最后一个节点 * 恒等式: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last; /** * 构造一个空的列表 */ public LinkedList() { } /** * 构造一个包含指定集合内所有元素的列表，存储的顺序为集合的迭代器访问顺序。 * @throws NullPointerException 空指针异常 */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); } /** * 把元素e链接成首节点 */ private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } /** * 把元素e链接成尾节点 */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } /** * 插入一个元素到指定非空节点之前 */ void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; } /** * 移除首节点并返回该节点元素值 */ private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; } /** * 移除尾节点并返回该节点元素值 */ private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; } /** * 移除非空节点x */ E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; } /** * 返回列表的首节点 */ public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } /** * 返回列表的最后一个节点 */ public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } /** * 移除并返回首节点 */ public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } /** * 移除并返回尾节点 */ public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } /** * 插入指定元素到列表首端 */ public void addFirst(E e) { linkFirst(e); } /** * 扩展指定元素到列表尾端 */ public void addLast(E e) { linkLast(e); } /** * 返回列表中是否包含指定元素 */ public boolean contains(Object o) { return indexOf(o) != -1; } /** * 返回列表中元素个数 */ public int size() { return size; } /** * 添加指定元素到列表尾部 */ public boolean add(E e) { linkLast(e); return true; } /** * 如果该元素存在，则移除列表中首次出现的该指定元素，如果不存在，则原链表不会改变。 * 如果该列表中包含该指定元素则返回true，否则返回false */ public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /** * 添加指定集合中的所有元素到列表的尾部，顺序为指定集合的迭代器遍历顺序。如果该操作正在进行时，指定集合 * 被修改了，那么该操作的行为是不可预测的。 */ public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } /** * 将指定集合中的所有元素插入到该列表的指定位置之后。将当前在该位置的元素及其之后的元素右移。新元素在列表 * 中的顺序为其原集合迭代器遍历顺序。 */ public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; Node<E> pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; } /** * 移除列表中所有元素 */ public void clear() { // 清除节点之间所有元素的链接不是必要的，但是: // - 如果被清除的节点处于不同代之间，可以帮助分代GC。 // - 一定要释放内存，即便有一个迭代器引用 for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; } // 位置访问操作 /** * 返回指定位置的元素 */ public E get(int index) { checkElementIndex(index); return node(index).item; } /** * 使用指定元素替换指定位置的元素 */ public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; } /** * 在列表指定位置插入指定元素，如果该位置有任何元素，则将其后的子序列元素都往右移（将它们的序号都增加1） */ public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } /** * 移除列表指定位置的元素，如果其后子序列存在，则将其元素左移，将它们的序号减一。 * 返回列表中移除的元素。 */ public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } /** * 判断该序号是否在列表中对应位置存在元素 */ private boolean isElementIndex(int index) { return index >= 0 && index < size; } /** * 判断给参数是否是迭代器或者add操作的合法位置 */ private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } /** * 构造一个IndexOutOfBoundsException 异常的详情消息，在错误处理代码的许多可能的重构中， * 这个大纲在服务端和客户端虚拟机中都表现的最好。 */ private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * 返回指定元素序号的非空节点。 */ Node<E> node(int index) { // assert isElementIndex(index); //做了一个小优化，如果取的序号小于元素个数的一半，则从链表首端开始遍历，否则从链表尾部开始遍历 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } // 搜索操作 /** * 返回指定元素在列表中第一次出现的位置，否则返回-1 */ public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } /** * 返回指定元素在链表中最后一次出现的位置，如果链表中不包含该元素，则返回-1 */ public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node<E> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; } // 队列操作 /** * 取回但不删除此列表的头部（第一个元素）。 */ public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; } /** * 取回但不删除此列表的头部（第一个元素）。 * 如果不存在，则会抛出NoSuchElementException异常 */ public E element() { return getFirst(); } /** * 取回并删除此列表的头部（第一个元素）。 * 如果该链表为空，则返回null */ public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } /** * 取回并删除此列表的头部（第一个元素）。 */ public E remove() { return removeFirst(); } /** * 添加指定元素到链表尾部 */ public boolean offer(E e) { return add(e); } // 双向队列操作 /** * 插入指定元素到队列首部 */ public boolean offerFirst(E e) { addFirst(e); return true; } /** * 插入指定元素到队列尾部 */ public boolean offerLast(E e) { addLast(e); return true; } /** * * 取回但是不删除队列的首元素。如果队列为空则返回null。 */ public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; } /** * 取回但是不删除链表的最后一个元素，如果队列为空，则返回null */ public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; } /** * 取回并删除队列的首元素，如果队列为空，则返回null */ public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } /** * 取回并删除队列的尾元素，如果队列为空，则返回null */ public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); } /** * 在队列前端插入元素 */ public void push(E e) { addFirst(e); } /** * 删除并返回队列的第一个元素，如果列表为空则抛出NoSuchElementException 异常 */ public E pop() { return removeFirst(); } /** * 删除此队列中第一个出现的指定元素（从头到尾的方式遍历时），如果队列中不包含该元素，则队列不会改变。 */ public boolean removeFirstOccurrence(Object o) { return remove(o); } /** * 删除此队列中最后一次出现的指定元素（从头到尾的方式遍历时），如果队列中不包含该元素，则队列不会改变。 */ public boolean removeLastOccurrence(Object o) { if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /** * 返回从指定位置开始，以正确的序列迭代该列表的迭代器. * 列表迭代器是“fail-fast”的，如果列表在迭代器创建之后的任何时刻被进行 * 结构性的修改了，则调用迭代器自身的remove或者add方法时将会抛出ConcurrentModificationException异常，因此 * 当遇到并发修改时，迭代器会快速的失败，而不是在未来某个不确定的时刻进行武断冒险或不确定性的行为 * * 注意，通常来说，不能保证迭代器的fail-fast机制，在遇到非同步的并发修改时，不可能做出任何严格的保证。 * fail-fast 迭代器只能尽最大努力抛出ConcurrentModificationException异常，因此，如果程序依赖这个异常来 * 进行正确性判断是错误的，fail-fast机制仅应该用于检测异常。 */ public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); } //列表迭代器类 private class ListItr implements ListIterator<E> { //记录上一个返回的节点 private Node<E> lastReturned; //指向下一个节点 private Node<E> next; //下一个节点的序号 private int nextIndex; //用于检测遍历过程中List是否被修改 private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { //检测是否修改 checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } public boolean hasPrevious() { return nextIndex > 0; } public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } public void remove() { checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++; } public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } public void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); while (modCount == expectedModCount && nextIndex < size) { action.accept(next.item); lastReturned = next; next = next.next; nextIndex++; } checkForComodification(); } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } private static class Node<E> { //存放元素 E item; //指向下一个Node节点 Node<E> next; //指向上一个Node节点 Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } /** * 返回一个倒序遍历的迭代器 */ public Iterator<E> descendingIterator() { return new DescendingIterator(); } /** * 降序迭代器 */ private class DescendingIterator implements Iterator<E> { private final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } } private LinkedList<E> superClone() { try { return (LinkedList<E>) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(e); } } /** * 浅克隆 */ public Object clone() { LinkedList<E> clone = superClone(); // Put clone into "virgin" state clone.first = clone.last = null; clone.size = 0; clone.modCount = 0; // Initialize clone with our elements for (Node<E> x = first; x != null; x = x.next) clone.add(x.item); return clone; } /** * 返回一个包含列表所有元素的数组，元素的顺序为从第一个到最后一个。 */ public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; } /** * 返回一个包含列表所有元素的数组，元素的顺序为从第一个到最后一个。返回元素数组的类型 * 与指定数组的类型一致。如果列表大小适合指定的数组，则返回该数组。否则，将为新数组分配指定 * 数组的运行时类型和此列表的大小。 * * 如果列表的空间适合指定的数组（数组比列表有更多的元素），紧跟在列表末尾之后的数组中的元素设置 * 为null（仅当调用者知道列表不包含任何null元素时，这在确定列表长度时很有用。） */ @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); int i = 0; Object[] result = a; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; if (a.length > size) a[size] = null; return a; } private static final long serialVersionUID = 876323262645176354L; /** * 序列化 */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject(); // Write out size s.writeInt(size); // Write out all elements in the proper order. for (Node<E> x = first; x != null; x = x.next) s.writeObject(x.item); } /** * 反序列化 */ @SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject(); // Read in size int size = s.readInt(); // Read in all elements in the proper order. for (int i = 0; i < size; i++) linkLast((E)s.readObject()); } /** * 创建一个可分割的迭代器 */ @Override public Spliterator<E> spliterator() { return new LLSpliterator<E>(this, -1, 0); } /** Spliterators.IteratorSpliterator 的定制版本 */ static final class LLSpliterator<E> implements Spliterator<E> { static final int BATCH_UNIT = 1 << 10; // batch array size increment static final int MAX_BATCH = 1 << 25; // max batch array size; final LinkedList<E> list; // null OK unless traversed Node<E> current; // current node; null until initialized int est; // size estimate; -1 until first needed int expectedModCount; // initialized when est set int batch; // batch size for splits LLSpliterator(LinkedList<E> list, int est, int expectedModCount) { this.list = list; this.est = est; this.expectedModCount = expectedModCount; } final int getEst() { int s; // force initialization final LinkedList<E> lst; if ((s = est) < 0) { if ((lst = list) == null) s = est = 0; else { expectedModCount = lst.modCount; current = lst.first; s = est = lst.size; } } return s; } public long estimateSize() { return (long) getEst(); } public Spliterator<E> trySplit() { Node<E> p; int s = getEst(); if (s > 1 && (p = current) != null) { int n = batch + BATCH_UNIT; if (n > s) n = s; if (n > MAX_BATCH) n = MAX_BATCH; Object[] a = new Object[n]; int j = 0; do { a[j++] = p.item; } while ((p = p.next) != null && j < n); current = p; batch = j; est = s - j; return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED); } return null; } public void forEachRemaining(Consumer<? super E> action) { Node<E> p; int n; if (action == null) throw new NullPointerException(); if ((n = getEst()) > 0 && (p = current) != null) { current = null; est = 0; do { E e = p.item; p = p.next; action.accept(e); } while (p != null && --n > 0); } if (list.modCount != expectedModCount) throw new ConcurrentModificationException(); } public boolean tryAdvance(Consumer<? super E> action) { Node<E> p; if (action == null) throw new NullPointerException(); if (getEst() > 0 && (p = current) != null) { --est; E e = p.item; current = p.next; action.accept(e); if (list.modCount != expectedModCount) throw new ConcurrentModificationException(); return true; } return false; } public int characteristics() { return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; } } } 最后，再对LinkedList做一个简单的小结： LinkedList是由Node节点首尾相连而成的结构，相比ArrayList而言，在进行插入和删除时不需要进行大量的元素移动，省去了元素复制的开销，也不存在扩容开销，但是每次添加节点都需要创建一个新的Node对象，所以当节点数量很多时，这部分对象将占用很大开销，包括时间成本和空间成本，因此需要根据实际情况进行合理选择。LinkedList因为提供了大量方便的获取元素、插入元素和移除元素的方法，所以可以很方便的进行队列、栈等数据结构的实现。到此，LinkedList就算讲解完毕了，一不小心又写了这么长，罪过罪过。。。下次还是多分几篇写吧，这么长的文章，确实不便于阅读，面壁中。。。真正重要的东西，用眼睛是看不见的。

2018-08-01

计科专业大一学生一枚，如何提高编程能力？

先简单介绍一下我的情况：大概去年的这个时候从学校毕业，二本A软件工程，现在在北上广深之一的某卫星城从事互联网相关工作，月薪勉强养活自己。看上去一份很没说服力的简历，希望我下面的话，不会让你有这个感觉。对于如何提升自己的编程能力。其他的回答中很多人都说了，这没什么捷径，就是多练，问题是并没有人说怎么练？一天敲50遍Hello Word算多练嘛？当然，各路大佬自然是知道该怎么练的，只是懒得在逼乎上浪费时间。我属于比较爱扯淡的，就在这里长篇大论的扯一波儿，不喜勿喷。首先、什么算你所谓的编程能力？我们对一项技能的掌握程度往往很难量化，对于编程能力的考量可能比较抽象，我们来类比比较直观的其他技能。比如说什么叫会弹吉他？我们说一个人吉他玩的好，这个人会弹吉他，是指他会弹《小星星》？还是会弹岸部真明的《time travel》？（力荐，好听！）

2018-06-28

【Java入门提高篇】Day20 Java容器类详解（三）List接口

今天要说的是Collection族长下的三名大将之一，List，Set，Queue中的List，它们都继承自Collection接口，所以Collection接口的所有操作，它们自然也是有的。 List，Set，Queue，分别是列表，集合，队列的意思，代表着Collection家族下的三种不同的势力，它们各有所长，也各有所短，就像骑兵，步兵和水兵，各有各的优势，并没有谁一定比谁更好的说法，合适的才是最好的。接下来，将会分别介绍这三名大将，从中你也会看到它们各自的特点。本篇先来介绍一下List接口。我们先来看看List的源码： public interface List<E> extends Collection<E> { // 查询接口 /** * 列表元素个数 */ int size(); /** * 是否为空 */ boolean isEmpty(); /** * 是否包含某元素 */ boolean contains(Object o); /** * 返回一个List迭代器 */ Iterator<E> iterator(); /** * 将List转换为Object数组 */ Object[] toArray(); /** * 转换为指定类型数组 */ <T> T[] toArray(T[] a); // 修改操作 /** * 添加元素，成功返回true */ boolean add(E e); /** * 移除某一个元素，成功返回true */ boolean remove(Object o); // 批量操作 /** * 判断是否包含集合C 中的所有元素 */ boolean containsAll(Collection<?> c); /** * 将集合C 中所有元素添加到列表 */ boolean addAll(Collection<? extends E> c); /** * 将集合C 中所有元素添加到列表，添加在序号为index的元素之后 */ boolean addAll(int index, Collection<? extends E> c); /** * 从列表中移除集合C 中所有元素 */ boolean removeAll(Collection<?> c); /** * 从列表中移除所有不在集合C 中的元素 */ boolean retainAll(Collection<?> c); /** * 全部替换 */ default void replaceAll(UnaryOperator<E> operator) { Objects.requireNonNull(operator); final ListIterator<E> li = this.listIterator(); while (li.hasNext()) { li.set(operator.apply(li.next())); } } /** * 根据指定的比较器来排序，如果传入的比较器是null，则元素必须实现Comparable 接口 */ @SuppressWarnings({"unchecked", "rawtypes"}) default void sort(Comparator<? super E> c) { Object[] a = this.toArray(); Arrays.sort(a, (Comparator) c); ListIterator<E> i = this.listIterator(); for (Object e : a) { i.next(); i.set((E) e); } } /** * 移除所有元素 */ void clear(); // 比较和hash boolean equals(Object o); int hashCode(); // 根据序号进行的操作 /** * 获取指定序号的元素 */ E get(int index); /** * 替换指定序号的元素 */ E set(int index, E element); /** * 在指定序号的元素后插入元素 */ void add(int index, E element); /** * 移除指定序号的元素 */ E remove(int index); // 搜索操作 /** * 返回元素第一次出现的位置，如果未找到则返回-1 */ int indexOf(Object o); /** * 返回元素出现的最后一个位置 */ int lastIndexOf(Object o); // List迭代器 /** * 返回一个List迭代器 */ ListIterator<E> listIterator(); /** * 返回一个序号从Index开始的List迭代器 */ ListIterator<E> listIterator(int index); // 视图 /** * 返回一个子队列，序列从fromIndex到toIndex，包含fromIndex，不包含toIndex * 对子队列的修改会影响原队列 * 如果原队列修改，那么对子队列的影响是未定义的 */ java.util.List<E> subList(int fromIndex, int toIndex); /** * 创建一个可分割的迭代器（用于并行计算） */ @Override default Spliterator<E> spliterator() { return Spliterators.spliterator(this, Spliterator.ORDERED); } } 其实JDK里的注释已经十分丰富，大家平时有时间可以多看看，为了方便阅读，我这里用简单粗暴的语言进行了精简翻译。 List即列表，存储的是有序集合，里面的元素有序存储，可以重复，所谓有序集合，顾名思义，就是里面的元素存放是有顺序的，每个插入的元素都对应着一个序号，可以根据序号获取元素。 List支持的操作也很丰富，最常用的增删改查，批量添加，批量替换，批量删除，还有搜索，排序操作，还支持普通迭代器和可分割式迭代器，前者主要用于遍历，后者则主要用于并行式计算，关于迭代器的知识后面会统一介绍。下面是使用常见操作的一个小栗子： public class Test { public static void main(String[] args){ test(); } static void test(){ List<Integer> integers = new ArrayList<>(); List<Integer> integersA = new ArrayList<>(); //添加元素 integers.add(1); integers.add(2); integers.add(3); integers.add(4); integersA.add(1); integersA.add(2); integersA.add(33); integersA.add(44); System.out.println("列表大小：" + integers.size()); System.out.println("是否为空：" + integers.isEmpty()); System.out.println("是否包含某元素：" + integers.contains(2)); System.out.println("是否包含全部元素：" + integers.containsAll(integersA)); //转换为数组 Integer[] integerArray = integers.toArray(new Integer[0]); System.out.println("遍历数组："); for (int i = 0; i < integerArray.length; i++){ System.out.println(integerArray[i]); } System.out.println("当前列表integers：" + integers); //批量添加 System.out.println("批量添加元素"); integers.addAll(integersA); System.out.println("当前列表integers：" + integers); //移除元素 System.out.println("移除元素"); integers.remove(1); System.out.println("当前列表integers：" + integers); //批量移除 System.out.println("批量移除元素"); integers.removeAll(integersA); System.out.println("当前列表integers：" + integers); //开始替换 System.out.println("批量替换元素"); integers.replaceAll(it -> it + 1); System.out.println("当前列表integers：" + integers); //从列表中移除所有不在集合integersA中的元素 integersA.add(2); integersA.add(4); System.out.println("保留元素"); integers.retainAll(integersA); System.out.println("当前列表integers：" + integers); //插入 System.out.println("开始插入"); System.out.println("当前列表integersA：" + integersA); integersA.add(2,155); integersA.add(1,125); System.out.println("当前列表integersA：" + integersA); //排序 System.out.println("开始排序——使用内部比较器"); integersA.sort(null); System.out.println("当前列表integersA：" + integersA); System.out.println("开始排序——使用外部比较器"); integersA.sort((itA, itB) -> itB - itA); System.out.println("当前列表integersA：" + integersA); //序号操作 Integer a = integersA.get(2); System.out.println("integersA第三个元素是：" + a); System.out.println("开始替换"); integersA.set(3, 66); System.out.println("当前列表integersA：" + integersA); System.out.println("开始移除"); integersA.remove(3); System.out.println("当前列表integersA：" + integersA); //搜索操作 System.out.println("查找元素2(第一次出现)位置：" + integersA.indexOf(2)); System.out.println("查找元素2(最后一次出现)位置：" + integersA.lastIndexOf(2)); //子队列操作 List<Integer> subList = integersA.subList(0, 4); System.out.println("子队列：" + subList); subList.add(5); subList.add(5); subList.add(5); System.out.println("当前子列表：" + subList); System.out.println("当前列表integersA：" + integersA); integersA.add(1, 233); integersA.add(1, 233); integersA.add(1, 233); System.out.println("当前列表integersA：" + integersA); System.out.println("当前子列表：" + subList); } } 大家可以先想想结果，再下看面的答案。实际输出如下：列表大小：4 是否为空：false 是否包含某元素：true 是否包含全部元素：false 遍历数组： 1 2 3 4 当前列表integers：[1, 2, 3, 4] 批量添加元素当前列表integers：[1, 2, 3, 4, 1, 2, 33, 44] 移除元素当前列表integers：[1, 3, 4, 1, 2, 33, 44] 批量移除元素当前列表integers：[3, 4] 批量替换元素当前列表integers：[4, 5] 保留元素当前列表integers：[4] 开始插入当前列表integersA：[1, 2, 33, 44, 2, 4] 当前列表integersA：[1, 125, 2, 155, 33, 44, 2, 4] 开始排序——使用内部比较器当前列表integersA：[1, 2, 2, 4, 33, 44, 125, 155] 开始排序——使用外部比较器当前列表integersA：[155, 125, 44, 33, 4, 2, 2, 1] integersA第三个元素是：44 开始替换当前列表integersA：[155, 125, 44, 66, 4, 2, 2, 1] 开始移除当前列表integersA：[155, 125, 44, 4, 2, 2, 1] 查找元素33(第一次出现)位置：4 查找元素33(最后一次出现)位置：5 子队列：[155, 125, 44, 4] 当前子列表：[155, 125, 44, 4, 5, 5, 5] 当前列表integersA：[155, 125, 44, 4, 5, 5, 5, 2, 2, 1] 当前列表integersA：[155, 233, 233, 233, 125, 44, 4, 5, 5, 5, 2, 2, 1] Exception in thread "main" java.util.ConcurrentModificationException at java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1239) at java.util.ArrayList$SubList.listIterator(ArrayList.java:1099) at java.util.AbstractList.listIterator(AbstractList.java:299) at java.util.ArrayList$SubList.iterator(ArrayList.java:1095) at java.util.AbstractCollection.toString(AbstractCollection.java:454) at java.lang.String.valueOf(String.java:2994) at java.lang.StringBuilder.append(StringBuilder.java:131) at com.frank.chapter20.Test.test(Test.java:115) at com.frank.chapter20.Test.main(Test.java:15) 不知道符不符合你的预期，这里关于内部比较器和外部比较器的知识只一笔带过，Integer类型是实现了Comparable接口的，所以sort方法传入null时会使用Integer的内部比较器进行排序，而使用外部比较器时，使用的是Java8的新特性，lamada表达式，省去了方法名和参数类型，因为函数式接口不存在重载方法，所以编译器可以推断出参数类型，这样就不用再大费周章的用new语法去创建一个比较器（当然，只是语法糖而已，如果不是很理解比较器，可以先行百度，后面的文章里也会有详细介绍）。在最后报出了一个ConcurrentModificationException，因为原队列修改后，子队列视图就被破坏了，所以再次访问子视图时就会报错。 List是最常用的容器类，List最大的特点便是要求元素有序存储，List跟数组相比，最大的优势在于List大小可以动态扩展，但数组支持随机存取，所以当元素个数的固定的时候，使用数组往往效率更高。（当然，一般情况下还是使用List吧，因为支持的操作更加丰富，比如进行排序时不需要自己写算法）。一般来说，对元素没有特殊要求，不需要去重存储，没有先进先出的要求的场景下，List是最好的选择。 List接口下有多个常用的实现类，每个类都有其特点，具体选择哪种类需要根据实际情况进行选择。希望大家能通过这篇文章，了解List的主要方法及其使用方法以及常用场景，关于List的常见具体实现类的讲解将在之后的文章里进行说明和比较。本篇到此结束，欢迎大家继续关注。真正重要的东西，用眼睛是看不见的。

2018-05-30

【Java入门提高篇】Day19 Java容器类详解（二）Map接口

上一篇里介绍了容器家族里的大族长——Collection接口，今天来看看容器家族里的二族长——Map接口。 Map也是容器家族的一个大分支，但里面的元素都是以键值对（key-value）的形式存放的，就像字典一样，用相应的key就可以拿到相应的value。先来看看Map接口的内容，下面是阉割版的Map接口（去掉了defaultmethod），去掉的部分涉及Stream操作，属于Map的高级用法，所以暂时不做介绍。 import java.io.Serializable; import java.util.Collection; import java.util.Comparator; import java.util.Objects; import java.util.Set; public interface Map<K,V> { // 查询操作 /** * 返回键值对数量 */ int size(); /** * Map是否为空 */ boolean isEmpty(); /** * Map中是否包含指定的key */ boolean containsKey(Object key); /** * Map中是否包含指定的value */ boolean containsValue(Object value); /** * 根据key获取对应的value */ V get(Object key); // Modification Operations /** * 插入键值对，如果Map中已经存在该key，则新的value会覆盖原来的value */ V put(K key, V value); /** * 移除指定key对应的键值对，并返回相应的value */ V remove(Object key); // 批量操作 /** * 将另一个Map中的键值对全部复制过来 */ void putAll(Map<? extends K, ? extends V> m); /** * 移除所有键值对 */ void clear(); // 视图 /** * 返回包含Map中所有key的（Set类型）键视图，对Map的修改也会影响到键视图 */ Set<K> keySet(); /** * 返回包含Map中所有value的（Collection类型）值视图，对Map的修改也会影响到值视图 */ Collection<V> values(); /** * 返回包含Map中所有键值对的（java.util.Map.Entry类型）键值对视图 */ Set<Map.Entry<K, V>> entrySet(); /** * Map 键值对接口 */ interface Entry<K,V> { /** * 返回键 */ K getKey(); /** * 返回值 */ V getValue(); /** * 设置键 */ V setValue(V value); boolean equals(Object o); int hashCode(); /** * 键比较器（内部比较器） */ public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() { return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> c1.getKey().compareTo(c2.getKey()); } /** * 值比较器（内部比较器） */ public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() { return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> c1.getValue().compareTo(c2.getValue()); } /** * 键比较器（外部比较器） */ public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) { Objects.requireNonNull(cmp); return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey()); } /** * 值比较器（外部比较器） */ public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) { Objects.requireNonNull(cmp); return (Comparator<Map.Entry<K, V>> & Serializable) (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue()); } } // 比较和散列 boolean equals(Object o); int hashCode(); } 可以看到，Map接口的内容，其实比Collection接口更丰富，这里因为省略了很多高级方法，而且里面包含了另外一个接口，Map.Entry接口，也就是一直所说的键值对，这个接口是Map中元素需要实现的接口。 Map有三种遍历方式：1.通过遍历KeySet来遍历所有键值对，2.通过遍历EntrySet来实现，3.通过EntrySet的Iterator来遍历。这里还有一个新概念——视图，视图其实就是一个集合，但是是一个不能修改的集合，只能对视图进行查询和遍历操作，在Map中一共有三个视图，键视图，值视图，键值对视图，下面可以看一个小栗子： public class Test { public static void main(String[] args){ Map<Integer, Integer> map = new HashMap<>(); map.put(1,11); map.put(2,22); map.put(3,33); Set<Integer> keys = map.keySet(); Collection<Integer> values = map.values(); Set<Map.Entry<Integer,Integer>> entries = map.entrySet(); Iterator<Map.Entry<Integer,Integer>> iterator = entries.iterator(); System.out.println(keys); System.out.println(values); System.out.println(entries); System.out.println("按keyset遍历"); for (Integer key : keys){ System.out.println("key:" + key + " value:" + map.get(key)); } System.out.println("按键值对遍历"); for (Map.Entry<Integer,Integer> entry : entries){ System.out.println("entry:" + entry); } System.out.println("按iterator遍历"); while (iterator.hasNext()){ Map.Entry<Integer,Integer> entry = iterator.next(); System.out.println("entry:" + entry); } map.put(2,444); map.put(4,44); System.out.println("修改后的视图"); System.out.println(keys); System.out.println(values); System.out.println(entries); keys.add(5); values.add(55); } } 输出如下： [1, 2, 3] [11, 22, 33] [1=11, 2=22, 3=33] 按keyset遍历 key:1 value:11 key:2 value:22 key:3 value:33 按键值对遍历 entry:1=11 entry:2=22 entry:3=33 按iterator遍历 entry:1=11 entry:2=22 entry:3=33 修改后的视图 [1, 2, 3, 4] [11, 444, 33, 44] [1=11, 2=444, 3=33, 4=44] Exception in thread "main" java.lang.UnsupportedOperationException at java.util.AbstractCollection.add(AbstractCollection.java:262) at com.frank.chapter19.Test.main(Test.java:44) 栗子里介绍了三种遍历方式，也看到了三种视图的样子，当我们试图修改视图时，抛出了一个UnsupportedOperationException异常，表明该视图集合无法修改。在Map.Entry接口里，还可以看到外部比较器和内部比较器，这两个概念暂时也不做介绍，在之后的文章里会介绍。关于Map，要说的主要就这么多了，目前来说只需要知道Map是以键值对的形式进行存取，并了解Map接口中的主要方法及其作用，了解Map的遍历方法，和视图的概念就已经足够了。本篇到此结束，欢迎大家继续关注。真正重要的东西，用眼睛是看不见的。

2018-05-21

【Java入门提高篇】Day18 Java容器类详解（一）Collection接口

今天来看看Java里的一个大家伙，那就是容器。所谓容器，就是专门用来装对象的东西，如果你学过高数，没错，就跟里面说的集合是一个概念，就是一堆对象的集合体，但是集合类是容器类中的一个子集，为了区别表示，所以还是叫容器类，之后所说的集合类只是容器里的一个子集，之后会有详细介绍。容器就是用来存放和管理其他类对象的地方，你可以把它理解为仓库管家，当你有东西需要存放和管理的时候，就要记得来找它。你也许会说，不是有数组吗？确实，用数组存放一堆相同类型对象也是一个不错的选择，但是有一个很大的缺陷，那就是数组大小只能是固定的，不能从数组里动态添加和删除一个对象，要扩容的时候，就只能新建一个数组然后把原来的对象全部复制到新的数组里，而且只能存放相同类型的对象，使用起来不够灵活。然而我们的管家就不一样了。国际惯例，先来看一个栗子： public class Test { public static void main(String args[]){ //小明打算学Java，买了三本书 Book bookA = new Book("Java核心技术（卷一）", 88.9); Book bookB = new Book("Java核心技术（卷二）", 88.6); Book bookC = new Book("Java编程思想", 99.0); //他想了想，放哪呢？到处放怕之后会找不到，放书架以后书变多了找起来就很麻烦 //于是他找了个管家 Map<String, Book> bookMap = new HashMap<>(3); //然后跟管家说，这三本书先放你这了，要用的时候找你拿 bookMap.put(bookA.getName(), bookA); bookMap.put(bookB.getName(), bookB); bookMap.put(bookC.getName(), bookC); //勤劳的管家兢兢业业的保存好了三本书 //小明回到家，想检查一下管家老不老实 //“管家，把Java核心技术（卷一）给我拿过来” Book bookD = bookMap.get("Java核心技术（卷一）"); //他查看了一下这本书的信息并跟原来的信息校验了一番 System.out.println(bookD); System.out.println(bookA.equals(bookD)); //并同样校验了另外两本书 Book bookE = bookMap.get("Java核心技术（卷二）"); System.out.println(bookE); System.out.println(bookB.equals(bookE)); Book bookF = bookMap.get("Java编程思想"); System.out.println(bookF); System.out.println(bookC.equals(bookF)); //嗯，看来管家没有玩花样，还是原来的书，晚饭给他加个蛋 } } class Book{ private String name; private Double price; public Book(String name, Double price) { this.name = name; this.price = price; } public Double getPrice() { return price; } public void setPrice(Double price) { this.price = price; } public String getName() { return name; } public void setName(String name) { this.name = name; } @Override public String toString() { return "Book{" + "name='" + name + '\'' + ", price=" + price + '}'; } } 输出如下： Book{name='Java核心技术（卷一）', price=88.9} true Book{name='Java核心技术（卷二）', price=88.6} true Book{name='Java编程思想', price=99.0} true 相信大家看过小明和管家的故事之后，对容器这个概念应该有初步的了解了。容器一般来说就是在你需要存放一系列对象时，可以给你管理对象的好管家。当然，容器家族里并不只有HashMap这一个管家，最开始就说了，容器可是一个庞大的家族。先来看一张图感受一下吧：好像有点多？关系有点复杂。没错，除了并发包里的集合类以外的大部分容器类差不多都在这了，这个图，emmmm...看看就好，我们还是看下面这个图吧别慌，其实最常用的就是这么几个了，Collection和Map是两个大的接口，Collection下有三个子接口，List，Queue，Set，下面是最常用的三个类，ArrayList，LinkedList，HashSet。Map接口下最常用的就要数上面栗子里的HashMap了。正如你看到的那样，容器类里有很多不同的实现类，也就是不同的管家，他们有的不同的能力，各有所长也各有所短，至于他们的具体介绍，将会留到之后的几篇文章里介绍，本篇作为集合的介绍篇就不多做讲解了。需要注意的是，容器中只能存放对象，而不能存放基本类型。所以当你将一个 int 型数据 1放入容器中的时候，其实它会自动装箱转换成 Integer 类后存入的，Java中每一种基本类型都有对应的引用类型。在容器存放的是多个对象的引用，对象本身还是放在堆内存中。容器可以存放不同类型，不限数量的数据类型。 Collection接口 Collection接口是容器家族里的老大哥，是最基本的容器接口，但是这里的Collection跟容器并不是等价关系，因为你仔细看看上面的图就知道，容器家族里还有另外一个老大哥，那就是Map接口。一个Collection代表一组Object，即Collection的元素（Elements）。Collection接口下有三个子接口，分别是List，Set，Queue，它们各有各的特点，下面会一一介绍，但是都继承于Collection接口，所以继承了Collection的所有特性。我们可以来看看Collection接口都有哪些方法： public interface Collection<E> extends Iterable<E> { //查询操作 /** * 返回集合中元素个数 */ int size(); /** * 集合是否为空 */ boolean isEmpty(); /** * 是否包含某个元素 */ boolean contains(Object o); /** * 取迭代器 */ @Override Iterator<E> iterator(); /** * 转到数组 */ Object[] toArray(); /** * 转到指定数组 */ <T> T[] toArray(T[] a); // 修改操作 /** * 添加元素 */ boolean add(E e); /** * 移除元素 */ boolean remove(Object o); // 批量操作 /** * 是否全部包含 */ boolean containsAll(Collection<?> c); /** * 全部添加 */ boolean addAll(Collection<? extends E> c); /** * 全部移除 */ boolean removeAll(Collection<?> c); /** * 条件移除 */ default boolean removeIf(Predicate<? super E> filter) { Objects.requireNonNull(filter); boolean removed = false; final Iterator<E> each = iterator(); while (each.hasNext()) { if (filter.test(each.next())) { each.remove(); removed = true; } } return removed; } /** * 保留全部 */ boolean retainAll(Collection<?> c); /** * 清空 */ void clear(); // 比较和哈希 /** * 比较是否相等 */ boolean equals(Object o); /** * 取哈希值 */ int hashCode(); @Override default Spliterator<E> spliterator() { return Spliterators.spliterator(this, 0); } //流操作 default Stream<E> stream() { return StreamSupport.stream(spliterator(), false); } default Stream<E> parallelStream() { return StreamSupport.stream(spliterator(), true); } } 可以看出，Collection的操作还是蛮多的，增删该查和批量操作都有，至于迭代器是什么东西，后面的篇章会有详细介绍。最后两个方法涉及到了流操作，这是Java8里新添加的特性，关于流操作的知识，这里暂时不多说，以后在做讲解。通过本篇，你只需要了解一下集合是什么，为什么要有集合，集合家族的全貌，了解一下Collection接口中有哪些方法就足够了，之后的文章会从以下几方面来介绍容器家族： 1.Map接口 2.Iterable接口 3.List，Set，Queue接口 4.ArrayList使用方式和应用场景+源码剖析 5.HashSet使用方式和应用场景+源码剖析 6.LinkedList使用方式和应用场景+源码剖析 7.HashMap使用方式和应用场景+源码剖析今天的讲解就到此为止了，仅仅介绍了容器的基本概念，作为容器学习的开胃菜，后面一系列的文章都会围绕容器展开，希望大家继续关注！真正重要的东西，用眼睛是看不见的。

2018-05-17

Android应用开发提高系列（3）——《Effective Java 中文版》读书笔记

书籍《Effective Java 中文版》 03版潘爱民译本书介绍了57条极具实用价值的经验规则。这些经验规则涵盖了大多数开发人员每天所面临的问题的解决方案，通过对Java平台设计专家所使用的技术的全面描述，揭示了应坐什么和不应做什么，才能产生清晰、健壮和高效的代码。正文注意：条目和用语可能与书籍有所出入，但尽量保持原样加一些自己的理解。 1. 构造函数一定不能调用可被覆写的方法，无论是直接还是间接进行。 2. 接口应该只是被用来定义类型的，它们不应被用来导出常量。（备注：不要再接口中定义常量）P/89 3. 一个安全而保守的策略是，永远不要导出两个具有相同参数数目的重载方法。 4. 返回零长度的数组而不是null。 5. 嵌套类嵌套类(nested class)是指被定义在另一个类的内部的类，其存在的目的应该只是为它的外围类提供服务。嵌套类分为四种： 5.1 静态成员类(static member class) 最简单的嵌套类，最好把它看做一个普通的类。它可以访问外围类的所有成员，包括那些声明为私有的成员。与其他类静态成员一样，也遵守同样的可访问性规则。其通常用法是作为公有的辅助类，仅当与它外部类一起使用时才有意义。私有静态成员类的一种通常用法是用来代表外围类对象的组件。例如，Map实例的内部通常有一个Entry对象对应与Map中每一对键值对，虽然每一个Entry都与一个Map关联，但Entry上的方法(getKey、getValue、setValue)并不需要访问该Map。因此使用非静态成员来表示Entry是浪费的，私有静态成员类是最佳的选择。 5.2 非静态成员类(nonstatic member class) 非静态成员类的每一个实例都包含一个额外指向外部类对象的引用。维护这份引用要消耗时间和空间。其通常用法是定义一个Adapter，它允许外围类的一个实例被看做另一个不相关的类的实例。例如，Map接口的实现往往使用非静态成员类来实现它们的集合视图。 5.3 匿名类(anonymous class) 没有名字，它不是外围类的一个成员，在使用的同时被声明和实例化。可以出现在代码中任何允许表达式出现的地方。通常只实现了其接口中或超类中的方法，不会声明任何新的方法，它们应该非常简短。用法1 是创建一个函数对象(function object)，比如Comparator实例。例如： Arrays.sort(args, newComparator<String>(){ @Override public intcompare(Stringobj1,Stringobj2){ returnobj1.length()-obj2.length(); } }); 用法2 创建一个过程对象(process object)，比如Thread、Runable或者TimeTask实例。用法3 在一个静态工厂方法的内部，如： staticListintArrayList( final int[]a){ return newAbstractList<Integer>(){ @Override publicIntegerget( intlocation){ returna[location]; } @Override public intsize(){ returna.length; }}; } 用法4 在复杂的类型安全枚举类型中，用于公有的静态final域的初始化器中，例如： public abstract classOperation{ private finalStringname; Operation(Stringname){ this.name=name; } publicStringtoString(){ return this.name; } abstract doubleeval( doublex, doubley); public static finalOperationPLUS= newOperation("+"){ @Override doubleeval( doublex, doubley){ returnx+y; } }; } 5.4 局部类(local class) 使用最少，在任何“可以声明局部变量”的地方，都可以声明局部类，也遵守同样的作用域规则。与匿名类一样，它们必须非常简短。简而言之，如果一个嵌套类需要在单个方法之外仍然是可见的，或者它太长了，不适合放在一个方法内部，那么应该使用成员类。如果成员类的每个实例都需要一个指向其外围实例的引用，则把成员类做成非静态的；否则就做成静态的。假设一个嵌套类属于一个方法的内部，如果你只需要在一个地方创建它的实例，并且已经有了一个预先存放的类型可以说明这个类的特征，则把它做成匿名类；否则就做成局部类。 6. 了解和使用库应该熟悉java.lang、java.util以及java.io中的内容。 6.1 Random.nextInt(int) 产生随机整数。 6.2 Collections.sort(v) 字符串组成的Vector排序 6.3 Collections.sort(v, String.CASE_INSENSITIVE_ORDER) 字符串组成的Vector排序，忽略大小写 6.4 System.out.println(Arrays.asList(a)) 循环打印一个数组中所有的元素 6.5 获取两个Hashtable包含相同映射键值的所有键： Maptmp= newHashMap(h1); tmp.entrySet().retainAll(h2.entrySet()); Setresult=tmp.keySet(); 6.6 Arrays.toString(a) 打印数组每一个元素 6.7 Arrays.equals(a1, a2) 比较两个数组长度、每一个元素是否相等。 7. 使用异常 7.1 被检查的异常(checked exception) 通过抛出一个被检查的异常，强迫调用者在一个catch子句中处理异常，或者将它传播到外面。 7.2 运行时异常(run-time exception) 大多数的运行时异常都是指API的客户没有遵守API规范建立的约定。例如数组越界。总而言之，对于可恢复的条件，使用被检查的异常；对于程序错误，使用运行时异常。 8. 尽量使用标准的异常 8.1 IllegalArgumentException 调用者传递的参数不合适 8.2 NullPointException 空指针异常 8.3 IndexOutOfBoundsException 下标越界 8.4 ConcurrentModificationException 在禁止并发修改的情况下，对象检测到并发修改 8.5 UnsupportedOperationException 对象不支持所请求的方法结束由于先读的《Practical Java》，与本书内容有部分相似，所以看得比较快，仍然值得一读，也终于弄懂关于嵌套类这块的内容。本文转自over140 51CTO博客，原文链接：http://blog.51cto.com/over140/844926，如需转载请自行联系原作者

2017-11-21

用不可变的基础设施提高攻击者的攻击成本

本文讲的是用不可变的基础设施提高攻击者的攻击成本， Docker 容器的一个便捷之处在于它们是不可变的。

2017-10-17

云服务器 ECS 安全：如何提高ECS实例的安全性

如何提高ECS实例的安全性云服务器 ECS 实例是一个虚拟的计算环境，包含了 CPU、内存、操作系统、磁盘、带宽等最基础的服务器组件，是 ECS 提供给每个用户的操作实体。

2017-08-10

一种提高Android应用进程存活率新方法（上）

双service(通知栏) 提高进程优先级思路：(API level > 18 ) 应用启动时启动一个假的Service(FakeService), startForeground()，传一个空的

2017-08-02

资源下载

更多资源

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。

WebStorm

WebStorm 是jetbrains公司旗下一款JavaScript 开发工具。目前已经被广大中国JS开发者誉为“Web前端开发神器”、“最强大的HTML5编辑器”、“最智能的JavaScript IDE”等。与IntelliJ IDEA同源，继承了IntelliJ IDEA强大的JS部分的功能。