c - 从随机 id 中检索元素的最佳算法

Question

我目前正在尝试找到适合我的情况的最佳数据结构/算法:

我收到单个唯一的随机 ID (uint32_t)，并创建一个与每个新 ID 关联的元素。

1. 我需要从 id 中检索元素。

2. 我还需要按创建顺序从任何元素(甚至 id)访问下一个和上一个元素。创建的顺序主要取决于 current 元素，它始终可以在旁边访问，因此新元素应该是它的下一个。

这是一个例子:

(12) <-> (5) <-> (8) <-> (1)
 ^                        ^
 '------------------------'

如果我假设当前元素是 (8) 并且创建了一个新元素 (3)，它应该如下所示:

(12) <-> (5) <-> (8) <-> (3) <-> (1)
 ^                                ^
 '--------------------------------'

需要考虑的重要一点是插入、删除和搜索的发生频率几乎相同(高)。不完全确定有多少元素会同时存在，但我会说最多 ~1000。

了解所有这些后，我考虑使用带有 id 作为排序键的 AVL，同时保留上一个和下一个元素。

在C语言中，是这样的:

struct element {
  uint32_t id;
  /* some other fields */
  struct element *prev;
  struct element *next;      
}

struct node {
   struct element *elt;
   struct node *left;
   struct node *right;
};

static struct element* current;

另一个想法可能是使用 HashMap ，但我需要找到正确的哈希函数。不完全确定它在实践中总能在如此数量的元素上击败 AVL。无论如何，这取决于哈希函数。

对于这种情况，AVL 是个好主意还是我应该考虑其他方法？

谢谢!

PS:我不是一个试图让你做作业的学生，​​我只是想开发一个简单的窗口管理器(只是为了好玩)。

Answer 1

您正在寻找 java a LinkedHashMap 中调用的一些变体

这基本上是 hash-table 的组合和一个(双向)linked list .

链表中的元素按所需顺序排列。在已知位置插入元素(假设您有指向正确位置的指针)在 O(1) 中完成。删除也一样。链表包含按所需顺序排列的所有元素。

第二个数据结构是散列图(或 TreeMap )。此数据结构从键(您的唯一 ID)映射到链表中的指针。这样，给定一个 id - 您可以快速找到它在链接列表中的位置，然后您可以从那里轻松访问下一个和上一个元素。

用于插入的高级伪代码:

insert(x, v, y): //insert key=x value=v, after element with key=y
   if x is in hash-table:
        abort
   p = find(hash-table,y) //p is a pointer
   insert_to_list_after(x,v,p) //insert key=x,value=v right after p
   add(hash-table,x,p) //add x to the hash-table, and make it point to p.

用于搜索的高级伪代码:

search(x):
    if x is not in hash-table:
        abort
    p = find(hash-table,x)
    return p->value;

删除应该与插入非常相似(并且时间复杂度相同)。

请注意，也很容易找到 x 之后的元素:

p = find(hash-table,x)
if (p != NULL && p->next != NULL):
    return p->next->value