Home > Article > Backend Development > How to implement a hash table in Python
Hash table is an important data structure widely used in computer science. It can quickly find, insert or delete a specific element in large amounts of data. Using Python to implement a hash table can not only provide you with a deep understanding of the internal working mechanism of a hash table, but also enhance your programming abilities. In this article, we will detail how to implement a hash table in Python.
A hash table is also called a hash table, which is a key-value storage method. It accesses data by mapping key to an index position of value. Its basic operations include insertion, deletion and search.
The core idea of a hash table is to use a hash function to map each key to a fixed-size table. A hash function is a function that converts an input message of arbitrary length into a fixed-length output. Common hash functions include MD5, SHA1, SHA256, etc.
We use Python to implement a simple hash table, including basic operations of the hash table, such as insertion, deletion and search.
First define a Node class to represent the node of the hash table. Each node contains a key and a value.
class Node: def __init__(self, key, val): self.key = key self.val = val self.next = None
Next define a HashTable class, and we use Python’s list to implement the underlying data structure. When inserting a key-value pair, we need to calculate the hash value based on the key and store the key-value pair at the corresponding location in the hash table.
class HashTable: def __init__(self): self.size = 100 self.table = [None] * self.size def hash_func(self, key): return sum([ord(c) for c in key]) % self.size def insert(self, key, value): hash_value = self.hash_func(key) if self.table[hash_value] is None: self.table[hash_value] = Node(key, value) else: cur = self.table[hash_value] while cur.next is not None: cur = cur.next cur.next = Node(key, value) def search(self, key): hash_value = self.hash_func(key) if self.table[hash_value] is None: return None else: cur = self.table[hash_value] while cur is not None: if cur.key == key: return cur.val else: cur = cur.next return None def delete(self, key): hash_value = self.hash_func(key) if self.table[hash_value] is None: return elif self.table[hash_value].key == key: self.table[hash_value] = self.table[hash_value].next else: cur = self.table[hash_value] while cur.next is not None: if cur.next.key == key: cur.next = cur.next.next return else: cur = cur.next
In the above code, the hash_func method calculates the hash value based on the key, the insert method inserts the key-value pair into the corresponding position in the hash table, the search method searches for the value based on the key, and the delete method searches for the value based on the key. Delete the corresponding key-value pair.
Next we test the hash table implemented above.
ht = HashTable() ht.insert('apple', 2.5) ht.insert('banana', 1.3) ht.insert('orange', 0.7) print(ht.search('apple')) # 2.5 print(ht.search('banana')) # 1.3 print(ht.search('orange')) # 0.7 print(ht.search('lemon')) # None ht.delete('apple') print(ht.search('apple')) # None
In the above code, we created a HashTable object ht and inserted three key-value pairs into ht. Then, we use the search method to find values with keys 'apple', 'banana' and 'orange', and delete a key-value pair with key 'apple'. Finally, we look for the value with key 'apple', which should return None.
This article introduces how to implement a hash table in Python. We defined a Node class to represent a node of the hash table, and then defined a HashTable class to represent the hash table, and implemented the basic operations of the hash table, such as insertion, deletion, and search. By implementing a hash table, we can deeply understand the internal working mechanism of the hash table and enhance our programming capabilities.
The above is the detailed content of How to implement a hash table in Python. For more information, please follow other related articles on the PHP Chinese website!