Pythonでハッシュテーブルを実装する方法

ハッシュ テーブルは、コンピューター サイエンスで広く使用されている重要なデータ構造です。大量のデータ内の特定の要素を迅速に検索、挿入、削除できます。 Python を使用してハッシュ テーブルを実装すると、ハッシュ テーブルの内部動作メカニズムを深く理解できるだけでなく、プログラミング能力も向上します。この記事では、Python でハッシュ テーブルを実装する方法を詳しく説明します。

1. ハッシュ テーブルとは

ハッシュ テーブルはハッシュ テーブルとも呼ばれ、キーと値の格納方法です。キーを値のインデックス位置にマッピングすることでデータにアクセスします。その基本操作には、挿入、削除、検索が含まれます。

ハッシュ テーブルの中心的な考え方は、ハッシュ関数を使用して各キーを固定サイズのテーブルにマップすることです。ハッシュ関数は、任意の長さの入力メッセージを固定長の出力に変換する関数です。一般的なハッシュ関数には、MD5、SHA1、SHA256 などが含まれます。

2. ハッシュ テーブルの実装

Python を使用して、挿入、削除、検索などのハッシュ テーブルの基本操作を含む単純なハッシュ テーブルを実装します。

最初に、ハッシュ テーブルのノードを表す Node クラスを定義します。各ノードにはキーと値が含まれています。

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None

次に HashTable クラスを定義し、Python のリストを使用して基礎となるデータ構造を実装します。キーと値のペアを挿入するときは、キーに基づいてハッシュ値を計算し、キーと値のペアをハッシュ テーブル内の対応する場所に保存する必要があります。

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

上記のコードでは、hash_func メソッドはキーに基づいてハッシュ値を計算し、insert メソッドはキーと値のペアをハッシュ テーブル内の対応する位置に挿入し、search メソッドは値に基づいて検索します。キーに基づいて値を検索し、対応するキーと値のペアを削除します。

3. ハッシュ テーブルをテストする

次に、上で実装したハッシュ テーブルをテストします。

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

上記のコードでは、HashTable オブジェクト ht を作成し、3 つのキーと値のペアを ht に挿入しました。次に、検索メソッドを使用してキー「apple」、「banana」、「orange」を持つ値を検索し、キー「apple」を持つキーと値のペアを削除します。最後に、キー「apple」を持つ値を探します。これは None を返します。

4. 概要

この記事では、Python でハッシュ テーブルを実装する方法を紹介します。ハッシュ テーブルのノードを表す Node クラスを定義し、ハッシュ テーブルを表す HashTable クラスを定義し、挿入、削除、検索などのハッシュ テーブルの基本操作を実装しました。ハッシュ テーブルを実装することで、ハッシュ テーブルの内部動作メカニズムを深く理解し、プログラミング能力を向上させることができます。

以上がPythonでハッシュテーブルを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。