基础回顾

栈和队列

java

Stack 继承自 Vector，是线程安全的列表实现。
Deque 是继承自 Queue，Queue 在 Collection 基础上定义了队列的方法，Deque 在 Queue 基础上定义了双向队列的方法。
java 里栈一般推荐用实现了 Deque 的 ArrayDeque 。ArrayDeque 和 Stack 内部实现差不多，都是基于数组实现的，但 ArrayDeque 效率比 Stack 高很多。

1. Stack 是线程安全的，每个方法都有 synchronized 。
2. ArrayDeque 内部只在空间不够的时候，进行扩容。而 Stack 其基于 Vector 会不断进行数组的 arraycopy 操作。
   所以其实就算要线程安全，也可以使用 Collections.synchronizedXXX 来处理或者用更高效的类。

go

go 的 mao 和 slice 是我看的比较累的源码，或者说有的根本就没有源码了。原因是有的直接就汇编进行了，有的方法它内嵌到 runtime 中了，没有明显的调用逻辑。
go 里面栈和队列都不用新建类，通过 slice 的一顿切片操作就可以满足。go 中切片原理简单来说就是创建一个指向原数组内存的新的结构体，不会进行拷贝数据等等。但切片不好点在于因为不会实际上删除，所以头部空间会一直存在。

C++

SGI STL 下，stack 会以 deque 为缺省情况的数据结构，也可以额外指定数据结构。所以 stack 不是容器，而是 contain adapter 的概念。其不会提供迭代器。

python3

在 python 中，就比较简单了。作为 stack，数组自带 append 相当于 push，list.pop() 相当于 pop，list[-1] 就是 peek。当然队列也可以这么干，但是性能就很低了，尤其在长数组的时候，因为移除头部数据会导致所有元素位移。队列应该使用 from collections import deque。python 也有切片，但它和 go 不同，它的切片会复制内存，而 go 不会。

树

一般生产里面用到的少。在高性能的地方会用到，因为树天然的分而治之的思想。

java

HashMap 里面同一个链表超过 8 会转而使用红黑树。PriorityQueue 里面用了最大堆最小堆的概念，实现它用了数组来实现，类似最大堆这种完全二叉树，用列表表示是比较清晰而且省内存。

HashMap

java

HashMap 内部初始化用了泊松分布得出的0.75因子，，扩容会重新计算 hash 来扩展，1.8 开始里面同一个链表超过 8 会转而使用红黑树。java 1.7 并发类使用了分桶加锁。java 1.8 并发类使用了 CAS+synchronized Node 来确保并发，保留了 HashMap 的红黑树等等特性。

go

Map 使用数组+桶+溢出桶链表。 sync.Map 则使用了 dirty，适用于读多写少场景。在其它场景还是直接用锁比较好。