Luna Tech | 聊聊关联数组(Associative Array)

July 30, 2020 字数 1512 4 min


0. 前言

通过之前的数据类型讲解,我们知道了三种数据类型(Primitive,Composite,Abstract),抽象数据结构简称 ADT(Abstract Data Type)。

Luna Tech | 聊聊数据结构(Data Structure)一文中,我提到了:

这种 Hash Value 和 Key-Value pair 一一对应的关系也被称作 Associative Array(关联数组)

Luna Tech | 聊聊树结构(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)。

人们现在有两种主要的解决方式:

  1. Hash Table(一种非线性数据结构)
  2. Search Tree(查找树)

比如 C# 里面的 Dictionary 本质上就是 Hash Table(也就是 Associative Array 的实现形式之一)。

Microsoft Doc says:

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

Reference: https://runestone.academy/runestone/books/published/pythonds3/Trees/SummaryofMapADTImplementations.html


4. 关联数组和集合的关系

Set (集合) 也是一种 ADT,用来存放不重复的值,Set 里面的元素是无序的。

计算机领域的【集合】概念源于数学里面的有限集合(Finite Set),也就是一个集合里面的元素数量是可数的。

集合的主要用途是什么呢?

集合主要用于【增查改删】的查,更确切地说,是用于确认【某元素是否存在于集合中】。

PS:集合有各种各样的种类,咱这里先省略细节。

集合是如何实现的?

最简单的方式是用 Linked List 或者 Array,但是这种方式需要遍历元素,效率不高。

所以很多时候,集合是用 Tree 或者 Hash Table 来实现的。

等等,Tree 和 Hash Table 不是 Associative Array 的实现方式吗?

对啦,其实集合的实现方式和 Associative Array 是一样的……

绕来绕去还是回到 Tree 和 Hash Table 了~

Wikipedia - Set

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. 结语

本文主要讲了:

  1. Associative Array 是一种抽象数据结构(ADT),目的是更高效的【增查改删】,解决线性结构的缺陷
  2. Associative Array 常用 Tree 和 Hash Table 这两种数据结构来实现
  3. Linked List 可以用来实现 Hash Table
  4. Set 主要是为了查看元素是否存在于集合,实现方式和 Associative Array 类似

Talk to Luna


Support Luna