ハッシュテーブル、空でないスロットに既にキーが含まれています。奇数データ値が新しいデータ値に置き換えられます。

Question

私は、Pythonでハッシュテーブルを学習しています。

ハッシュ関数が始まるとき、空の "マップ"ハッシュを生成する必要があります。なぜ "空でないスロットにはすでにキーが含まれていますが、奇数データ値は新しいデータ値に置き換えられます"次の空きスロットとそこに格納し、なぜ置き換えますか？

https://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html

ハッシュ関数は、単純な剰余方法を実装します。衝突解決技法は、「プラス1」リハッシュ機能を備えた線形プロービングである。 put関数（リスト3を参照）は、キーがself.slotsにすでに存在していない限り、最終的に空のスロットが存在すると想定しています。元のハッシュ値を計算し、そのスロットが空でない場合、空のスロットが発生するまで再ハッシュ関数を反復します。空でないスロットに既にキーが含まれている場合は、古いデータ値が新しいデータ値に置き換えられます。空きスロットが残っていない状況に対処することが課題です。

Answer 1

まず、我々はhash value、keyとvalueを区別する必要があります。

Hash valueは、ハッシュテーブル内のスロットのIDであり、ハッシュ関数によって生成されます。

Keyは、マッピング元のデータです。

valueは、マップするデータです。

したがって、マッピングとは、ある値を参照する一意のキーがあり、その値が必ずしも明確ではないことを意味します。

あなたはプット機能は、次の操作を行いますkeyとvalueで新しいスロットを追加しよう：

それはリストにし、このIDを持つスロットがある場合は、スロットのIDを取得するには、キーをハッシュ

1-見つかったスロットは空ではありませんが、そのキーは新しいキーと同じではありません。つまり、2つの異なるキーが同じhash valueを持つことを意味します。このため、これは挿入が正常に行われます。衝突とみなされ、送信したリンクに記載されている方法で解決されます。

2見つかったスロットは空ではありませんが、そのキーは新しいキーと同じです。つまり、古いスロットvalueを新しいスロットに置き換えます。

例：次に、あなたがhash["foo"] = 10を挿入しようとした、これはキー（foo）をハッシュし、ハッシュテーブル（リスト）にそのスロットのIDを検索します

"foo": 5 
"bar": 7 

、および： ハッシュは、これらのスロットが含まれている場合それはまた、キーfooとスロットが存在することがわかりますので、値を置き換えますとハッシュテーブルは次のようになります：

"foo": 10 
"bar": 7 

しかし、あなたはhash["abc"] = 7を挿入しようとした場合には、第キーabcをハッシュし、hash valueがabcと異なるキーを持つ空でないスロットにマッピングしている場合、この場合、put関数はこれを衝突とみなし、別の空のスロットを見つけようとします。