栈和队列
java
Stack 继承自 Vector,是线程安全的列表实现。
Deque 是继承自 Queue,Queue 在 Collection 基础上定义了队列的方法,Deque 在 Queue 基础上定义了双向队列的方法。
java 里栈一般推荐用实现了 Deque 的 ArrayDeque 。ArrayDeque 和 Stack 内部实现差不多,都是基于数组实现的,但 ArrayDeque 效率比 Stack 高很多。
- Stack 是线程安全的,每个方法都有 synchronized 。
- 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,适用于读多写少场景。在其它场景还是直接用锁比较好。