DSA 哈希映射

哈希映射

哈希映射是一种 哈希表 数据结构，通常包含大量条目。

使用哈希映射，我们可以非常快速地搜索、添加、修改和删除条目。

哈希映射用于查找有关某事物的详细信息。

在下面的模拟中，人们存储在一个哈希映射中。可以使用一个人唯一的社会安全号码（哈希映射的键）来查找某个人，然后我们可以看到这个人的名字（哈希映射的值）。

要理解哈希映射的工作原理，最好先看一下前面两页关于 哈希表 和 哈希集合 的内容。理解下面的单词也很重要。

• 条目：由一个键和一个值组成，形成一个键值对。
• 键：哈希映射中每个条目都是唯一的。用于生成哈希码，该哈希码决定了条目在哈希映射中的存储桶。这确保了每个条目都可以被高效地定位。
• 哈希码：从条目的键生成的数字，用于确定该哈希映射条目属于哪个存储桶。
• 存储桶：哈希映射由许多这样的存储桶或容器组成，用于存储条目。
• 值：可以是几乎任何类型的信息，例如一个人的姓名、出生日期和地址。值可以是多种不同类型信息的组合。

查找哈希码

哈希码由一个 哈希函数 生成。

上面模拟中的哈希函数会获取社会安全号码中的数字（不包括连字符），将它们加在一起，然后对字符的总和进行模 10 运算（% 10），以获得 0 到 9 之间的哈希码数字。

这意味着，根据每个人的社会安全号码的哈希码，该人将被存储在哈希映射的十个可能存储桶中的一个。当我们要从哈希映射中搜索或删除某个人时，会生成并使用相同的哈希码。

只要相应存储桶中只有一个人，哈希码就可以提供即时访问。

在上面的模拟中，Charlotte 的社会安全号码是 123-4567。将数字加在一起得到总和 28，然后模 10 的结果是 8。这就是为什么她属于存储桶 8。

哈希映射中的直接访问

在哈希映射中搜索 Charlotte 时，我们必须使用社会安全号码 123-4567（哈希映射的键），它会生成哈希码 8，如上所述。

这意味着我们可以直接转到存储桶 8 来获取她的名字（哈希映射的值），而无需搜索哈希映射中的其他条目。

在这些情况下，我们说哈希映射在搜索、添加和删除条目时具有恒定时间 \(O(1)\)，这与使用数组或链表相比非常快。

但是，在最坏的情况下，所有人都存储在同一个存储桶中，如果我们试图查找的人是该存储桶中的最后一个人，我们就需要将所有其他社会安全号码与该存储桶中的号码进行比较，才能找到我们要找的人。

在这种最坏的情况下，哈希映射的时间复杂度为 \(O(n)\)，与数组和链表相同。

为了保持哈希映射的快速运行，因此重要的是要有一个能够将条目均匀分布到存储桶中的哈希函数，并且存储桶的数量大致等于哈希映射的条目数。

拥有比哈希映射条目多得多的存储桶是浪费内存，而拥有比哈希映射条目少得多的存储桶则是浪费时间。

哈希映射实现

Python 中的哈希映射通常通过使用 Python 自带的 dictionary 数据类型 来实现，但为了更好地理解哈希映射的工作原理，我们在这里不使用它。

要在 Python 中实现哈希映射，我们创建一个名为 SimpleHashMap 的类。

在 SimpleHashMap 类内部，我们有一个用于初始化哈希映射的 __init__ 方法，一个用于哈希函数的 hash_function 方法，以及用于基本哈希映射操作的方法：put、get 和 remove。

我们还创建了一个 print_map 方法，以便更好地了解哈希映射的外观。

class SimpleHashMap:
    def __init__(self, size=100):
        self.size = size
        self.buckets = [[] for _ in range(size)]  # A list of buckets, each is a list (to handle collisions)

    def hash_function(self, key):
        # Sum only the numerical values of the key, ignoring non-numeric characters
        numeric_sum = sum(int(char) for char in key if char.isdigit())
        return numeric_sum % 10  # Perform modulo 10 on the sum

    def put(self, key, value):
        # Add or update a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Update existing key
                return
        bucket.append((key, value))  # Add new key-value pair if not found

    def get(self, key):
        # Retrieve a value by key
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None  # Key not found

    def remove(self, key):
        # Remove a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]  # Remove the key-value pair
                return

    def print_map(self):
        # Print all key-value pairs in the hash map
        print("Hash Map Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

使用 SimpleHashMap 类，我们可以创建与本页顶部相同的哈希映射。

class SimpleHashMap:
    def __init__(self, size=100):
        self.size = size
        self.buckets = [[] for _ in range(size)]  # A list of buckets, each is a list (to handle collisions)

    def hash_function(self, key):
        # Sum only the numerical values of the key, ignoring non-numeric characters
        numeric_sum = sum(int(char) for char in key if char.isdigit())
        return numeric_sum % 10  # Perform modulo 10 on the sum

    def put(self, key, value):
        # Add or update a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Update existing key
                return
        bucket.append((key, value))  # Add new key-value pair if not found

    def get(self, key):
        # Retrieve a value by key
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None  # Key not found

    def remove(self, key):
        # Remove a key-value pair
        index = self.hash_function(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]  # Remove the key-value pair
                return

    def print_map(self):
        # Print all key-value pairs in the hash map
        print("Hash Map Contents:")
        for index, bucket in enumerate(self.buckets):
            print(f"Bucket {index}: {bucket}")

# Creating the Hash Map from the simulation
hash_map = SimpleHashMap(size=10)

# Adding some entries
hash_map.put("123-4567", "Charlotte")
hash_map.put("123-4568", "Thomas")
hash_map.put("123-4569", "Jens")
hash_map.put("123-4570", "Peter")
hash_map.put("123-4571", "Lisa")
hash_map.put("123-4672", "Adele")
hash_map.put("123-4573", "Michaela")
hash_map.put("123-6574", "Bob")

hash_map.print_map()

# Demonstrating retrieval
print("\nName associated with '123-4570':", hash_map.get("123-4570"))

print("Updating the name for '123-4570' to 'James'")
hash_map.put("123-4570","James")

# Checking if Peter is still there
print("Name associated with '123-4570':", hash_map.get("123-4570"))