マップと辞書

MicroPython の辞書とマップは、オープンアドレス法と線形探索法と呼ばれる手法を使用しています。この章では、これら両方の手法について詳しく説明します。

オープンアドレス法

衝突を解決するために オープンアドレス法 が使用されます。衝突は非常によく起こる事象で、2 つの項目がたまたま同じスロットや位置にハッシュされたときに発生します。例えば、次のようなハッシュ構成が与えられたとします。

../_images/collision.png

スロット 0 を 70 で埋める要求があった場合、スロット 0 は空ではないため、オープンアドレス法はこの要求を処理するために辞書内の次の利用可能なスロットを探します。この代替位置を逐次的に探す処理を プロービング と呼びます。プロービングのアルゴリズムにはいくつかの種類がありますが、MicroPython は次のセクションで説明する線形探索法を使用します。

線形探索法

線形探索法は、辞書内の利用可能なアドレスやスロットを見つけるための手法の 1 つです。MicroPython では、オープンアドレス法とともに使用されます。上記で説明した要求を処理する際、線形探索法は他のプロービングアルゴリズムとは異なり、プローブ間の間隔を 1 に固定すると仮定します。したがって、この要求は、項目を次の空きスロット、この例ではスロット 4 に配置することで処理されます。

../_images/linprob.png

辞書内の項目を検索する際にも、同じ手法、すなわちオープンアドレス法と線形探索法が使用されます。データ項目 33 を検索したいとします。計算されるハッシュ値は 2 になります。スロット 2 を見ると 33 が見つかります。この時点で True を返します。70 の検索はかなり異なります。挿入時に衝突があったためです。したがって、計算されるハッシュ値は 0 で、そこには現在 44 が保持されています。単に False を返すのではなく、項目 70 が見つかるか、空きスロットに遭遇するまで、位置 1 から逐次的に検索を行います。これがハッシュにおけるルックアップの一般的な実行方法です。

// not yet found, keep searching in this table
pos = (pos + 1) % set->alloc;

if (pos == start_pos) {
    // search got back to starting position, so index is not in table
    if (lookup_kind & MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
        if (avail_slot != NULL) {
            // there was an available slot, so use that
            set->used++;
            *avail_slot = index;
            return index;
        } else {
            // not enough room in table, rehash it
            mp_set_rehash(set);
            // restart the search for the new element
            start_pos = pos = hash % set->alloc;
        }
    }
} else {
     return MP_OBJ_NULL;
}