應用程式設計/字典和集合

資料結構

在計算機科學中，資料結構是一種資料組織、管理和儲存格式，它允許高效地訪問和修改。^[1][2][3]更準確地說，資料結構是資料值的集合，它們之間的關係以及可以應用於資料的函式或操作。^[4]

資料結構提供了一種有效管理大量資料的機制，用於大型資料庫和網際網路索引服務等用途。通常，高效的資料結構是設計高效演算法的關鍵。一些正式的設計方法和程式語言強調資料結構，而不是演算法，作為軟體設計中的主要組織因素。資料結構可用於組織儲存在主記憶體和輔助儲存器中的資訊的儲存和檢索。^[5]

資料結構通常基於計算機能夠在它的記憶體中的任何位置獲取和儲存資料的能力，該位置由一個指標指定 - 一個表示記憶體地址的位串，它本身可以儲存在記憶體中並由程式操作。因此，陣列和記錄資料結構基於對資料項地址進行算術運算來計算，而連結資料結構基於將資料項地址儲存在結構本身中。

資料結構的實現通常需要編寫一組過程，這些過程建立和操作該結構的例項。資料結構的效率不能與這些操作分開分析。這一觀察促使了抽象資料型別的理論概念，抽象資料型別是一種透過可以在其上執行的操作以及這些操作的數學屬性（包括其空間和時間成本）來間接定義的資料結構。^[6]

存在許多型別的資料結構，通常構建在更簡單的原始資料型別之上：^[7]

• 陣列是一系列按特定順序排列的元素，通常都是相同型別（取決於語言，單個元素要麼都被強制為相同型別，要麼可以是幾乎任何型別）。元素是使用整數索引來訪問的，以指定需要哪個元素。典型的實現為陣列的元素分配連續的記憶體字（但這並不總是必需的）。陣列可以是固定長度的，也可以是可調整大小的。
• 連結串列（也稱為列表）是任何型別的資料元素的線性集合，稱為節點，每個節點本身都有一個值，並指向連結串列中的下一個節點。連結串列相對於陣列的主要優勢在於，始終可以高效地插入和刪除值，而無需重新定位列表的其餘部分。但是，某些其他操作，例如對某個元素的隨機訪問，在列表上的速度比在陣列上慢。
• 記錄（也稱為元組或結構體）是聚合資料結構。記錄是一個包含其他值的價值，通常是固定數量和順序，通常由名稱索引。記錄的元素通常稱為欄位或成員。
• 聯合體是一種資料結構，它指定其例項中可能儲存的許多允許的原始型別中的哪一個，例如浮點數或長整數。與記錄形成對比，記錄可以被定義為包含一個浮點數和一個整數；而在聯合體中，一次只有一個值。分配足夠的儲存空間來容納最寬的成員資料型別。
• 標記聯合體（也稱為變體、變體記錄、區分聯合體或不相交聯合體）包含一個附加欄位來指示其當前型別，以增強型別安全性。
• 物件是一種資料結構，它包含資料欄位，就像記錄一樣，以及對資料內容進行操作的各種方法。物件是類從分類學中的記憶體中例項。在面向物件程式設計的背景下，記錄被稱為普通的舊資料結構，以將它們與物件區分開來。^[8][9]

字典（資料結構）

在計算機科學中，關聯陣列、對映、符號表或字典是一種抽象資料型別，由（鍵，值）對的集合組成，使得每個可能的鍵在集合中最多出現一次。

與這種資料型別相關的操作允許：^[10][11]

• 將一對新增到集合中；
• 從集合中刪除一對；
• 修改現有的一對；
• 查詢與特定鍵關聯的值。

實現關聯陣列提出了字典問題，這是一個經典的計算機科學問題：設計一種資料結構的任務，該結構在“搜尋”、“刪除”和“插入”操作期間維護一組資料。^[12]解決字典問題的兩個主要方案是雜湊表和搜尋樹。^{[10][11][13][14]}在某些情況下，也可以使用直接定址陣列、二叉搜尋樹或其他更專門的結構來解決問題。

許多程式語言將關聯陣列作為原始資料型別包含在內，它們在許多其他語言的軟體庫中可用。內容定址記憶體是一種對關聯陣列的直接硬體級支援的形式。

關聯陣列有許多應用，包括諸如記憶化和裝飾器模式等基本程式設計模式。^[15]

這個名字並非來自數學中已知的結合律。相反，它源於這樣一個事實，即我們將值與鍵關聯起來。

在關聯陣列中，鍵和值之間的關聯通常被稱為“對映”，同一個詞對映也可以用來指建立新關聯的過程。

通常為關聯陣列定義的操作有：^[10][11]

• 新增或插入：向集合新增一個新的 $(key,value)$ 對，將新鍵對映到其新值。此操作的引數是鍵和值。
• 重新分配：替換集合中已有的 $(key,value)$ 對中的值，將現有鍵對映到新值。與插入一樣，此操作的引數是鍵和值。
• 刪除：從集合中刪除 $(key,value)$ 對，取消將給定鍵與其值之間的對映。此操作的引數是鍵。
• 查詢：查詢繫結到給定鍵的值（如果有）。此操作的引數是鍵，返回值是操作的結果。如果找不到值，一些關聯陣列實現會丟擲異常，而其他實現則會建立一個具有給定鍵和值型別預設值（零、空容器...）的鍵值對。

因此，通常情況下，除了新增或重新分配之外，還存在一個單獨的 設定 操作，該操作會在 $(key,value)$ 對不存在時新增一個，否則重新分配它。

此外，關聯陣列還可能包含其他操作，例如確定對映的數量或構造一個迭代器來遍歷所有對映。通常，對於這種操作，返回對映的順序可能是實現定義的。

多重對映透過允許將多個值與單個鍵關聯來概括關聯陣列。 雙向對映是一種相關的抽象資料型別，其中對映在兩個方向上起作用：每個值必須與唯一的鍵關聯，並且第二個查詢操作以值作為引數並查詢與該值關聯的鍵。

假設圖書館提供的貸款集合在資料結構中表示。圖書館中的每本書一次只能由一點陣圖書館使用者借閱。但是，單個使用者可以借閱多本書。因此，關於哪些書借閱給哪些使用者的資訊可以用關聯陣列表示，其中書籍是鍵，使用者是值。使用來自 Python 或 JSON 的符號，資料結構將是

{
    "Pride and Prejudice": "Alice",
    "Wuthering Heights": "Alice",
    "Great Expectations": "John"
}

對鍵“Great Expectations”進行查詢操作將返回“John”。如果 John 還回了他的書，這將導致刪除操作，而如果 Pat 借閱了一本書，這將導致插入操作，導致不同的狀態

{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}

字典的基本定義沒有規定順序。為了保證列舉的固定順序，通常使用關聯陣列的有序版本。有序字典有兩種含義

• 列舉順序對於給定的鍵集始終是確定的，方法是透過排序。對於基於樹的實現而言，情況就是這樣，其中一個代表是 C++ 的 <map> 容器。
• 列舉順序與鍵無關，而是基於插入順序。這就是 .NET Framework 和 Python 中的“有序字典”的情況。

後一種有序字典的含義更為常見。它們可以使用關聯列表實現，或者透過在普通字典之上疊加雙向連結串列來實現。後一種方法，如 CPython 在 3.6 版本之前的版本中使用的方法，具有保持另一種實現的潛在更佳複雜度的優勢。CPython 3.6+ 透過將雜湊表拆分為一個插入有序的鍵值對陣列和一個稀疏陣列（“雜湊表”）來使字典有序。

鍵值資料庫

什麼是鍵值資料庫？

鍵值資料庫是一種非關係型資料庫，它使用簡單的鍵值方法來儲存資料。鍵值資料庫將資料儲存為鍵值對的集合，其中鍵用作唯一識別符號。鍵和值都可以是任何東西，從簡單的物件到複雜的複合物件。鍵值資料庫高度可分割槽，並且允許水平擴充套件到其他型別的資料庫無法達到的規模。

與關係型資料庫相比，鍵值資料庫有何不同？

關係型資料庫使用表格來組織資料。表是結構，它們對它們儲存的記錄施加模式。表中的每一列都有一個名稱和一個數據型別。每一行代表表中的一個單獨的記錄或資料項，其中包含每列的值。關係型資料庫的名稱來自使用元組（如表中的行）來表示有序資料集的數學關係。

這意味著什麼？

鍵值資料庫的工作方式與廣為人知的關係型資料庫 (RDB) 非常不同。RDB 預先定義了資料庫中的資料結構，作為包含具有明確定義的資料型別的欄位的一系列表格。將資料型別公開給資料庫程式，使其能夠應用許多最佳化。相反，鍵值系統將資料視為單個不透明的集合，每個記錄可能具有不同的欄位。這提供了相當大的靈活性，並且更緊密地遵循面向物件程式設計等現代概念。由於可選值不像大多數 RDB 中那樣由佔位符或輸入引數表示，因此鍵值資料庫通常使用更少的記憶體來儲存相同的資料庫，這可能在某些工作負載中導致巨大的效能提升。

活動

1) 編寫一個程式，建立一個字典，其中鍵是 2 到 20 之間的偶數整數，值是相應的鍵乘以它之前的奇數整數。

示例輸出：{2: 2, 4: 12, 6: 30, 8: 56...}

2) 編寫一個程式，它接受兩個列表並將它們合併為一個字典。

示例

list_1 = [5, 10, 15, 20] 

list_2 = ['a', 'b', 'c', 'd']

結果：{5: 'a', 10: 'b', 15: 'c', 20: 'd'}

3) 編寫一個程式，它搜尋最小值並返回相應的鍵。

示例

prices = {'Popcorn': 1.50, 'Soda': 1.00, 'Hotdog': 1.25, 'Nachos': 0.75}

結果：'Nachos'

關鍵術語

字典 / 關聯陣列 / 雜湊 / 對映 - 一種抽象資料型別，可以以 (鍵，值) 對的形式儲存資料。

凍結集 - Python 中的本機資料型別，它具有集合的特性（包括類方法），但像元組一樣是不可變的。

雜湊衝突 - 當使用相同的索引鍵生成兩個條目時發生。當對大型可能的鍵集的隨機子集進行雜湊運算時，這種情況發生的可能性很高。

雜湊表 - 一種儲存鍵值對的資料結構型別。鍵被髮送到雜湊函式，該函式對其執行算術運算。結果（通常稱為 雜湊值 或 雜湊）是雜湊表中鍵值對的索引。

鍵 - 資料庫表中的一個欄位或欄位組合，用於根據某些要求檢索和排序表中的行。定義鍵是為了加快對資料的訪問速度，並且在許多情況下是為了在不同的表之間建立連結。

負載因子 - 雜湊表的一個關鍵統計量，它指的是訪問雜湊表的快慢。較高的負載因子表明表可能會變慢或根本無法工作。

合併演算法 - 一系列演算法，它們將多個排序列表作為輸入，並生成單個列表作為輸出，該列表包含輸入列表的所有元素，並按排序順序排列。這些演算法用作各種排序演算法中的子例程，最著名的是合併排序。

多重對映 - 對映或關聯陣列抽象資料型別的一種泛化，其中可以將多個值與給定鍵關聯併為其返回。

多重集 - 一種與集合類似的關聯容器型別，區別在於多個元素可以具有相同的值。

序列化 - 生成原始物件的文字或二進位制表示，可以將其直接寫入檔案，並提供了一種使用關聯陣列的永久形式的解決方案。

集合 - 一種無序的可變資料型別，其中每個值必須是唯一的。