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"))