本书是对数据结构与算法的归档，正在撰写中，欢迎各位Star与PR

面向读者

有工作经验，不适用于应届生（应届生推荐直接读书）
已经有一定知识体系，但是希望达到Middle或者更高级别

为读者提供了

数据结构与算法，需要达到手写水平
常见眼高手低的误区
本书尽量给所有数据结构提供业界使用的示例（比如OkHttp内部为何使用了队列），而非画出一堆公式与框框

最终希望

白板手写各种结构与算法

技术交流

邮件: miao1007@gmail.com

license

本作品采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。

https://leetcode.com/problems/multiply-strings/

String

String本身不难，主要它作为可读编码，需要各种转换

单个计算的

转换为Hex，Integer，Array，特别是LeadingZero的定义可能不同: 这种问题说实话就是拼手速与用例，一般是Easy与Middle的难度。比如https://leetcode.com/problems/string-to-integer-atoi/
作为Tokenizer的输入源，实现简易的Inteceptor/Decoder，需要通过PatternMatch维护状态机（最简单的boolean到较为复杂的枚举），不同嵌套级别的ContextScope（比如Stack/Map），这个王垠比较在行

eg: https://leetcode.com/problems/decode-string/

需要对比的

与Regex混用（Greedy/DP）需要掌握表达式，比如 https://leetcode.com/problems/valid-parenthesis-string/，Kleene closure
Elastic搜索相关，比如编辑距离，共同拥有的某个特点，倒排索引，NGram等

Substing类型

排列组合，比如不能连续N个值，很容易转为数组类问题，滑动窗口等

常见问题

StringBuilder一个个append性能不如subString()
不熟悉的业务，不要上来就抽象出公共method

常见方法

// avoid for loop
String.join("|",Collections.emptyList());

// clear stringBuilder cache
sb.setLength(0);

// str <--> number
int n = 0;
for(int i = 0; i< s.length();i++){
  char c = s.charAt(i);
  if(Character.isDigit(c)){
  	n = n*10 + c - '0';
	}
}
// or Integer.valueOf(str)

// char <--> string
Character.toString('c');
"aaa".toCharArray();


// 高性能StringBuilder，用于冲top1 然而这里一般不是瓶颈,一般也就是8ms的差距
char[] arr = new char[SIZE];
int size = 0;
new String(Arrays.copyOfRange(sb,0,size));// size is excluded.

编辑距离

应用场景

Elastic中项目要用的真实例子: https://www.elastic.co/blog/found-fuzzy-search 模糊（Fuzzy）搜索以及拼写错误（Spell checker）
OJ例子: https://leetcode.com/problems/edit-distance/
更难的例子: https://leetcode.com/problems/regular-expression-matching/
Java业务: 通过EditDistance反射找到Bean（使用Common库实现）

理论教程

详见这个胶片 https://web.stanford.edu/class/cs124/lec/med.pdf

实现

本处实现是参考算法书中最通用的动态规划实现(其中replace复杂度为1)，与Elastic/Lucene等专业实现肯定还是有很大性能区别。还有值得注意的是，编辑距离不要求枚举所有的路线图，而只要求计算结果。如果需要保存路线，那么就相当于实现了一份Diff了

// https://leetcode.com/problems/edit-distance/

相比Fibonacci中使用Map作为缓存，由于EditDistance有两个入参，因此需要一个二维数组(cost array)来实现记忆化

cost[m][n]表示缓存了字符串word1前m个字符串与word2前n个字符串，从word1到word2的编辑距离

// 前N个含有0，因此需要加一
int[][] cost = new int[word1.length+1][word2.length+1];

比如现在有两个字符串，分别是 abcd 与 ccd，通过大脑计算显然可以看出需要删1换1，最终是2，我们现在用记忆化实现一下，我们将数组维护为一个Table，

首先完成边界起始迭代，由于是纯ADD/DEL操作，比如cost[3][0]表示将abc删成""，操作数当然是3

0	1(c)	2(c)	3(d)	4	5
1(a)
2(b)
3(c)
4(d)

这一部分可以用如下Java代码实现

// for word1 delete to word2
for (int i = 0; i< word1.length+1;i++){
  cost[i][0] = i;
}
// for word1 add to word2
for (int i = 0; i< word2.length+1;i++){
  cost[0][i] = i;
}

然后我们就可以基于预知条件，做一套从它的上面，左边与左对角线的迁移状态机，在上面的预制条件找最优解了

比如求值

cost[1][1]=distance('a','c')
- REPLACE: 由于a不等于c，因此成本是1
- delete_first: 先计算distance('','c') ，再计算 distance('','c') -> distance('a','c')，转换成本是1
- delele_second: 先计算distance('a','') ，再计算 distance('a','') -> distance('a','c')，转换成本是1
cost[1][2]=distance('a','cc')
- REPLACE: 由于a不等于c，因此成本是1
- delete_first: 先计算distance('','cc')，再计算 distance('','cc') -> distance('a','cc')，转换成本是1
- delele_second: 先计算distance('a','c') ，再计算 distance('a','c') -> distance('a','cc')，转换成本是1

这里代码如下

// calculate every transformation cost
for (int i = 1; i < len1 + 1; i++) {
  char c1 = word1.charAt(i - 1);
  for (int j = 1; j < len2 + 1; j++) {
    int swapCost = (c1 == word2.charAt(j - 1) ? 0 : 1);
    int delete_both_to_normal = cost[i - 1][j - 1] + swapCost;
    // 网上有很多用add作为命名，但是正如上文所写，状态转移最好命名长一点，避免歧义
    int delete_first_to_normal = cost[i][j - 1] + 1;
    int delele_second_to_normal = cost[i - 1][j] + 1;
    cost[i][j] = Math.min(
      Math.min(delete_first_to_normal, delele_second_to_normal), 
      delete_both_to_normal
    );
  }
}
return [i][j];

白板注意事项

不要写过长代码(eg: Math.min)，防止括号中加一位置计算错误，难以定位
二维数组尽量直接操作index，不要用arr.length
string的length方法有括号

literal-expression interceptor

背景

String作为表达式的输入源，实现简易的Interceptor/Decoder，需要通过PatternMatch维护状态机（比如栈），不同嵌套级别的ContextScope（比如Stack/Map），难度一般为Middle到Hard

比如

只涉及长度位置的问题，连Lexer都不用使用（Middle）
实现Tokenizer（用2个while）
实现一个计算器/Encoder/Decoder（Middle～Hard）(涉及乘法优先级的太恶心，我是不会搞的，反正这种公司也不去)
实现一个OGNL，模版引擎（支持，取属性与$取）（Hard）
支持赋值与函数的Lisp表达式处理器（ READ/EVAL/PRINT LOOP，Very Hard），可以参考Clojure的LispReader(注意它解析后S-Exp是放在表达式上下文运行的)

其中hard的占总hard的15%，很多问题是披着String的外表，内部却干着（简易）编译器的活。

常见解析流程

前三种问题均可以由下面流程搞定，注意，由于题目一般都是理想情况，因此为了时间并没有使用AST的DFS，仍然是String的startWith处理PatternMatch

步骤如下

初始化

如果涉及到env，进行Runtime的init

Atomic处理

对于无法拆分的Atomic元素（比如int/boolean/symbol，注意这里不是最小的表达式），直接解析运算，并写好用例

表达式处理

对于表达式（比如某种括号/数字开头），需要扫描两次

切分表达式

第一遍扫描（delimeter）：此处对括号split，不含嵌套（遇到多个括号嵌套时，不处理，直接append进去）。举个例子，比如计算器

(+ (* 2 (+ 6 7)) (* 4 5))

我将解析为如下，注意保留了括号，这里本质上是一个退化的链表

['+', '* 2 3 (+ 6 7)', '* 4 5']

而不是AST的树形结构

['+', ['*', '2', '3', ['+', '6', '7']], ['*','4', '5']]

如果你看过Clojure的实现，比如执行(let x 2 x)时，它将在Java侧通过LispReader解析为List表达式，后续步骤将在Clojure的Runtime进行invoke，而不是把工作全部扔到了Reader中，这样做当然是最工程化的；而如果你是在做题时，如果通过嵌套List，那么类型强制转换、Symbol状态保存、env与String的编码将比较繁琐，因此我个人建议通过保留括号String而不是维护嵌套List

执行表达式

第二遍扫描（eval）：通过匹配startWith（使用下面的readInt与readLetter等工具实现，没有转为单独的Tree，没有达到Parser的级别）实现DFA，并根据表达式进行eval（递归/Stack ，复杂度为N!）

这里扫描两次并不会太慢，因为如果只扫描一遍就全部搞定的话，需要维护很多全局变量与If判断（而且很难总结为经验），即通过很多goto语句实现DFA与AST，也就是所谓的意大利面式代码，导致调试中的index位置非常复杂。同时，由于你经常通过两次扫描进行训练，可以更专注在核心eval上，而不是反复折腾全局变量，真正白板时，对bugfree要求还是很高的。

例子

我们挑一个中等的题目，要求如下

https://leetcode.com/problems/number-of-atoms/

解决方法就是构造DFA遍历执行

附录

表达式到底扫描几遍

王垠曾经说过，在TOKEN扫描的时候不要为了节约遍历而做Parse/eval的工作，否则额外的判断与全局变量等问题会提高复杂度，我个人也赞成垠神的说法，因为这类问题一般不会有性能问题，N与2N不会太大。

此外，如果是为了做题/最小复杂度，那么尽可能不形成AST，而是直接保存split后的String，因为时间可能不够。

使用栈还是递归

用递归代码简洁优雅，不用维护额外的栈，时间性能可以达到Top1%；但是技巧性较高，不好记住，涉及到缓存时代码也不简单。

使用Deque：工程最常用，模版可以背，可以轻易颠倒顺序。如果为了性能可以维护一个array based stack。

要不要使用正则表达式

虽然使用此工具匹配很快，但是不推荐平时使用，因为套路还是以手动匹配为主

手写DFA常见工具类

下面两个可以实现返回多个值，完全通用各种场景

// array x is to fix immutable primary type
// x 的管理也由上游控制
int readDigit(String s, int i, int[] x){
    int n = s.charAt(i) - '0';
    while(i + 1 < s.length() && Character.isDigit(s.charAt(i+1))){
       n = n*10 + s.charAt(i+1) - '0';
       i++;
    }
  	x[0] = n;
    return i;
}

// StringBuilder是为了方便上游滑动窗口等复用， sb的释放由上游负责
public int readLetter(String s, int i, StringBuilder sb){
    sb.append(s.charAt(i));
    while(i+1 < s.length() && Character.isLetter(s.charAt(i+1)) ){
        sb.append(s.charAt(i+1));
        i++;
    }
    return i;
}

// usage，非常优雅，没有任何if是多余的
for(int i = 0;i<s.length();i++){
  char c = s.charAt(i);
  if(Character.isDigit(c)){
    int[] num = new int[1];
    i = readDigit(s, i, num);
  } else if(Character.isLetter(c)){
    i = readLetter(s, i, sb);
  }
}

除了手写，还有正则表达式匹配，但是感觉失去了本质

相似字符串

组合相似
符合某个规则（isomorphic）

这类问题一般是是

维护一个pair（或者称作Entry/Tuple）
hashCode相等，或者内部相减
sliding window来进行遍历计算

读题与测试用例

读好英文，准备明确的测试用例

比如这一个 https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

就一定要明确abc可以，但是abbc是不可以的

有些题目就是这么low，只能靠用例补充

以下要求阅读过源码或者有输出

Map的各种实现

Java的HashMap源码实现，特别注意当冲突达到7时，变化为红黑树的操作
Zk中为何使用ConcurrentHashMap作为树
Redis的HashTable的实现，渐进式rehash实现
SLB中一致性Hash算法
布隆过滤器
LRU算法中的LinkedHashMap
JDK8/Groovy集合类中groupBy

WeakHashMap

WeakReference相比SoftReference，无论是否OOM，都会被GC。因此可以配合Map做缓存

动态代理/反射中的缓存
大对象/容易再次生成的对象

HashMap的优化与实践

文章速读

HashMap通过计算哈希实现数据的索引
当碰撞达到8时，将链表转为红黑树(一种对称的二叉查找树)
HashMap进行rehash时性能较差，因此需要设计一个好的容量，或者使用Redis的渐进式rehash

HashMap的复杂度

如图是ArrayList/LinkedList/HashMap三个数据结构的复杂度对比，可以看出HashMap整体上性能都非常不错，但是不稳定，为O(N/Buckets)，N就是以数组中没有发生碰撞的元素，Buckets是因碰撞产生的链表。

获取	查找	添加/删除	空间
ArrayList	O(1)	O(1)	O(N)	O(N)
LinkedList	O(N)	O(N)	O(1)	O(N)
HashMap	O(N/Bucket_size)	O(N/Bucket_size)	O(N/Bucket_size)	O(N)

注：发生碰撞实际上是非常稀少的，所以N/Bucket_size约等于1

HashMap是对Array与Link的折衷处理，Array与Link可以说是两个速度方向的极端，Array注重于数据的获取，而处理修改（添加/删除）的效率非常低；Link由于是每个对象都保持着下一个对象的指针，查找某个数据需要遍历之前所有的数据，所以效率比较低，而在修改操作中比较快。

复杂度是如何考察的？

对于数据结构，在时间上我们需要考察Acessing ,Search, Deletion/Insertion的平均与最差的复杂度。在空间上，我们要考虑维护这个数据结构所占用的内存空间。

常见的数据结构与排序的复杂度都在这里

HashMap的实现

本文以JDK8的API实现进行分析

1. 什么是hash，什么是碰撞？

Hash：是一种信息摘要算法，一般用于验证完整性，它还叫做哈希，或者散列，但是它不是加密。我们平时使用的MD5,SHA1,SSL中的公私钥验证都属于Hash算法，通过输入key进行Hash计算，就可以获取key的HashCode()，比如我们通过校验MD5来验证文件的完整性。
碰撞：好的Hash算法可以出计算几乎出独一无二的HashCode，如果出现了重复的hashCode，就称作碰撞;

就算是MD5这样优秀的算法也会发生碰撞，即两个不同的key也有可能生成相同的MD5。

2. HashMap中是如何实现写入与读取的？

HashMap实现了Map接口，保存着K-V这样的集合。我们以put操作为例

2.1. 对key进行Hash计算

在JDK8中，由于使用了红黑树来处理大的链表开销，所以hash这边可以更加省力了，只用计算hashCode并移动到低位就可以了

static final int hash(Object key) {
    int h;
    //计算hashCode，并无符号移动到低位
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

举个例子: 363771819^(363771819 >>> 16)

0001 0101 1010 1110 1011 0111 1010 1011(363771819)
0000 0000 0000 0000 0001 0101 1010 1110(5550) XOR
--------------------------------------- =
0001 0101 1010 1110 1010 0010 0000 0101(363766277)

这样做可以实现了高地位更加均匀地混到一起，详见这里

下面给出几个常用的哈希码(hashCode)的算法。

Object类的hashCode. 返回对象的经过处理后的内存地址，由于每个对象的内存地址都不一样，所以哈希码也不一样。这个是native方法，取决于JVM的内部设计，一般是某种C地址的偏移。
String类的hashCode. 根据String类包含的字符串的内容，根据一种特殊算法返回哈希码，只要字符串的内容相同，返回的哈希码也相同。
Integer等包装类，返回的哈希码就是Integer对象里所包含的那个整数的数值，例如Integer i1=new Integer(100),i1.hashCode的值就是100 。由此可见，2个一样大小的Integer对象，返回的哈希码也一样。
int，char这样的基础类，它们不需要hashCode，如果需要存储时，将进行自动装箱操作，计算方法同上。

2.2. 获取到当前的位置

计算了Hash，我们现在要把它插入数组中了

i = (tab.length - 1) & hash；

通过位运算，确定了当前的位置，因为HashMap数组的大小总是2^n，所以实际的运算就是 (0xfff...ff) & hash ，这里的tab.length-1相当于一个mask，滤掉了大于当前长度位的hash，使每个i都能插入到数组中。

2.3. 生成包装类

这个对象是一个包装类，Node<K,V>，内部有key,value,hash还有next，可以看出来它是一个链表。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        //getter and setter .etc.
}

2.4. 插入包装类到数组

(1). 如果输入当前的位置是空的，就插进去，如图，左为插入前，右为插入后

0           0
|           |
1 -> null   1 - > null
|           |
2 -> null   2 - > null
|           | 
..-> null   ..- > null
|           | 
i -> null   i - > new node
|           |
n -> null   n - > null

(2). 如果当前位置已经有了node，且它们发生了碰撞，则新的放到前面，旧的放到后面，这叫做链地址法处理冲突。

0           0
|           |
1 -> null   1 - > null
|           |
2 -> null   2 - > null
|           | 
..-> null   ..- > null
|           | 
i -> old    i - > new - > old
|           |
n -> null   n - > null

我们可以发现，失败的hashCode算法会导致HashMap的性能由数组下降为链表，所以想要避免发生碰撞，就要提高hashCode结果的均匀性。当然，在JDK8中，采用了红黑二叉树进行了处理，这个我们后面详细介绍。

什么是Hash攻击?

通过请求大量key不同，但是hashCode相同的数据，让HashMap不断发生碰撞，硬生生的变成了SingleLinkedList
0
|
1 -> a ->b -> c -> d(撞！撞！撞！复杂度由O(1)变成了O(N))
|
2 -> null(本应该均匀分布，这里却是空的)
|
3 -> null
|
4 -> null
这样put/get性能就从O(1)变成了O(N)，CPU负载呈直线上升，形成了放大版DDOS的效果，这种方式就叫做hash攻击。在Java8中通过使用TreeMap，提升了处理性能，可以一定程度的防御Hash攻击。

3. 扩容

如果当表中的75%已经被占用，即视为需要扩容了

(threshold = capacity * load factor ) < size

它主要有两个步骤：

1. 容量加倍

左移1位，就是扩大到两倍，用位运算取代了乘法运算

newCap = oldCap << 1;
newThr = oldThr << 1;

2. 遍历计算Hash

for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //如果发现当前有Bucket
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //如果这里没有碰撞
                    if (e.next == null)
                        //重新计算Hash，分配位置
                        newTab[e.hash & (newCap - 1)] = e;
                    //这个见下面的新特性介绍，如果是树，就填入树
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //如果是链表，就保留顺序....目前就看懂这点
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }

由此可以看出扩容需要遍历并重新赋值，成本非常高，所以选择一个好的初始容量非常重要。

如何提升性能？

解决扩容损失：如果知道大致需要的容量，把初始容量设置好以解决扩容损失；
比如我现在有1000个数据，需要 1000/0.75 = 1333 个坑位，又 1024 < 1333 < 2048，所以最好使用2048作为初始容量。
解决碰撞损失：使用高效的HashCode与loadFactor，这个...由于JDK8的高性能出现，这儿问题也不大了。
解决数据结构选择的错误：在大型的数据与搜索中考虑使用别的结构比如TreeMap，这个就是知识积累了。一般需要key排序时，建议使用TreeMap，本文暂不讨论；

HashMap与HashTable的主要区别

在很多的Java基础书上都已经说过了，他们的主要区别其实就是Table全局加了线程同步保护

HashTable线程更加安全，代价就是因为它粗暴的添加了this同步锁，所以会有性能损失。
其实有更好的concurrentHashMap可以替代HashTable，它采用了CAS实现了数组元素的插入

JDK8中HashMap的新特性

如果某个桶中的链表记录过大的话（当前是TREEIFY_THRESHOLD = 8），就会把这个链动态变成红黑二叉树，使查询最差复杂度由O(N)变成了O(logN)。

//e 为临时变量，p为当前的链
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;
}

JDK8在其他地方也有提升，更多的可以看这里。

HashMap的装箱空间效率

在笔试题中，一般“内存限制”是不考虑装箱的，而在现实中HashMap空间效率之低，你却不一定知道。

比如定义了一个 HashMap<Long,Long>

1. Long的装箱

在对象头中，加入额外的指针8Bype，加入8Bype的MarkWord(hashcode与锁信息)，这里就是16Byte

也就是说，long在装箱后，效率为 8/24 = 1/3

2. Map.Entry的装箱

字段空间: hash(4) + padding(4) ＋ next(8) = 16Byte，这里的padding是字节对齐

对象头: 16Byte，指针+MarkWord

也就是说，维护一个Entry需要32Byte的空间

static class Node<K,V> implements Map.Entry<K,V>
{    
    final int hash;    
    final K key;    
    V value;    
    Node<K,V> next;
}

3. 总效率

8/(24 + 32) = 1/7

计算结果可能有差异，本文主要在强调装箱过程造成的损失

如果你想挑战OJ的TOP1，必须通过数组等手段实现Map

ConcurrentHashMap与HashTable

ConcurrentHashMap通过CAS锁实现，使用了synchonized(node)搜索链表，只有输入操作有锁，输出操作无锁
HashTable通过synchronized方法实现，也就是用this作为锁，粒度过大

ConcurrentHashMap在开源项目的使用

Mybatis中执行动态SQL时缓存表达式(expressionCache)

CopyOnWriteHashMap在开源项目的使用

zk中的zkNode节点
tomcat中的ApplicationContext，即request.getServletContext().getAttribute("key")

Guava中的LocalCache

CopyonWritMap(zk)

##1. Cache的简介

缓存，顾名思义，也就是方便用户快速的获取值的一种储存方式。小到与CPU同频的昂贵的缓存颗粒，内存，硬盘，网络，CDN反代缓存，DNS递归查询，OS页面置换，Redis数据库，都可以看作缓存。它有如下的特点：

缓存载体与持久载体总是相对的，容量远远小于持久容量，成本高于持久容量，速度高于持久容量。比如硬盘与网络，目前主流的SSD硬盘可以达到1000MB/S，而很多地区网速却只有4M，将网络中的文件存到硬盘中，硬盘就相当于缓存；再比如内存与硬盘，主流的DDR3内存的速度可以达到10GB/S，而硬盘相对的慢了很多数量级别，将硬盘的游戏加载到内存，内存就相对于硬盘是一种缓存。
需要实现排序依据，在java中，可以使用Comparable<T>作为排序的的接口
需要一种页面置换算法(page replacement algorithm)将旧页面去掉换成新的页面，如最久未使用算法（LFU）、先进先出算法（FIFO）、最近最少使用算法（LFU）、非最近使用算法（NMRU）等
如果没有命中缓存，就需要从原始地址获取，这个步骤叫做“回源”，CDN厂商会标注“回源率”作为卖点

Comparable<T>是java用来排序的接口，推荐参考阅读《Java Software Structures Designing and Using Data Structures》

页面置换算法可以参考阅读《现代操作系统》的中译本

##2. LinkedHashMap原理

###2.1. 源码概述分析

在HashMap中，维护了一个Node<K,V>[] table，当put操作时，将元素按照计算出的Hash填到数组相应位置table[Hash]中，最后迭代时，从table[0]开始向后迭代，具体的顺序取决于元素的HashCode，所以我们常说HashMap的元素迭代是不可预测的。

而在LinkedHashMap中，除了Node<K,V>[] table，还维护着2个Entry<K,V> head,tail，并组成了链表。当put元素后，调用下列回调函数对链表将元素移动到链尾以及清理旧的元素

// move node to last
void afterNodeAccess(Node<K,V> e)
// possibly remove eldest
void afterNodeInsertion(boolean evict)

在get元素时，如果设置accessOrder为true时，通过调用如下回调移动元素到链尾，这里特别强调移动，如果这个元素本身已经在链表中，那它将只会移动，而不是新建

// move node to last
void afterNodeAccess(Node<K,V> e)

综上，当你反复对元素进行get/put操作时，经常使用的元素会被移动到tail中，而长期不用的元素会被移动到head

最后迭代(Iterator)时，迭代是从旧元素迭代到新元素，这就是LRU的实现

head <--> .... <--> tail

旧元素 <-----------> 反复使用的新元素

对LinkedHashMap进行了封装实现LRU的框架，基本上是按照下图的方法进行初始化

//按照访问顺序排序的Map，设置accessOrder为true
map = new LinkedHashMap<>(0, 0.75f, true);

###2.2. HashMap的对比

以下是常见的3种map的区别，以下均不计算扩容时的时间复杂度

	HashMap	LinkedHashMap	TreeMap
Performance get/set	O(1)	O(1)	O(logN)
Implement	Array	Link + Array	Red-Black Tree
Iteration	unpredictable	put/accessOrder	Comparable`<Key>`

上述具体代码没有源码分析哦

本部分基于JDK1.8.0_05，可能部分函数与网上文章相冲突

在golang中，使用ring与map实现了Lru，可以看这里

在树这一章中，我建议先学习LISP，学会用表结构与模式匹配后，再研究树，比Java代码表达能力强多了

以下至少要能够说清楚

编程语言中的抽象语法树(AST)
通信中的Haffman编码(实现总权最小)
Drools等规则引擎(RuleEngine)中的RETE算法(实现总叶子最小)
数据库中的B+Tree与LSM Tree
倒排索引(Inverted index)
文本匹配中的双数组Trie算法
优先队列

定义

see here https://www.wikiwand.com/en/Binary_tree#/Types_of_binary_trees

@startmindmap
skinparam shadowing false
+ Binary Tree
++ Heap
+++ Max-Heap\n t>=t.l && t>=t.r
+++ Min-Heap\n t<=t.l && t<=t.r
++++ PriorityQueue\n 
++ Complete tree\n filled left to right
++ Height-balance tree\n Abs(t.l - t.r)<=1
++ Binary search tree\n t.l<=t<=t.r
@endmindmap

遍历

pre

void traverse(TreeNode root) {
  <pre order code>
  traverse(root.left)
  traverse(root.right)
}

void traverse(TreeNode root) {
  traverse(root.left)
  <in order code>
  traverse(root.right)
}

after

void traverse(TreeNode root) {
  traverse(root.left)
  traverse(root.right)
  <after order code>}

Traverse

Depth-First

深度遍历是最常见的场景，本质上也是进行模式匹配

二叉树的深度遍历，方便进行直观理解

思路与其他遍历一样，先解决Atomic特例，再遍历

; racket draw Binary Tree
#lang racket
; 导入绘图工具类
(require pict pict/tree-layout)
; 判断Token是否是单个元素
(define (atom? x) (not (or (pair? x) (null? x))))
; 定义一个名为gen-ast,入参为exp的函数
(define gen-ast
  (λ (exp)
    (match exp
      [(? atom? leaf)   ;如果为叶子
       (tree-layout #:pict (text (~v leaf)))] 
      [`(,op,l,r)        ;对S表达式进行遍历
       (let ([v1 (gen-ast l)]
             [v2 (gen-ast r)])
         (tree-layout #:pict (text (~v op)) v1 v2))])))
; 将生成的 tree-layout 赋值到 tree 变量
(define tree (gen-ast `(+ 1 (+ (* 2 5) (/ 2 4)))))
; 执行绘图
(naive-layered tree)

生成的结果是这样的

Breed-First

二叉树

什么是BinaryTree

有最多两个叶子的就是二叉树，与它的大小，排序无关

红黑树

以下摘自百科

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

节点是红色或黑色。
根是黑色。
所有叶子都是黑色（叶子是NIL节点）。
每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

下面是一个具体的红黑树的图例：

TreeMap

最优二叉树: 通信领域中的Huffman编码

树这个数据结构一直是我的弱项。其实最开始接触树是通信领域中的Huffman编码+奇怪的数学符号，直接对树吓出了阴影。

之前写过HashMap分析文章，它是通过Obeject的equals与hashcode进行放入与查询的。HashMap内部通过数组进行存储，Index基于Hash值，由于hash算法的“随机”均匀性，因此，如果对KeySet进行遍历的话，将是不可预料的。

而TreeMap基于树，准确的说是基于红黑树实现了Map接口。

Huffman的思想在很多场景都有遇到过，比如在Switch/Case/If条件链中，概率高的条件放到前面，程序的执行会更快。

基础知识复习

树的定义

树是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树

上面定义可以看出，树不一定有2个Child，也不是父与子、兄弟一定要满足特定的大小关系

u5Y-gzU-CmQ-nge

堆的定义

n个元素序列{k1,k2...ki...kn},当且仅当满足下列关系时称之为堆： (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

这种数据结构具有以下性质。

任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入

这里也没有说一定是二叉堆，但是平时一般说堆都是特指二叉堆

TreeMap、TreeSet、HashMap 与 PriorityQueue 的对比

计算TopN

参考

TreeSet

去重(unique)

["222","111",'33','44','44'].unique()
=> ["222","111",'33','44']

这里用TreeSet可以将它实现

def unique = { List list->
    TreeSet set = new TreeSet()
    set.addAll(list)
    return set.toList()
}

其中TreeSet内部addAll通过for循环调用treeMap实现

list.each{e->
    //If the map previously contained a mapping for the key, the old value is replaced.
    treeMap.put(e, PRESENT)
}

Pool

池虽然不是名义上的数据结构，但是它一般通过Map实现

CommonPool的源码实现，JedisPool中Socket连接池实现
OkHttp中Socket连接池源码实现
ThreadPool(线程池)的源码实现
RxJava(Reactive式操作)的SchedulerPoolFactory实现
数据库连接池实现(了解)

Double Queue(双端队列)

特点

ArrayDeque

基于数组，本质上是一个SlidingWindow，性能比LinkedList或者树性能更强。`

// push A B C into deque
value                A B C
index head(min) 1 2  . . .  tail(max)

录入

分别作为Stack与Quque

addFirst: push
addLast: offer, add

迭代

与数组一样，从head开始到tail，满足栈的先进后出与队列的先进先出。

此外还有双端链表LinkedList，请在其它章节进行了解。

OkHttp内部请求队列实现

(本部分基于git checkout tags/parent-3.9.1版本分析)

在okhttp内部，采用了ArrayDeque实现请求的排队，它主要有如下两个对象

AsyncCall extend NamedRunnable: 对Runnable的封装，非HTTP请求
RealCall extend Call: 真正的HTTP请求

同步请求场景

同步请求是按照顺序阻塞调用的，内部维护了排队队列

// 线程不安全，但是入队与出队加了synchronized锁，自动扩容
private final Deque<RealCall> runningSyncCalls = new ArrayDeque<>();

请求侧如下

// okhttp3.RealCall#execute
 try {
 	 //　enque the element to tail
   client.dispatcher().executed(this);
   // blocking IO works
   Response result = getResponseWithInterceptorChain();
   if (result == null) throw new IOException("Canceled");
   return result;
 } catch (IOException e) {
   eventListener.callFailed(this, e);
   throw e;
 } finally {
   // poll the head element: 注意它是head元素，删除的不一定是刚刚入队的this
   client.dispatcher().finished(this);
 }

同步队列主要用于多个线程阻塞调用OkHttp时Call的引用计数，方便某些场景下执行cancelAll，事实上把这个Queue删除，同步请求也照样能使用的。

异步请求场景

异步请求中维护了两个Runnable队列，虽然Deque可以自动扩容，但是下面通过外置条件控制了running状态，注意异步请求中由于readyAsyncCalls不一定是排序，当某个Host请求多后，少的Host会优先。

/** Ready async calls in the order they'll be run. */
private final Deque<AsyncCall> readyAsyncCalls = new ArrayDeque<>();
/** Running asynchronous calls. Includes canceled calls that haven't finished yet. */
private final Deque<AsyncCall> runningAsyncCalls = new ArrayDeque<>();

入队实现如下

synchronized void enqueue(AsyncCall call) {
  // 某些并行MAX条件
 	if (runningAsyncCalls.size() < maxRequests && runningCallsForHost(call) < maxRequestsPerHost) {
 	  runningAsyncCalls.add(call);
    // 执行 AsyncCall.run()
    // 它的finally中也会执行 finished(runningAsyncCalls, call, true); 进行出队
    // 因此当请求没有达到并行MAX条件时，与阻塞调用类似
 	  executorService().execute(call);
 	} else {
    // 我们只分析这里
 	  readyAsyncCalls.add(call);
 	}
 }

当请求达到了并行MAX条件时，就会涉及排队了。当某个请求完成后，将调用finished

// okhttp3.Dispatcher#finished(java.util.Deque<T>, T, boolean)
// 通过同步锁实现控制两个队列的原子操作
synchronized (this) {
  // 将运行的队列移除，由于是异步，这里**并非**移动的是第一个元素，而是最差N次循环数组才能找
  if (!calls.remove(call)) throw new AssertionError("Call wasn't in-flight!");
  // 通过判断MAX条件，for循环查找尽可能将 readyAsyncCalls 移动到 runningCalls
  promoteCalls();
  runningCallsCount = runningCallsCount();
}

值得注意的是，readyAsyncCalls并不是完全按照先进先出实现排序，而是外部包装了maxRequestsPerHost判断，因此同样是排队，Host少的就是比Host的快，同时PerHost还保持着排序

声明：网上的OkHttp3源码分析【任务队列】 是我以前写的，但是有疏漏（这里并不是移动ready的tail到running的head，而是N次查找），所以我全删了，网上未经授权抄的我救不了啦，要有批判思维。

我们可以参考这些思路去做自己的多参数场景（比如MQ基于IP分发），实现比优先队列更加灵活的排队调度

OJ题目: cooling interval

https://leetcode.com/problems/task-scheduler/

优先队列

优先队列基于堆(Heap)，是一种通过优先级进行调度的策略。在输入元素时，将通过Comparable实现优先级的对比，进而实现按照优先级“插队”的调度，举个例子

Picasso在加载图片时内部的线程池使用了优先队列进行线程的调度，进而实现多个不同图片优先级的显示（这里通过优先队列实现了OkHttp的网络请求）。更广泛地说，只要涉及到调度策略，肯定要与优先队列有关系。
MQ中间件: 在后台的订单派发、抢购活动中，基本上都涉及到MQ的优先级
同样在笔试中，用于解决TopK问题

为了简化目标，本文仅分析JDK(基于1.8.0_101)下 PriorityQueue 的入队与出队操作。

什么是优先队列？

优先队列(PriorityQueue)由堆(heap)构成，即一个完全二叉树，在本文中，子(child)节点总是小于父(parent)节点。

     2
 3      5
5 7   6

`(3 `(3 5 7) `(5 6))

在JDK实现的PriorityQueue中，当输入元素时，首先将元素放到最下层的叶节点（数组的末尾），接着从叶节点向上爬，并取代比它小的元素；当移除元素时，首先移除最高的根节点，然后下面向上填坑，由下面的小元素将它取而代之。

“堆”密度大的沉在下面，密度小的飘到上面。

HEAP与BST的区别

假设这是一个树``(p l r)`

BST需要保证 l < p < r
而Heap需要保证 p < (or l r)，同级的排序不涉及，因此设计与插入维护更加简单

入队操作

入队是最常见的操作，将数据放到堆的末端叶子，一般用于生产者，比如将一个含优先级的请求放入线程池，必须实现Comparable或者Comparator接口。源代码如下

//添加元素到队尾
public boolean offer(E e) {
  if (e == null)
    throw new NullPointerException();
  modCount++;
  int i = size;
  //如果需要扩容
  if (i >= queue.length)
    // 通过System.arraycopy 扩容加一
    grow(i + 1);
  size = i + 1;
  if (i == 0)
    queue[0] = e;
  els
    siftUp(i, e);
  return true;
}

在siftUp中代码如下，通过此处可以看出，JDK中默认采用的是小堆(Heaps where the parent key is less than the child keys are called min-heaps)，也就是堆顶(queue[0])是数组中最小的值，接着调用了 siftUp 方法进行“升迁”排序，具体实现如下

//如果小于Parent，就替换掉它
//k: queue.size();
//E: Data to insert
private void siftUpComparable(int k, E x) {
  Comparable<? super E> key = (Comparable<? super E>) x;
  // 首与parent对比，如果比它小或等，就替换掉。
  while (k > 0) {
    int parent = (k - 1) >>> 1;//也就是 除以2
    Object e = queue[parent];
    if (key.compareTo((E) e) >= 0)
      break;
    queue[k] = e;
    k = parent;
  }
  queue[k] = key;
}

举个例子，比如我要依次插入[6,3,7,9,2,1]，Scheme代码如下

(offer () 6) = (6 nil nil)
(offer (6) 3) = (3 6 nil)
(offer (3 6) 7) = (3 6 7)
(offer (3 6 7) 9) = (3 (2 9 nil) 7)
(offer (3 (6 9 nil) 7) 2) = (2 (3 9 6) 7)
(offer (2 (3 9 6) 7) 1) = (1 (3 9 6) (2 7 nil))

从上面的例子可以看出，第一个元素，也就是根节点总是最小的值，这个sitfup也就是插队的流程。

这里也可以看出，优先队列内部并不是全量依次排序的

提取元素

此场景在消费者中经常使用，从堆顶中拿出最小的元素，空缺位置从下向上依此提拔。

public E poll() {
  if (size == 0)
    return null;
  int s = --size;
  modCount++;
  //队首最小的元素
  E result = queue[0];
  //队尾元素
  E x = queue[s];
  queue[s] = null;
  if (s != 0)
    //开始内部替换，并取而代之queue[0]
    siftDown(0, x);
  return result;
}

具体套路是这样的

//k=0 x=leaf, 
private void siftDownComparable(int k, E x) {
  int half = size >>> 1;        // loop while a non-leaf
  //不断向下
  while (k < half) {
    // getSmallerChild start
    int child = (k << 1) + 1; // assume left child is least
    E c = queue[child];
    int right = child + 1;
    if (right < size && c.compareTo(queue[right]) > 0){
      c = queue[child = right];      
    }
    // getSmallerChild end
    if (x.compareTo(c) <= 0)
      break;
    queue[k] = c;
    k = child;
  }
  queue[k] = x;
}

总之，这个与公司的职级晋升很像。

优先队列的迭代

优先队列的默认实现是数组从左到右边依此输出，等价于树(从左到右的)广度遍历BFS，但是由于左右叶子没有规范大小，因此输出是毫无意义的。唯一有意义的就是最小值queue[0]，因此如果需要排序结果，那么只能用循环实现，而且还只能从小到大（或者像下面这样从0插入）。

//descending order
public <T, R> List<R> itrQueueDesc(Queue<T> queue, Function<T, R> function) {
  List<R> list = new ArrayList<>(); //array runs faster than the link in LeetCode, haha
  while (!queue.isEmpty()) {
    T poll = queue.poll();
    list.add(0, function.apply(poll));
  }
  return list;
}

toString 也是同理，没有输出意义

OJ的TopK例子

维护一个固定长度为K的队列，时间复杂度为logN，占用内存为N

//215. Kth Largest Element in an Array https://leetcode.com/problems/kth-largest-element-in-an-array/
public <T> Queue<T> fixedQueue(Collection<T> ts, int k, Comparator<T> comparator) {
  Queue<T> queue = new PriorityQueue<>(k, comparator);
  for (T t : ts) {
    // 此处有判断size再插入的方法，但是性能差距不大
    queue.add(t);
    if (queue.size() > k) {
      queue.poll();
    }
  }
  return queue;
}

OJ的WordFreq问题

词频统计(CountBy)，先GroupBy，后TopN，注意这个与Elastic的InvertedIndex是没有关系的

// 688. https://leetcode.com/problems/top-k-frequent-words
public List<String> topKFrequent(String[] words, int k) {
  // count by 
  // 此部分在Eureka的一致性Hash中也有出现，用于校验增量更新，比如UP_3_DOWN_2
  Map<String, Long> collect = new HashMap<>();
  for (String w : words) {
    collect.put(w, collect.getOrDefault(w, 0l) + 1);
  }
  Queue<Map.Entry<String, Long>> queue = fixedQueue(collect.entrySet(), k, 
    (newVal, oldVal) -> {
      //  from highest to lowest
      int i = newVal.getValue().compareTo(oldVal.getValue());
      if (i == 0) {
        return oldVal.getKey().compareTo(newVal.getKey()); //lower alphabetical comes first
      }
      return i;
  });
  return itrQueueDesc(queue, Map.Entry::getKey);
}

此外还有基于Redis的ZSET的实现

数组与链表的区别

在内存上，数组是连续地址，而链表是离散地址；数组通过下标定位，而链表只能通过指针定位；

||get(index)|contain(obj)|add/remove(index,obj)|空间|| |: |ArrayList |O(1)| O(N)|O(N) | O(N)| |LinkedList | O(N) | O(N) |O(1)* |O(N)

这里的get可以用“定位/index”翻译，而contain可以翻译为“查找/Search”，两者翻译不可混为一谈;

add/remove这里有争议，特指已经查找到了元素位置的情况下，移动数据所需要的时间;

不考虑第一与最后位的特殊情况

####1. 定位（get(index)）

数组通过下标进行定位

 E elementData(int index) {
        return (E) elementData[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;
        }
    }

####2. 搜索（contain(obj)）

在数组中，contain实际上就是indexof，因为需要遍历查表对比，所以复杂度都是O(N)

public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -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;
    }

####3. 添加或删除(add/remove(index,obj))

在数组中，插入元素需要调整后面的所有元素，所以消耗比较多，我们以add为例，可以看出，是先复制后添加的，复杂度为O(N)；

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //使用native代码以提高效率
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

而在链表中，add时间为{定位时间 + O(1)}，我们平时说的添加删除的复杂度O(1)是指已经获得当前定位的情况，在stackoverFlow上也有关于这个的讨论，你要说到底我支不支持O(1)呢，那我当然支持了，毕竟都是那么写的嘛

public void add(int index, E element) {
        checkPositionIndex(index);
		
        if (index == size)
            linkLast(element);
        else
            //这里node()定位的复杂度已经是O(N)了，但是我们不考虑
            linkBefore(element, node(index));
    }
    
/**
 * Inserts element e before non-null Node succ.
 * 这里的元素数据复杂度为O(1)
 */
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++;
}

4. 总结

总得来说，就是Array定位比LinkedList快，而插入删除（不包括定位时间的情况）操作LinkedList更快。

title: ArrayList与LinkedList categories:

数据结构

##1. 关系图

还是只放一个UML图吧，蓝色的箭头是继承关系，绿色虚线箭头是实现的接口

ArrayList

LinkedList

##2. 数组与链表的区别