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.

1. What is a hash table

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.

2. Implementing a hash table

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.

3. Test the hash table

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.

4. Summary

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!