伸展树 _SplayTree

https://zh.wikipedia.org/wiki/%E4%BC%B8%E5%B1%95%E6%A0%91

伸展树（英语：Splay Tree）是一种能够自我平衡的二叉查找树，它能在O(log n)内完成插入、查找和删除操作。

在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

_SplayTree的插入和删除都会将相应节点搬移到树根去。如新插入的点就是根节点；删除操作前先将要删除的节点搬移到树根去，然后再删除。

SplayTreeMap

class SplayTreeMap<K, V> extends _SplayTree<K, _SplayTreeMapNode<K, V>> with MapMixin<K, V>
用key来进行排序比较

SplayTreeSet

class SplayTreeSet<E> extends _SplayTree<E, _SplayTreeNode<E>> with IterableMixin<E>, SetMixin<E>
直接用值来进行排序比较

拓展 OrderedSet
- flutter 的游戏框架flame使用OrderedSet来存储游戏中渲染的组件。
- 与SplayTreeSet 的区别是可以存储compare相等的元素。SplayTreeSet中不能存compare相等的元素。

哈希表 HashTable

https://en.wikipedia.org/wiki/Hash_table

算法最差情况出现在所有key通过hash function计算后得到同样的结果
dart中的基于HashTable实现的Set和Map如下
Map：HashMap、LinkedHashMap（Map的默认实现）
Set：HashSet、LinkedHashSet（Set的默认实现）
LinkedHashMap、LinkedHashSet会跟踪元素的插入顺序，并按插入顺序进行遍历。

hash_table.png

数组 List

数组如果在最后面增删，其算法时间复杂度为O(1)，因为在最后面增删不用移动或者拷贝数组内其他元素

数据排序算法

此处只讨论List的排序方法void sort([int compare(E a, E b)]);List使用的排序算法为双轴快速排序
https://github.com/dart-lang/sdk/blob/da0363172adaa266ef2d44cf87e09b61a185e79d/sdk/lib/internal/sort.dart

单轴快速排序：

快速排序的基本思想就是从一个数组中任意挑选一个元素（通常来说会选择最左边的元素）作为中轴元素，将剩下的元素以中轴元素作为比较的标准，将小于等于中轴元素的放到中轴元素的左边，将大于中轴元素的放到中轴元素的右边，然后以当前中轴元素的位置为界，将左半部分子数组和右半部分子数组看成两个新的数组，重复上述操作，直到子数组的元素个数小于等于1（因为一个元素的数组必定是有序的）。

双轴快速排序：

双枢轴快速排序的想法是采用两个枢轴，一个在阵列的左端，第二个在阵列的右端。左枢轴必须小于或等于右枢轴，因此如有必要，我们将其交换。
然后，我们开始将数组划分为三个部分：在第一部分中，所有元素都将小于左枢轴，在第二部分中，所有元素都将大于或等于左枢轴，并且还将小于或等于右枢轴，在第三部分中，所有元素都将大于右枢轴。然后，我们将两个枢轴移动到其合适的位置，如下图所示，然后，我们开始使用此方法对这三个部分进行递归快速排序。