解锁数据存储利器！Python算法解析：掌握哈希表的娴熟应用，高效数据处理！

测试开发囤货

发布于 2023-08-08 09:30:02

1570

发布于 2023-08-08 09:30:02

文章被收录于专栏：测试开发囤货

解锁数据存储利器！Python算法解析：掌握哈希表的娴熟应用，高效数据处理！

哈希表

哈希表是一种常用的数据结构，它通过哈希函数将键映射到存储位置，从而实现高效的数据访问和插入操作。

哈希表的原理和基本操作：

哈希函数：哈希表使用哈希函数将键转换为索引，这样可以快速确定键对应的存储位置。
存储结构：哈希表通常使用数组作为底层存储结构，每个位置称为哈希桶（bucket）。每个桶可以存储一个键值对或者多个键值对（通过链表或其他数据结构实现）。
基本操作：

插入（Insert）：根据哈希函数计算键的索引，并将键值对存储在对应的桶中。
查找（Lookup）：根据哈希函数计算键的索引，找到对应的桶，并在桶中查找给定键的值。
删除（Delete）：根据哈希函数计算键的索引，找到对应的桶，并在桶中删除给定键的键值对。

示例

下面是用Python实现哈希表数据结构的示例：

class HashTable:
    def __init__(self):
        self.size = 10  # 哈希表的大小
        self.buckets = [[] for _ in range(self.size)]  # 哈希桶，使用列表实现

    def _hash(self, key):
        hash_value = 0
        for char in str(key):
            hash_value += ord(char)
        return hash_value % self.size

    def insert(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                bucket[i] = (key, value)  # 如果键已存在，则更新值
                return
        bucket.append((key, value))  # 键不存在，则添加键值对

    def lookup(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        for existing_key, value in bucket:
            if existing_key == key:
                return value
        return None  # 键不存在

    def delete(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                del bucket[i]  # 删除键值对
                return

# 测试示例
hash_table = HashTable()
hash_table.insert("apple", 5)
hash_table.insert("banana", 7)
hash_table.insert("orange", 2)

print(hash_table.lookup("apple"))  # 输出：5
print(hash_table.lookup("banana"))  # 输出：7
print(hash_table.lookup("orange"))  # 输出：2
print(hash_table.lookup("pear"))  # 输出：None

hash_table.delete("banana")
print(hash_table.lookup("banana"))  # 输出：None

在这个示例中，我们定义了一个HashTable类，包含了插入、查找和删除等基本操作的方法。哈希表使用列表作为哈希桶，并使用哈希函数将键映射到索引。

可视化

现在让我们展示哈希表的内部结构和操作过程，以加深对哈希表的理解。

以下是一个示意图，展示了哈希表内部的结构和操作过程：

哈希表:
bucket[0]: []
bucket[1]: [('orange', 2)]
bucket[2]: []
bucket[3]: []
bucket[4]: []
bucket[5]: []
bucket[6]: []
bucket[7]: []
bucket[8]: []
bucket[9]: [('apple', 5)]

插入键值对 ('apple', 5)：
bucket[0]: []
bucket[1]: [('orange', 2)]
bucket[2]: []
bucket[3]: []
bucket[4]: []
bucket[5]: []
bucket[6]: []
bucket[7]: []
bucket[8]: []
bucket[9]: [('apple', 5)]

插入键值对 ('banana', 7)：
bucket[0]: []
bucket[1]: [('orange', 2)]
bucket[2]: []
bucket[3]: []
bucket[4]: []
bucket[5]: []
bucket[6]: []
bucket[7]: []
bucket[8]: []
bucket[9]: [('apple', 5), ('banana', 7)]

插入键值对 ('orange', 2)：
bucket[0]: []
bucket[1]: [('orange', 2)]
bucket[2]: []
bucket[3]: []
bucket[4]: []
bucket[5]: []
bucket[6]: []
bucket[7]: []
bucket[8]: []
bucket[9]: [('apple', 5), ('banana', 7), ('orange', 2)]

查找键 'apple' 的值：5
查找键 'banana' 的值：7
查找键 'orange' 的值：2
查找键 'pear' 的值：None

删除键 'banana'：
bucket[0]: []
bucket[1]: [('orange', 2)]
bucket[2]: []
bucket[3]: []
bucket[4]: []
bucket[5]: []
bucket[6]: []
bucket[7]: []
bucket[8]: []
bucket[9]: [('apple', 5), ('orange', 2)]

查找键 'banana' 的值：None

通过这个示意图，你可以看到哈希表内部的桶和键值对的存储情况，并理解插入、查找和删除操作对哈希表的影响。