associative-container

關聯容器 Associative Container

關聯容器是一種抽象資料型別，儲存鍵與值配對關係（key-value pair）的集合，並透過鍵存取元素，所謂「鍵值對」好比身份證字號與公民，戶政單位知道一個人證號，就可在關聯容器內，透過證號查找是否有這個公民，以及此證號對應的公民基本資訊。

關聯容器有許多別名，例如字典（dictionary）、關聯陣列（associative array）、映射（map）、表（table）等。在大多數程式語言函式庫中，關聯容器通常是最基本的容器型別之一，如 Python 的 dict，JavaScript 的 Map，以及 Rust 的 HashMap。

方便起見，本文以「映射表」統稱這類集合型別。

（雜湊表示意圖）

特性

一般來說，映射表有以下特性：

• 鍵值對為單向關係：可透過鍵取得其唯一值；但無法確保一值僅對應唯一的鍵。
• 鍵值唯一性：同個映射表內，同個鍵不重複，只會出現一次。
• 元素組合性：映射表內每個元素都是「鍵值對」，鍵或值無法單獨存在。
• 操作開銷小：合理實作下，基本操作開銷相對較小，不高於線性時間。

註：多重映射表為一對多的例外。

映射表會有以下幾種基本操作：

• 新增：配對鍵值關聯，又稱為綁定 binding。
• 修改：修改任意鍵之下的值。
• 移除：透過任意鍵移除該鍵值對，又稱 unbinding。
• 查找：透過任意鍵搜尋該鍵值對。

不難看出，基本操作都是透過鍵取得值。事實上，合理實作的映射表，只要透過鍵來操作，就能有良好效能，甚至上述操作能達到 $O(1)$ 複雜度。

適用場景

雖然映射表依實作不同，效能有所權衡。但其最大優勢仍是可「高效地透過鍵尋找值」，只要有映射關係的資料，都非常適合使用映射表。例如，快取暫存機制需透過特定鍵快速查找暫存值。此外，現代常用的 JSON、TOML 等資料交換格式，都是「鍵—值對」的形式，非常適合使用映射表處理。而應用映射表最有名的實際案例莫過於資料庫的索引，透過索引，我們可以大大降低搜尋的成本，從線性時間直落到對數甚至常數時間，不過相對就需要付出額外時空間建立索引。

我們再次把應用場景條列出來，方便懶人帶著走。

• 有映射關係，處理「鍵—值」配對的資料結構。
• 處理 JSON、TOML 等資料交換，資料序列化。
• 實作快取（cache）機制。
• 資料庫索引的實作方法之一。
• 查找操作頻率遠高於其他操作時。

總的來說，只要資料有對應綁定關係，就可以考慮使用映射表處理。

種類

以下簡單介紹常見的映射表，詳情請點擊各連結。

雜湊表 Hash Map

雜湊表是以雜湊函數實作的映射表。透過雜湊函數將任意資料轉換為固定長度的雜湊值，並將此鍵與一筆資料綁定，再映射到內部資料結構的某位置。理論上，只要雜湊函數品質過得去，雜湊表的基本操作都能在常數時間完成。

有序映射表 Ordered Map

有序映射表係一種有特定排序方式的映射表。常見兩種排序方式，其一是依照插入映射表的先後順序；其二則是依照鍵的大小。不同排序的底層資料結構各異，操作複雜度也不盡相同，如依鍵大小排序的映射表通常使用搜索樹實作，因此「新增」操作的複雜度為較差的 $O(\log n)$。

多重映射表 Multimap

多重映射表允許鍵值對重複，一個鍵可對應多個值（一對多）。類似於映射表內放入陣列，但能以較方便輕鬆的介面來操作或疊代整張映射表。

集合 Set

集合實際上並無鍵值「關聯」，可將其想像成普通的映射表。只關心鍵而值不重要。集合借用了數學集合論（set theory）中有限集合的概念，常應用於需要操作交集、聯集、差集等集合運算場景。

布隆過濾器 Bloom Filter

布隆過濾器是一種類似於集合，但只會回報「絕對不存在」或「可能存在」的機率資料結構，實作上節省空間，常用於在海量資料中確認成員是否存在，並能有一定容錯率的場景。

參考資料

• Wiki: Associative array
• Wiki: Associative containers
• cpprefernce.com: std::map
• Rust documentation: std::colledtion
• Map graph by Jorge Stolfi CC BY-SA-3.0 via Wikimedia Commons.