How to write a hash lookup algorithm in Python?

How to write a hash search algorithm in Python?

Hash search algorithm, also known as hash search algorithm, is a data search method based on hash table. Compared with traditional search algorithms such as linear search and binary search, the hash search algorithm has higher search efficiency. In Python, we can use a dictionary to implement a hash table and then implement a hash lookup.

The basic idea of ​​the hash search algorithm is to convert the keyword to be searched into an index value through a hash function, and then search for the corresponding data in the hash table based on the index value. In a hash table, each index value corresponds to a bucket, and each bucket stores one or more keywords. Conflicts occur when multiple keywords map to the same index value. In order to resolve conflicts, a common method is to use the chain address method to link conflicting keywords in a linked list.

The following is an example of a simple hash lookup algorithm written in Python:

class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [[] for _ in range(self.size)]  # 使用列表作为哈希表的桶
    
    def _hash_function(self, key):
        return key % self.size  # 哈希函数采用取余方式
    
    def insert(self, key, value):
        index = self._hash_function(key)
        self.table[index].append((key, value))  # 将关键字和值作为一个元组插入哈希表桶中
    
    def search(self, key):
        index = self._hash_function(key)
        for item in self.table[index]:
            if item[0] == key:
                return item[1]  # 返回关键字对应的值
        return None  # 若关键字不存在，则返回None

# 示例用法
hash_table = HashTable()
hash_table.insert(1, 'apple')
hash_table.insert(2, 'banana')
hash_table.insert(11, 'orange')

print(hash_table.search(1))  # 输出: apple
print(hash_table.search(2))  # 输出: banana
print(hash_table.search(3))  # 输出: None
print(hash_table.search(11)) # 输出: orange

In the above example, we define a hash table class HashTable, containing Hash functions, insertion and search operations. The hash function uses a simple remainder method to convert the keyword into the corresponding index value. The insertion operation inserts the key and value as a tuple into the bucket corresponding to the index. The search operation traverses the bucket of the corresponding index, finds the tuple matching the keyword, and returns the corresponding value. If the keyword does not exist, None is returned.

Through the above example, we can see the simple implementation of the hash search algorithm. In practice, more complex hash functions and conflict resolution methods can be selected based on specific needs and data characteristics. At the same time, operations such as dynamic expansion of the hash table can also be performed to improve search efficiency.

The above is the detailed content of How to write a hash lookup algorithm in Python?. For more information, please follow other related articles on the PHP Chinese website!