利用Python實現高效的哈希映射：Dictionary Set

哈希映射是一種將key與value關聯起來的數據結構。通過將key通過哈希函數轉化為一個數字，將這個數字與一個數組下標相關聯，就可以實現將key與value進行快速查找。在Python中，Dictionary與Set就是哈希映射的兩種實現方式。

一、Dictionary的使用

Dictionary，也叫做字典，是Python中內置的數據類型之一。可以將Dictionary看作是一種無序的鍵值對集合。其中每個鍵（key）都是唯一的，對應的值（value）可以是任意類型。下面是一個簡單的例子：

{
    "name": "Tom",
    "age": 25,
    "gender": "male"
}

在Python中，可以使用“{}”或者“dict()”來創建Dictionary，並且可以通過索引方式獲取對應的值：

# 創建Dictionary
student = {
    "name": "Tom",
    "age": 25,
    "gender": "male"
}

# 讀取Dictionary
print(student["name"]) # Tom
print(student.get("age", 0)) # 25

Dictionary的特點之一是可以通過鍵來快速檢查值是否存在：

if "name" in student:
    print("Name is in the student dictionary.")

二、Set的使用

Set是另一種基於哈希表實現的數據結構。Set中存儲的是一組互不相同的元素，類似於Dictionary中的key，可看作是一組不重複的值。Set中元素的排列順序是無序的。

Set最常用的方式是將一個列表或者元組轉化為一個Set，也可以直接使用“{}”或“set()”函數創建：

# 列錶轉Set
num_list = [1, 2, 3, 4]
num_set = set(num_list)
print(num_set) # {1, 2, 3, 4}

# 創建Set
fruit_set = {"apple", "banana", "orange"}

可以使用常見的集合操作，例如並集、交集和差集：

A = set([1, 2, 3, 4, 5])
B = set([4, 5, 6, 7, 8])

# 並集
print(A | B) # {1, 2, 3, 4, 5, 6, 7, 8}

# 交集
print(A & B) # {4, 5}

# 差集
print(A - B) # {1, 2, 3}

三、哈希衝突的解決辦法

在哈希映射中，不同的key可能會經過哈希函數以後映射到數組的同一個位置上，這就是哈希衝突。當發生哈希衝突時，可以使用一下兩種方法來解決：

1、拉鏈法：拉鏈法是一種將散列表中的每個單元都變成一個鏈表的方法。當出現了衝突，直接在對應的位置上插入一個新的元素即可。

# 哈希衝突的解決（拉鏈法）
class ListNode:
    def __init__(self, key, val):
        self.pair = (key, val)
        self.next = None
    
class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.table = [None] * self.size
    
    def put(self, key, value):
        index = hash(key) % self.size
        if self.table[index] is None:
            self.table[index] = ListNode(key, value)
        else:
            node = self.table[index]
            while node:
                k, v = node.pair
                if key == k:
                    node.pair = (key, value)
                    return
                if node.next is None:
                    break
                node = node.next
            node.next = ListNode(key, value)
    
    def get(self, key):
        index = hash(key) % self.size
        node = self.table[index]
        while node:
            k, v = node.pair
            if key == k:
                return v
            node = node.next
        return -1
    
    def remove(self, key):
        index = hash(key) % self.size
        node = prev = self.table[index]
        if not node:
            return
        if node.pair[0] == key:
            self.table[index] = node.next
        else:
            node = node.next
            while node:
                if node.pair[0] == key:
                    prev.next = node.next
                    return
                node, prev = node.next, prev.next

2、開放地址法：開放地址法是一種使用不同位置的單元來解決衝突的方法。可以通過線性探測、平方探測和再哈希等方式來選擇下一個空閑位置。

# 哈希衝突的解決（開放地址法）
class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.keys = [0] * self.size
        self.values = [0] * self.size
    
    def put(self, key, value):
        index = self.hash_function(key)
        while self.keys[index] != 0 and self.keys[index] != key:
            index = (index + 1) % self.size
        self.keys[index] = key
        self.values[index] = value
    
    def get(self, key):
        index = self.hash_function(key)
        while self.keys[index] != 0:
            if self.keys[index] == key:
                return self.values[index]
            index = (index + 1) % self.size
        return -1
    
    def remove(self, key):
        index = self.hash_function(key)
        while self.keys[index] != 0:
            if self.keys[index] == key:
                self.keys[index] = 0
                self.values[index] = 0
                return
            index = (index + 1) % self.size
        
    def hash_function(self, key):
        return key % self.size

結論

Dictionary和Set在Python中的應用非常廣泛，可以用來解決大量的問題。在哈希衝突的解決方案中，開放地址法比拉鏈法的實現方式更加高效，但也需要考慮到不同的解決方案對空間消耗的影響。