前言
作为程序员，基础数据结构是我们在日常工作中必须掌握的基础知识，就像是建房子时的图纸，而熟练地掌握数据结构可以让我们在工作中能够以更加高效和巧妙的方式来解决所遇到的问题。
然而，没有一个数据结构是完美的，每一个数据结构都是优点和缺点并存，就如同世间万物，总是有正反或阴阳两面。 每一个数据结构都是计算机科学家们为了解决某一个问题而发明的，并没有好坏之分，只是在具体的场景下，会有更适合的应用。
因此，随着计算机科学的发展，就产生了非常多的数据结构。
这里我尝试由浅入深去猜想各种数据结构产生的原因并将它们进行串联，期望能够达到方便记忆的效果。
提醒: 以下数据结构演进原因为个人理解和猜想，只是为了串联各种数据结构。
基础结构
Array
查找 O(1)
插入/删除 O(n)
数组应该是我们日常中使用最多的数据结构，数组是由一个个元素组成，并以下标一一做标记。它的特别非常明确，可以直接通过下标查找或修改元素，因此查找和修改非常高效； 但要插入或删除元素时，需要重新排列下标，效率较低。因此数组适合多读少写的场景（这里的写指插入和删除元素）。
那肯定要解决插入效率低的场景啊，所以程序员就想到取消下标的方式，将每个元素按顺序串联起来，以串联的顺序来决定元素所在的问题，这也就是LinkedList了。
LinkedList
查找 O(n)
插入/删除 O(1)
链表也是由一个一个元素组成，但是以一种串联的形式组成。 链表的元素叫node，下一个node指向上一个node，一直到最前面的node，像是一个链条。如果要在AB两个node中新增一个node， 只需B node指向新node，而新node再指向A，就完成了插入，非常高效。但因为缺少下标，它不是很擅长查找的场景，因为没有下标来快速定位，它需要一个一个node地询问，直到找到自己的目标。因此数组 适合少读多写的场景。
Map
查找 O(1)
插入 O(1)
但程序员肯定会遇到既需要查找快，也需要修改快的场景啊。那这种场景下，Array和LinkedList都不是特别能够满足要求了。 于是，程序员就想如何解决这样的问题。
程序员先从分析Array下手
Array修改低下的原因主要是：
- 在中间进行元素插入或删除，就需要重排下标
- 初始大小固定，如果超出，则需要重新分配和迁移元素
所以，要解决Array修改效率低的问题就需要
- 取消下标，用非顺序数字的形式来作为索引，进行查找
- 不设置固定大小
于是程序员就自己实现了新的数据结构来尝试解决这个问题，就有了Map。
tips：Java中Map是通过Array实现的，所以其实固定大小的问题在Java中没有被解决。
Map是由一个个pairs组成，pairs是由key和value组成。 Map的优势就是可通过key快速查找到value的值。也可以高效地插入新的Pair。 当然Map也有缺点，Map的索引不是类似有序数字的下标，所以Key是无序的，且作为索引，Key元素不可重复。
Tree
查找 O(logN)
插入 O(logN)
于是程序员又想，那能不能从LinkedList入手，尝试去解决LinkedList的缺陷。 LinkedList的问题是查找效率。通过顺序查找是比较低效的查找方式，而在元素有序的条件下，最有效率的方式应该就是二分法查找了。 二分法的思路有点像算法中的“剪枝”，当路径分叉时，只关注有用的路径。 能不能通过二分法查找来提高LinkedList的查找效率呢？
程序员受到二分法查找的启发，发明了又一个新的数据结构 - Tree。
Array 的衍生
Vector(Java和C++中的实现)
Vector在理论上的定义就是一维数组。
但在Java中的实现会有些特点。
众所周知，Array有个限制，就是在初始化时需要给定大小来确定分配的内存大小。程序员写多了Size不够用的Array之后，心想将这个过程抽个方法吧，太累了，后面就演进成了一个新型数据结构Vector， 其实就是能够自动扩展的Array了。
Java中实现的Vector还有个特点，插入元素时是单线程加锁插入。
Stack
当程序员经常要写插入元素到数组，然后以倒序输出的场景。他就在想，这块代码是不是也能抽离一下，每次都要记录下标和Size，封装一下应该就通用很多。于是，就有了Stack，一个以First In Last Out闻名的数据结构。 其实就是倒序排序了一下。
Queue
既然有了正序输入倒序输出的场景（Stack），自然少不了正序输入正序输出的场景了，于是程序员也创造了Queue，类似管道或队列，所以Queue的特点就是First In First Out。
DeQueue(Double-end Queue)
有了Queue之后，程序员又想，要不再做灵活点，方便我从头尾都可以输入，也可以从头尾都可以读取，于是就有了DeQueque。
Map的衍生
Set
程序员偶尔会遇到需要元素唯一的场景，如果有Array来做，我们在收集完元素后，还需要进行一个算法复杂度为O(n)的排除计算。因此期望用一个数据结构来解决这个问题，就叫Set。
之前我们说到过Map有个特点是Key元素不可重复，Java程序员发现可以利用Map这个特性，在元素去重的场景做到自然过滤，避免了多余的排除计算，因此Java中，Set的底层是通过Map来做实现的，也叫HashSet。
HashMap/HashTable
HashMap可以理解为Map的衍生，也可以理解为是其中一种具体的实现。
当Map中的元素较多时，如果要去判断某个元素是否存在于Map中，就会遍历N次。所以程序员们就想了个方法来减少Key的数量，来提高这里的效率。 通过结合Hash算法，可以控制Pair中Key的冲撞几率，可以用较少的Key储存更多的Value。这个设计就很类似于索引。
然而，这样的结果就是Pair中的Value就会存在多个，在Java中是使用LinkedList来存储同一个pair中的多个value的。
tips: Java8之后，也对HashMap做了优化，当碰撞的次数大于8并且总容量大于64的时候，储存Value的链表就会变为红黑树结构（这里应该就默认这里变为了需要提高读效率的场景了)。 tips2: 在Java中，HashMap和HashTable有个小的区分实现，HashTable的元素插入是会加锁(sychronized)插入的。
BloomFilter
BloomFilter一般比较少被大家使用，但实际用处还比较大。 BloomFilter是一个很长的二进制向量(可以使用BitSet, 也可以使用Map)和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。 它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
Tree的衍生
Search Tree
我们之前有说到，Tree的查找是有受到二分法的启发。二分法可以使用的一个必要条件就是需要元素是有序的。因此，想要Tree的查找应用二分法查找的方式，自然其中的元素也必须是有序的。 这种Tree，被命名为Search Tree，其中任何节点都必须比左子树中的节点大，而比右子树上的节点小。
BinaryTree
那要让二分查找法在Tree中的效率最高，就最好是每个节点下最多有两个子节点，这种类型的Tree我们叫它BinaryTree。所以BinarySearchTree理论上是Tree中搜索速度最快的。
BalancedTree(AVL Tree, Treap, Splay Tree, RedBlackTree et al.)
Tree的搜索效率还有一个重要的影响因素，就是树的高度。 那程序员就想如何才能让树的高度永远处于一个最优的情况呢？ 其实高度最优的情况就是避免产生极度坏的情况(极度坏的情况其实就类似链表了)，让根节点到每个叶子节点的路径都相等，就避免了最坏查询情况的产生。 要想达到该效果，就要在每次新元素加入或移除的时候，对树做一些额外调整，也就产生了自平衡树。
Priority Queue & Heap(Max & Min)
基于Search Tree的一个拓展，Seach Tree的排序是从左到右的。那程序员有天就想，如果是一个优先取最小值的场景的话，将排序做成垂直的，从小到大排列，那不是第一个就是最小值么，于是做了这样的优化后，就产生了Priority Queue。同理，也适用于从大到小排列的场景。
tips: Heap是Priority Queue的一种实现
Tree在业务场景中衍生的数据结构
Trie
利用Tree分叉的结构来做单词搜索，提升搜索效率，产生了新的数据结构Trie。
Disjoint-Set/Union Find Set
Disjoint-set又叫并查集，一般被用来做分类和区分。Disjoint-set的实现一般是使用类似Tree的结构，利用了Tree每个节点都只会有一个Parent的特性来做分类和合并。当两个节点的root节点一致时，则认为两个节点为一类。
Graph
Tree有一个特点就是每个节点都只能有一个父节点，但现实生活中，肯定会出现需要一个节点有多个父节点的情况，就产生了一个特殊的Tree，一个新的数据结构，被命名为Graph。
Graph由vertices和edges组成。
B Tree
B Tree的场景有点特殊，在数据库设计者在设计索引时，肯定是要符合多写多读的场景的，再加上对顺序的要求，很自然是应该应用Tree。 但如果使用上面说到的BinarySearchTree，会产生一个问题。 因为数据库的数据最终是要存储在硬盘上的，开发同学可能都知道磁盘查询是个性能较慢的操作，特别是随机查询。要知道Tree的每一个节点都是独立的，所以不可能是连续数据，如果按照BinarySearchTree的方式来做，就会使得树的高度增加，导致查询节点的次数增多，每一个都要做一次磁盘查询，这样总体上性能就会很慢。 那为了解决这个问题，数据库的设计者们就想到了一个针对性的优化-减少树的高度，一个节点多存些数据。于是就发明了一种新的Tree的数据结构，命名为B Tree。
B+ Tree
B+ Tree是B Tree的增强版，是为了优化B树刚好在范围查询时，查找的数据没有在当前节点上，而导致额外查询其他兄弟节点的场景。所以数据库设计者又将B Tree中的兄弟节点都链接起来，加快同级查询，就产生了B+ Tree。
既然说到了关系型数据库所使用的B+树，那就顺带讲一下redis中应用的另一种业务场景中衍生的数据结构。
LinkedList在业务场景中衍生的数据结构
跳表(SkipList)
我们之前提到过LinkedList适合多写少读的场景，因为查询效率不高。跳表的发明就是尝试解决LinkedList的这个缺陷的。跳表可以理解为是加了索引的LinkedList。 Redis中就是用跳表来实现有序集合的。
那Redis为什么不用树来实现呢？ 我的理解是Redis是基于内存的，所以不用过于考虑硬盘查询的性能消耗，就没有必要使用B+树这样的结构，那最快的查询树就是BinarySearchTree了。但BinarySearchTree在区间范围查询上有个缺陷，也就是为什么B树演进为B+树的原因。 因此，就发明了跳表，LinkedList加上索引后，采用的思路也是类似于二分法的思路，也解决了Tree在范围查询上的缺陷，唯独就是理论上会比Tree多占用些空间，以空间换时间。
结语
希望读过这篇文章的同学都能够理解每一个数据结构产生的原因，并能够熟练地应用。
附上我整理的关系图
最后推荐这个网站，它将各种数据结构和算法以可视化的形式展示了出来，非常便于理解