資料庫管理系統(DBMS) - 散列：初學者指南

你好，未來的資料庫魔法師們！今天，我們將要踏入資料庫管理系統中的神奇世界——散列。如果你從未寫過一行代碼也不用擔心——我將會是你在這場冒險中的友好指南。所以，拿起你的虛擬魔杖（鍵盤），我們開始吧！

什麼是散列？

在我們深入細節之前，讓我們先了解散列到底是什麼。想像你正在組織一座巨大的圖書館。你決定不是按字母順序排列書籍，而是根據書名給每本書一個唯一的數字。這就是散列在數據庫中做的事情——它將數據轉換為固定大小的值（稱為散列值），以便於存儲和检索。

一個簡單的散列示例

讓我們從一個基本的Python示例來說明散列：

def simple_hash(string):
total = 0
for char in string:
total += ord(char)
return total % 10

print(simple_hash("Hello"))  # 輸出: 2
print(simple_hash("World"))  # 輸出: 7

在這個示例中，我們創建了一個非常簡單的散列函數。它計算字符串中每個字符的ASCII值總和，然後使用模數運算符來得到0到9之間的數字。這是一種非常基本的散列形式，但它給你一個散列是如何工作的概念。

散列組織

現在我們對散列有了一個基本的理解，讓我們看看它在數據庫中是如何組織的。

散列表

散列表是散列組織的基石。將散列表想像成一個高級數組，其中每個元素（通常稱為桶）可以存儲多個項目。

以下是在Python中散列表的一個簡單實現：

class HashTable:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(self.size)]

def hash_function(self, key):
return hash(key) % self.size

def insert(self, key, value):
hash_key = self.hash_function(key)
self.table[hash_key].append((key, value))

def get(self, key):
hash_key = self.hash_function(key)
for k, v in self.table[hash_key]:
if k == key:
return v
return None

# 使用我們的散列表
ht = HashTable(10)
ht.insert("apple", 5)
ht.insert("banana", 7)
print(ht.get("apple"))  # 輸出: 5
print(ht.get("grape"))  # 輸出: None

這個散列表使用Python的內置hash()函數和模數運算符來確定存儲每個鍵值對的位置。當我們想要检索一個值時，我們使用相同的過程來找到它應該存儲的位置。

靜態散列

靜態散列就像在圖書館中有固定數量的書架。你知道你能夠存儲多少書，但如果你有很多同一主題的書，你可能會遇到問題。

靜態散列的優點和缺點

優點	缺點
實現簡單	可能導致分配不均
對小數據集速度快	對於增長的數據集不靈活
性能可預測	可能浪費空間

桶溢出

有時候，我們的散列函數可能會將太多的項目發送到同一個桶。這稱為桶溢出，就像試圖將太多的書塞到一個書架上。

處理溢出

有幾種方法可以處理溢出：

1. 鏈接法：每個桶包含一個條目的鏈表。
2. 開放地址法：如果一個桶已滿，我們尋找下一個空桶。

讓我們在我們之前的散列表中實現鏈接法：

class ChainedHashTable:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(self.size)]

def hash_function(self, key):
return hash(key) % self.size

def insert(self, key, value):
hash_key = self.hash_function(key)
for item in self.table[hash_key]:
if item[0] == key:
item[1] = value
return
self.table[hash_key].append([key, value])

def get(self, key):
hash_key = self.hash_function(key)
for k, v in self.table[hash_key]:
if k == key:
return v
return None

# 使用我們的鏈接散列表
cht = ChainedHashTable(10)
cht.insert("apple", 5)
cht.insert("banana", 7)
cht.insert("cherry", 3)
print(cht.get("apple"))  # 輸出: 5
print(cht.get("cherry"))  # 輸出: 3

在這個實現中，每個桶可以持有多個鍵值對，從而解决了溢出問題。

動態散列

動態散列就像擁有一個神奇的圖書館，當你需要時會長出新的書架。它比靜態散列更靈活，並能夠適應增長的數據集。

可伸縮散列

動態散列的一種流行形式是可伸縮散列。它使用一個可以根據需要增長或縮小的目錄結構。

以下是一個可伸縮散列的簡化實現：

class ExtendibleHashTable:
def __init__(self, bucket_size=2):
self.bucket_size = bucket_size
self.global_depth = 1
self.directory = [[] for _ in range(2**self.global_depth)]

def hash_function(self, key):
return hash(key) % (2**self.global_depth)

def insert(self, key, value):
hash_key = self.hash_function(key)
if len(self.directory[hash_key]) < self.bucket_size:
self.directory[hash_key].append((key, value))
else:
self._split(hash_key)
self.insert(key, value)

def _split(self, index):
self.global_depth += 1
new_directory = [[] for _ in range(2**self.global_depth)]
for i, bucket in enumerate(self.directory):
new_index = i if i < index else i + 2**(self.global_depth-1)
new_directory[new_index] = bucket
self.directory = new_directory

def get(self, key):
hash_key = self.hash_function(key)
for k, v in self.directory[hash_key]:
if k == key:
return v
return None

# 使用我們的可伸縮散列表
eht = ExtendibleHashTable()
eht.insert("apple", 5)
eht.insert("banana", 7)
eht.insert("cherry", 3)
eht.insert("date", 9)
print(eht.get("apple"))  # 輸出: 5
print(eht.get("date"))   # 輸出: 9

這個實現允許散列表隨著更多項目的添加而動態增長。

組織和操作

現在我們已經介紹了散列的基本知識和一些實現，讓我們總結一下關鍵操作及其複雜度：

操作	平均時間複雜度	最壞情況
插入	O(1)	O(n)
刪除	O(1)	O(n)
搜索	O(1)	O(n)

平均情況通常非常快，這也是散列如此流行的原因。然而，在最壞的情況下（當所有項目都散列到同一個桶時），性能可能會退化到鏈表的水平。

結論

恭喜你！你剛剛踏入了DBMS中散列的世界。記住，散列是關於在速度和空間之間找到平衡。當使用正確時，它是一個強大的工具，可以显著提高數據庫操作的效率。

隨著你在計算機科學的道路上繼續前行，你會在許多其他上下文中遇到散列——從密碼存儲到緩存系統。每次你使用Python中的字典或JavaScript中的對象時，你都是在從散列的魔法中受益！

持續練習，保持好奇心，並且快樂編程！

Credits: Image by storyset