利用Python实现高效的哈希映射：Dictionary Set

Python 笔记

哈希映射是一种将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中的应用非常广泛，可以用来解决大量的问题。在哈希冲突的解决方案中，开放地址法比拉链法的实现方式更加高效，但也需要考虑到不同的解决方案对空间消耗的影响。