c - 实现条目超时的 C 哈希表的最有效方法是什么？

Question

我目前正在开发一个哈希表作为数据库数据结构，它可能包含大量元素，并且必须尽可能高效(特别是在添加新元素和更新现有元素的操作上) 。 我还被迫只使用 C(避免使用 C++ 或其他具有现有类或结构的语言，这些类或结构在这种情况下确实有帮助)。

我需要开发的是一个带有链接列表的哈希表，其中每个条目都有一个超时(比如说几分钟)，之后它应该自动删除自己(或者，作为替代方案，旧条目应该是“垃圾”在某个时间点收集”，因为元素可能会以非常快的速度添加，并且我不想为太旧的条目使用太多内存)。

我正在考虑向哈希表的每个条目添加一个计时器字段:

struct HTnode {
    // Hash table entry ID
    long int id;
    
    // Pointer to the next element of the linked list (when hash is the same for two different IDs)
    struct STnode * next;
    
    // Other fields...

    // Timer for each entry
    timer_t entryTimer;
};

然后，当添加新条目时，启动计时器(该项目仅在 Linux 上运行，这就是我考虑使用 timer_t 的原因 - 此示例代码中不执行错误检查为了简洁起见):

struct sigevent entryTimerEvent;
struct itimerspec entryTimerTs;

// Allocate a new entry for a given id (struct HTnode *entry)
// ...

memset(&entryTimerEvent,0,sizeof(entryTimerEvent));

// entryDeleter() is a function deleting the current entry from the hash table
entryTimerEvent.sigev_notify_function=entryDeleter;
entryTimerEvent.sigev_notify=SIGEV_THREAD;

entryTimerTs.it_value.tv_sec=...; // Set to a certain timeout value
entryTimerTs.it_value.tv_nsec=...; // Set to a certain timeout value
entryTimerTs.it_interval.tv_sec=...; // Set to a certain timeout value
entryTimerTs.it_interval.tv_nsec=...; // Set to a certain timeout value

timer_create(CLOCK_REALTIME,&entryTimerEvent,&(entry->entryTimer));

timer_settime(entry->entryTimer,0,&entryTimerTs,NULL);

当条目更新时，我只需使用 timer_settime 重新设置计时器。

但是，我担心当我达到数千个以上的条目时，这样的解决方案可能会在性能方面出现问题，所有条目都有自己的运行计时器(一些事件条目甚至可能以亚秒的粒度进行更新，导致非常频繁地调用 timer_settime)，我目前正在努力寻找一个好的替代方案。

您认为是否有更好、更高效的解决方案，也许不需要为每个条目使用计时器？

提前非常感谢您。

Answer 1

我对您的要求的了解:

1. 如果某个元素已超时，当您尝试获取它时，该元素不应出现
2. 最终它会被删除，这样表就不会永远增长

要实现这一点，您可以为每个元素添加时间戳，并且

1. 更改您的 get 函数以检查当前时间是否在时间戳之前，否则不返回
2. 有一个删除过期元素的观察者线程