マップと辞書¶

MicroPython の辞書とマップは、オープンアドレッシングとリニアプロービングと呼ばれる技法を使っています。この章では、この2つの手法の詳細を説明します。

オープンアドレッシング¶

オープンアドレッシングは、衝突を解決するために使用されます。衝突は非常によく起こる現象で、2つのアイテムが偶然同じスロットや場所にハッシュされたときに起こります。たとえば、次のようなハッシュ設定があるとします:

スロット 0 を 70 で満たす要求があった場合、スロット 0 は空ではないので、オープンアドレッシングは、この要求をサービスするために、辞書内の次の利用可能なスロットを見つける。このように代替となる場所を逐次的に探すことを プロービング と呼びます。いくつかのシーケンスプロービングアルゴリズムがありますが、MicroPython は次の章で説明するリニアプロービングを採用しています。

リニアプロービング¶

リニアプロービングは、辞書で利用可能なアドレスやスロットを見つけるための方法の1つです。MicroPython では、オープンアドレッシングと一緒に使います。上記の要求を処理するために、他のプロービングアルゴリズムとは異なり、リニアプロービングはプローブ間の固定間隔を 1 と仮定しています。したがって、このリクエストは、次の空きスロット(この例ではスロット4)にアイテムを配置することで処理されることになります:

辞書の項目を検索する場合にも、オープンアドレッシングとリニアプロービングという同じ方法が使われます。たとえば、データ項目 33 を検索するとします。計算されたハッシュ値は 2 です。スロット2を見ると 33 が見つかり、この時点で True を返します。70を検索する場合は、挿入時に衝突が発生していたため、まったく異なります。したがって、ハッシュ値を計算すると、現在 44 を保持している 0 になります。単純に False を返すのではなく、ポイント 1 から順に、アイテム70が見つかるか、空きスロットに出会うまで、順次検索を実行します。これがハッシュの検索を行う一般的な方法です:

// まだ見つかっていないため、このテーブルで検索を続ける
pos = (pos + 1) % set->alloc;

if (pos == start_pos) {
    // 検索が開始位置に戻ったため、インデックスがテーブル内にない
    if (lookup_kind & MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
        if (avail_slot != NULL) {
            // 空いている枠があったので、そちらを使用する
            set->used++;
            *avail_slot = index;
            return index;
        } else {
            // テーブルの空きがないので、それをリハッシュする
            mp_set_rehash(set);
            // 新しい要素の検索を再開する
            start_pos = pos = hash % set->alloc;
        }
    }
} else {
     return MP_OBJ_NULL;
}