7-1 构造散列表

散列表（Hash Table）是一种数据结构，它通过把元素的关键字映射到一个位置来实现元素的快速查找。这个映射函数叫做哈希函数，它将关键字映射到散列表的数组索引上。

构造散列表的基本步骤如下：

1. 定义散列表的大小，通常为质数，例如10007。

2. 定义哈希函数，它将关键字映射到散列表的数组索引上。常见的哈希函数有取模法、乘法哈希、平方取中法等。

3. 初始化散列表，将每个数组元素设为 NULL 或者一个特殊值。

4. 插入元素时，根据哈希函数计算出数组索引，然后将元素插入到该位置。如果该位置已经被占用，则使用冲突解决方法，例如开放地址法或链表法。

5. 查找元素时，根据哈希函数计算出数组索引，然后在该位置查找。如果该位置的元素不是要查找的元素，则使用相应的冲突解决方法查找下一个位置。

6. 删除元素时，根据哈希函数计算出数组索引，然后将该位置的元素删除或者标记为删除状态。

例如，以下是一个使用取模法和链表法解决冲突的散列表的示例代码：

class ListNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class HashTable:
    def __init__(self):
        self.size = 10007
        self.table = [None] * self.size

    def hash_function(self, key):
        return key % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        node = self.table[index]
        while node:
            if node.key == key:
                node.value = value
                return
            node = node.next
        new_node = ListNode(key, value)
        new_node.next = self.table[index]
        self.table[index] = new_node

    def get(self, key):
        index = self.hash_function(key)
        node = self.table[index]
        while node:
            if node.key == key:
                return node.value
            node = node.next
        return None

    def remove(self, key):
        index = self.hash_function(key)
        node = self.table[index]
        prev = None
        while node:
            if node.key == key:
                if prev:
                    prev.next = node.next
                else:
                    self.table[index] = node.next
                return
            prev = node
            node = node.next

这是一个简单的散列表实现，可以用来存储键值对。其中，哈希函数使用取模法，插入元素时使用链表法解决冲突。