7739


pythonの辞書型を使いました。  
今まで線形探索で行っていた単語の検索が異常に早くなり快適です。

ところで、ハッシュについて調べた所、

[code]

     h(x)=x%5 //5はテーブルの行数
    
[/code]

のようなハッシュ関数で振り分けていると分かりました。  
しかし、私がこの前実行したpythonのコードでは単語数が100万語近くありました。  
キーが衝突するかと思いましたが、高速に動作しました。

ここで疑問が２つ湧きました。

**・キーの衝突が無い（少ない？）ということは余りを求める数（上記のハッシュ関数の例では５）はpythonのdict型では可変なのでしょうか？  
  
・キーの数自体が多い場合、キーの保存されている領域を探すために結局時間がかかるように思えるのですが・・・**

実際の実装の中身についてもお願いします

* * *

追記  
回答を読んでいて、もう一つ疑問が生まれました。  
キーは文字列ですよね。  
では、文字列をキーにして、データにアクセスする方法（アドレスを指定する方法）はどうやって実装していますか？

もともとC言語を扱っていたので、データにアクセスするにはアドレスを指定しないといけない気がします


CC BY-SA 3.0
2015-03-10T06:03:33.010
7703
2015-03-11T07:45:25.083
2015-03-11T07:24:23.480
2155
2155
question
python アルゴリズム ハッシュ
pythonの辞書型の実装


> **・キーの衝突が無い（少ない？）ということは余りを求める数（上記のハッシュ関数の例では５）はpythonのdict型では可変なのでしょうか？**

可変です。  
Yoshさんのコメントしているリンク先の回答によれば、初期状態でのスロット数は8で、必要に応じて拡張されます。

> **・キーの数自体が多い場合、キーの保存されている領域を探すために結局時間がかかるように思えるのですが・・・**

キーの保存されている領域を探す必要はありません。  
なぜなら、ハッシュそのものがキーの保存されている領域の位置を示しているからです。

ただし、衝突が多い場合に関してはもちろんそれだけ時間がかかります。

> 回答を読んでいて、もう一つ疑問が生まれました。 キーは文字列ですよね。  
>  では、文字列をキーにして、データにアクセスする方法（アドレスを指定する方法）はどうやって実装していますか？

`hash()`組み込み関数を使えばわかりますが、キー（ハッシュ）は文字列ではありません。整数値です。

[code]

    In [1]: hash("abc")
    Out[1]: 1453079729188098211
    
[/code]

現在のＰｙｔｈｏｎの実装では、文字列からハッシュ（整数値）への変換にはこのような関数が使われています。

[code]

    Py_hash_t
    _Py_HashBytes(const void *src, Py_ssize_t len)
    {
        Py_hash_t x;
        /*
          We make the hash of the empty string be 0, rather than using
          (prefix ^ suffix), since this slightly obfuscates the hash secret
        */
        if (len == 0) {
            return 0;
        }
    
    #ifdef Py_HASH_STATS
        hashstats[(len <= Py_HASH_STATS_MAX) ? len : 0]++;
    #endif
    
    #if Py_HASH_CUTOFF > 0
        if (len < Py_HASH_CUTOFF) {
            /* Optimize hashing of very small strings with inline DJBX33A. */
            Py_uhash_t hash;
            const unsigned char *p = src;
            hash = 5381; /* DJBX33A starts with 5381 */
    
            switch(len) {
                /* ((hash << 5) + hash) + *p == hash * 33 + *p */
                case 7: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
                case 6: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
                case 5: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
                case 4: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
                case 3: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
                case 2: hash = ((hash << 5) + hash) + *p++; /* fallthrough */
                case 1: hash = ((hash << 5) + hash) + *p++; break;
                default:
                    assert(0);
            }
            hash ^= len;
            hash ^= (Py_uhash_t) _Py_HashSecret.djbx33a.suffix;
            x = (Py_hash_t)hash;
        }
        else
    #endif /* Py_HASH_CUTOFF */
            x = PyHash_Func.hash(src, len);
    
        if (x == -1)
            return -2;
        return x;
    }
    
[/code]

<https://github.com/python/cpython/blob/c7688b44387d116522ff53c0927169db45969f0e/Python/pyhash.c#L145-L191>


CC BY-SA 3.0
2015-03-10T14:17:39.697
7739
2015-03-11T07:45:25.083
2015-03-11T07:45:25.083
3639
3639
7703
answer


ハッシュテーブル自体はCの配列です。ハッシュ関数はkeyから、その配列のインデックスを求めるために使います。配列の要素へのアクセスは、先頭だろうと、真ん中だろうと、最後だろうと同じ時間でできるので速いわけです。

もちろんkeyの数が増えてくれば、インデックスの衝突が増えてアクセスが遅くなります。したがって、ハッシュテーブルのサイズは適宜大きくなります。


CC BY-SA 3.0
2015-03-10T14:32:47.723
7740
2015-03-10T14:32:47.723
3605
7703
answer