以下约束的最佳数据结构？

Question

以下是我需要的数据结构的一些约束.看起来没有一个共同的数据结构(我会提到我在下面想到的那些)都很适合这些.任何人都可以建议一个我可能没有想到的吗？

1. 我需要能够通过无符号整数键执行查找.
2. 要存储的项目是用户定义的结构.
3. 这些指数很稀疏,通常极其如此.常规数组已经出局.
4. 每个指数的频率将具有非均匀分布,小指数比大指数更频繁.
5. N通常很小,可能不大于5或10,但我不想太依赖它,因为它可能偶尔会大得多.
6. 常数术语很重要.当N很小时,我需要非常快速的查找.我已经尝试过通用哈希表,根据经验,它们太慢了,即使N = 1,也就是没有冲突,可能是因为涉及的间接量很大.但是,我会接受有关利用所提到的其他约束的专用哈希表的建议.
7. 只要检索时间很快,插入时间就不重要了.即使O(N)插入时间也足够好.
8. 空间效率并不是非常重要,但重要的是不要只使用常规数组.

Answer 1

当 N 很小时，以键 + 值作为有效负载的简单数组或单链表非常有效。即使当 N 变大时它不是最好的。

您获得 O(N) 查找时间，这意味着查找需要k * N时间。AO(1) 查找需要恒定的K时间。因此，您可以使用 O(N)获得更好的N < K/k性能。这里k非常小，因此您可以得到有趣的 N 值。请记住，Big O 表示法仅描述大 Ns 的行为，而不是您所追求的。对于小桌子

void *lookup(int key_to_lookup)
{
  int n = 0;
  while (table_key[n] != key_to_lookup)
    n++;
  return table_data[n];
}

很难被击败。

对哈希表、平衡树和简单数组/链表进行基准测试，看看它们分别在哪个 N 值时开始变得更好。然后你就会知道哪个更适合你。

我差点忘了：将经常访问的键保留在数组的开头。根据您的描述，这意味着要对其进行排序。