聊聊关联数组（Associative Array）
2020-07-30
0. 前言
通过之前的数据类型讲解，我们知道了三种数据类型（Primitive，Composite，Abstract），抽象数据结构简称 ADT（Abstract Data Type）。
在 聊聊数据结构（Data Structure） 一文中，我提到了：
这种 Hash Value 和 Key-Value pair 一一对应的关系也被称作 Associative Array（关联数组） 。
在 聊聊树结构（Tree） 一文中，我提到了：
BST（二叉查找树）这种数据结构是用来实现 Abstract Data Type 里面的 sets（集）, multisets（多重集）, associative arrays（关联数组）的。
下面我们就来好好认识一下 Associative Array（关联数组）这个重要的数据结构吧~
1. 关联数组是什么？
首先，Associative Array 有很多别名，它和 Map（映射）、Dictionary（字典）本质上是一个东西。
Associative Array 由 Key-Value Pair（键值对）组成，在 Associative Array 里面，每个 key 都是独一无二的。
这种数据类型支持【增查改删】这四种常见操作。
2. 我们为什么需要关联数组？
复习
我们之前讲过 Array 这种线性数据结构，Array 的特点是，查起来特别快（因为它用的是一块连续的内存），但是缺点也很明显，【查改删】特别麻烦（需要找到另一块连续内存）。
而另一种线性数据结构——Linked List，通过增加指针的方式来尝试解决 Array 存在的问题，这种方式的缺点在于，每一个操作都需要遍历所有的元素（因为它是线性的……）。
既然线性数据结构无法满足我们的需求，那我们就用非线性数据结构来实现 Associative Array 吧！
在选择数据结构的时候，我们要考虑可能的操作，如果只是简单的【查】，那么 Array 是最高效的，但是如果涉及到【增查改删】这些复杂的操作，就应该选择 Associative Array 的相关数据结构（比如 dictionary，map……）。
3. 关联数组是如何实现的？
既然 Associative Array 是一种 ADT，那么我们需要通过相应的数据结构去实现它。
字典问题和解决方式
如何实现 Associative Array，也被称为【字典问题】（dictionary problem）。
人们现在有两种主要的解决方式：
- Hash Table（一种非线性数据结构）
- Search Tree（查找树）
比如 C# 里面的 Dictionary 本质上就是 Hash Table（也就是 Associative Array 的实现形式之一）。
Microsoft Doc says:
- Dictionary is a generic version of Hashtable .
Linked List 可以帮忙
虽然 Linked List 是一种线性数据结构，但是实现 Associative Array 的时候我们可以（并不是必须）用到它。
为什么呢？
-
Linked List 的本质是 value + pointer；
-
Double Linked List 的本质是 pointer + value + pointer。
试想，假如我们把 value 换成 hash value，把 pointer 改成指向 hash value 所对应的 Key-Value Pair，那 Linked List 不就等于一个 Hash Table 的元素了吗？
补充：不同的 implementation performance 比较
- Sorted List
- Hash Table
- Binary Search Tree
- Balanced Binary Search Tree
4. 关联数组和集合的关系
Set (集合) 也是一种 ADT，用来存放不重复的值，Set 里面的元素是无序的。
计算机领域的【集合】概念源于数学里面的有限集合（Finite Set ），也就是一个集合里面的元素数量是可数的。
集合的主要用途是什么呢？
集合主要用于【增查改删】的查，更确切地说，是用于确认【某元素是否存在于集合中】。
PS：集合有各种各样的种类，咱这里先省略细节。
集合是如何实现的？
最简单的方式是用 Linked List 或者 Array，但是这种方式需要遍历元素，效率不高。
所以很多时候，集合是用 Tree 或者 Hash Table 来实现的。
等等，Tree 和 Hash Table 不是 Associative Array 的实现方式吗？
对啦，其实集合的实现方式和 Associative Array 是一样的……
绕来绕去还是回到 Tree 和 Hash Table 了~
Sets are often instead implemented using more efficient data structures, particularly various flavors of trees , tries , or hash tables .
……a self-balancing binary search tree for sorted sets (which has O(log n) for most operations), or a hash table for unsorted sets (which has O(1) average-case, but O(n) worst-case, for most operations). A sorted linear hash table may be used to provide deterministically ordered sets.
5. 结语
本文主要讲了：
- Associative Array 是一种抽象数据结构（ADT），目的是更高效的【增查改删】，解决线性结构的缺陷
- Associative Array 常用 Tree 和 Hash Table 这两种数据结构来实现
- Linked List 可以用来实现 Hash Table
- Set 主要是为了查看元素是否存在于集合，实现方式和 Associative Array 类似