algorithm - 如何为 O(1) 中的一系列数字创建一个返回相同值的函数？

Question

例如

H: [0, 20] -> "a"
H: [21: 25] -> "y"
H: [26: 132] -> "z"

无论我输入了多少个范围，我怎样才能使 H 函数花费恒定时间(以及插入的恒定时间)？这可能吗？

Answer 1

是的，只需使用查找表。使用您希望由范围表示的值为每个范围初始化表，然后返回索引处的值。像这样:

const char *lookup(int index)
{
    static const char *table[] = {
        "foo",
        "foo",
        "foo",
        "foo",
        "bar",
        "bar",
        "quirk",
        "quirk",
        "quirk"
    };
    return table[index];
}

对于 [0, 3] 范围返回 "foo"，对于 [4, 5] 和 "quirk" 范围 [6, 8]。