PYTHON のハッシュマップ

ハッシュマップはインデックス付きのデータ構造です。ハッシュマップはハッシュ関数バケットまたはスロットの配列へのキーを使用してインデックスを計算します。その値は、対応するインデックスを持つバケットにマップされます。キーは一意であり、不変です。ハッシュマップは、中に保管されているもののラベルが付いている引き出しがあるキャビネットと考えてください。たとえば、ユーザー情報を保存する場合、電子メールをキーとみなして、そのユーザーに対応する名、姓などの値をバケットにマッピングできます。

ハッシュ関数は、ハッシュマップの実装の中核です。キーを受け取り、それをバケットリスト内のバケットのインデックスに変換します。理想的なハッシュでは、キーごとに異なるインデックスが生成されるはずです。ただし、衝突が発生する可能性があります。ハッシュによって既存のインデックスが得られる場合、リストを追加するか再ハッシュすることで、複数の値にバケットを使用するだけで済みます。

Python では、辞書はハッシュマップの例です。検索を最適化するためにそのようなデータ構造を構築およびカスタマイズする方法を学ぶために、ハッシュマップの実装を最初から見ていきます。

ハッシュマップの設計には次の機能が含まれます。

set_val(キー, 値): キーと値のペアをハッシュマップに挿入します。値がハッシュマップに既に存在する場合は、値を更新します。
get_val(キー): 指定されたキーがマップされている値を返します。このマップにキーのマッピングが含まれていない場合は、レコードが見つかりませんでした。
delete_val(キー): ハッシュマップにキーのマッピングが含まれている場合、特定のキーのマッピングを削除します。

以下は実装です。

Python3

class> HashTable:> > # Create empty bucket list of given size> > def> __init__(> self> , size):> > self> .size> => size> > self> .hash_table> => self> .create_buckets()> > def> create_buckets(> self> ):> > return> [[]> for> _> in> range> (> self> .size)]> > # Insert values into hash map> > def> set_val(> self> , key, val):> > > # Get the index from the key> > # using hash function> > hashed_key> => hash> (key)> %> self> .size> > > # Get the bucket corresponding to index> > bucket> => self> .hash_table[hashed_key]> > found_key> => False> > for> index, record> in> enumerate> (bucket):> > record_key, record_val> => record> > > # check if the bucket has same key as> > # the key to be inserted> > if> record_key> => => key:> > found_key> => True> > break> > # If the bucket has same key as the key to be inserted,> > # Update the key value> > # Otherwise append the new key-value pair to the bucket> > if> found_key:> > bucket[index]> => (key, val)> > else> :> > bucket.append((key, val))> > # Return searched value with specific key> > def> get_val(> self> , key):> > > # Get the index from the key using> > # hash function> > hashed_key> => hash> (key)> %> self> .size> > > # Get the bucket corresponding to index> > bucket> => self> .hash_table[hashed_key]> > found_key> => False> > for> index, record> in> enumerate> (bucket):> > record_key, record_val> => record> > > # check if the bucket has same key as> > # the key being searched> > if> record_key> => => key:> > found_key> => True> > break> > # If the bucket has same key as the key being searched,> > # Return the value found> > # Otherwise indicate there was no record found> > if> found_key:> > return> record_val> > else> :> > return> 'No record found'> > # Remove a value with specific key> > def> delete_val(> self> , key):> > > # Get the index from the key using> > # hash function> > hashed_key> => hash> (key)> %> self> .size> > > # Get the bucket corresponding to index> > bucket> => self> .hash_table[hashed_key]> > found_key> => False> > for> index, record> in> enumerate> (bucket):> > record_key, record_val> => record> > > # check if the bucket has same key as> > # the key to be deleted> > if> record_key> => => key:> > found_key> => True> > break> > if> found_key:> > bucket.pop(index)> > return> > # To print the items of hash map> > def> __str__(> self> ):> > return> ''.join(> str> (item)> for> item> in> self> .hash_table)> hash_table> => HashTable(> 50> )> # insert some values> hash_table.set_val(> '[email protected]'> ,> 'some value'> )> print> (hash_table)> print> ()> hash_table.set_val(> '[email protected]'> ,> 'some other value'> )> print> (hash_table)> print> ()> # search/access a record with key> print> (hash_table.get_val(> '[email protected]'> ))> print> ()> # delete or remove a value> hash_table.delete_val(> '[email protected]'> )> print> (hash_table)>

出力：