辞書とハッシュテーブルの空間の複雑さ

Question

私は明らかにしたい辞書とハッシュテーブルについていくつかの混乱があります。私は現在の辞書と現在のPythonの実行のハッシュの現在の出力を持っています。

Dict = dict() 
print(hash('a')) 
print(hash('b')) 
print(hash('c')) 
Dict['a'] = 1 
Dict['b'] = 2 
Dict['c'] = 3 
print(Dict) 

ハッシュテーブルは、単にハッシュは、ハッシュテーブルのインデックスである配列である私の知識にとても

1714333803 
1519074822 
1245896149 
{'a': 1, 'c': 3, 'b': 2} 

の出力を持っています。例えば、 'a'は1714333803のハッシュを持っていたので、私のハッシュテーブルのインデックス1714333803は 'a'という値を持っています。だから、ハッシュテーブルのインデックスの数と、ハッシュ関数が答えを生成する方法を混同していますか？モジュラスを使用し、固定範囲のインデックスを持っていますか？与えられた辞書のプリントは{'a': 1, 'c': 3, 'b': 2}を出力するので、実際にはそれが出力されていると仮定するのは正しいですが、辞書は実際には1714333803のインデックスを少なくとも1つ配列しています。それは宇宙の無駄です。また、ハッシュテーブルの場合、値のないインデックスには何が含まれますか？

Answer 1

dictの実際のサイズは実装によって異なりますが、あなたのケースではおそらく8です。これはどのように機能しますか？

dict（または一般にハッシュマップ）の動作原理は、すべてのキーの数値ハッシュを計算することです。あなたの場合、それは例えばhash("a") == 1714333803です。現在、ハッシュは直接インデックスとして使用されていません。代わりに、辞書のサイズにマップされます。

これを行う簡単な方法は、モジュロ（%）です。 dictのサイズが8であるとします。その後、hash("a") % 8 == 1714333803 % 8 == 3。あなたの商品は実際には4位にあります。アイテムは配列の外側にインデックスを持つことはできません。

ここでは、ハッシュの衝突のような複雑なものがいくつかあります。たとえば、別のアイテムにハッシュ98499がある場合、そのもは3にマップされます。この場合、異なるインデックスを選択する衝突解決戦略があります。

あなたのdictはなぜサイズ8ですか？これはdefault size in pythonなのでdictのgetが小さすぎる場合は、サイズを変更する必要があります。アレイとは対照的に、これはdictが実際にいっぱいになる前、つまりtwo thirds fillingに完了します。これは、ハッシュの衝突を減らすために行われます.dictが99％いっぱいになると、衝突が実際に保証されます。サイズ8のdictの場合は、サイズ変更する前に5〜6個の項目、つまりdoubles its capacity〜16を入力する必要があります。