ハッシュ テーブルは、コンピューター サイエンスで広く使用されている重要なデータ構造です。大量のデータ内の特定の要素を迅速に検索、挿入、削除できます。 Python を使用してハッシュ テーブルを実装すると、ハッシュ テーブルの内部動作メカニズムを深く理解できるだけでなく、プログラミング能力も向上します。この記事では、Python でハッシュ テーブルを実装する方法を詳しく説明します。
ハッシュ テーブルはハッシュ テーブルとも呼ばれ、キーと値の格納方法です。キーを値のインデックス位置にマッピングすることでデータにアクセスします。その基本操作には、挿入、削除、検索が含まれます。
ハッシュ テーブルの中心的な考え方は、ハッシュ関数を使用して各キーを固定サイズのテーブルにマップすることです。ハッシュ関数は、任意の長さの入力メッセージを固定長の出力に変換する関数です。一般的なハッシュ関数には、MD5、SHA1、SHA256 などが含まれます。
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 メソッドは値に基づいて検索します。キーに基づいて値を検索し、対応するキーと値のペアを削除します。
次に、上で実装したハッシュ テーブルをテストします。
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 を返します。
この記事では、Python でハッシュ テーブルを実装する方法を紹介します。ハッシュ テーブルのノードを表す Node クラスを定義し、ハッシュ テーブルを表す HashTable クラスを定義し、挿入、削除、検索などのハッシュ テーブルの基本操作を実装しました。ハッシュ テーブルを実装することで、ハッシュ テーブルの内部動作メカニズムを深く理解し、プログラミング能力を向上させることができます。
以上がPythonでハッシュテーブルを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。