我目前正在开发一个哈希表，用作数据库数据结构，该结构可能包含大量元素，并且必须尽可能高效(尤其是在添加新元素和更新现有元素的操作上)。我还被迫只使用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的频繁调用)，我目前正在努力寻找一个好的替代方案。
在你看来，是否有更好、更有效的解决方案，也许不需要每次输入都使用计时器？
事先非常感谢。
我了解您的需求：
- 如果元素超时，则在尝试获取它时不应出现它
- 最终它将被删除，这样表就不会永远增长
要实现这一点，您可以为每个元素和添加一个时间戳
- 更改get函数以检查当前时间是否在时间戳之前，否则不返回
- 具有删除过期元素的观察程序线程
一个粗糙但简单的选项：
有不同的哈希表——例如，三个表，每个表存储在特定分钟内添加的所有条目；将新条目添加到表[active]中。要进行查找或擦除，请在活动表中进行搜索(如果最近添加的元素在统计上最有可能被访问)，然后依次尝试旧表。当您添加一个元素并发现分钟已更改时，请将活动与++active %= 3一起切换，然后在添加新元素之前清除table[active]。
一种更为过度设计的方式，使用单个哈希表。。。
假设您希望删除早于X个时间单位的元素，即使它们最近被访问过，那么您所需要的就是在哈希表的一侧创建一个双端队列，用于跟踪您添加的元素。队列中的每个元素都应该存储到期时间和便于快速删除的内容(例如，指向bucket中链表中前一个元素(或bucket/root)的指针，如果您使用单独的链接，则不必支持调整哈希表的大小，并且知道元素不会被任何其他机制擦除)。我之所以说上一个，是因为如果它是一个单链列表，那么你需要重新连接上一个元素的下一个指针。如果它是一个双链接列表，那么存储指向元素本身的指针可能会更直观，然后可以使用prev->next = next重新布线。
当您添加一个元素时，您会将它添加到该队列的后面。每当您有空闲时间进行一些内务管理时，您都会从队列的最前面开始，并擦除任何过期的元素。您可以查看是否最好有一个单独的线程来处理expiries(但随后您需要围绕哈希表访问/更新进行锁定)，或者从使用哈希表的同一线程进行锁定。
如果您确实希望最近访问的元素停留更长时间，那么您可能希望使用最近最少使用的缓存机制来跟踪到期时间，这意味着您需要能够按关键字在LRU中进行搜索，因此您可能需要使用平衡的二进制树。这将是更多的实施工作。
如果您使用的是封闭哈希/开放寻址哈希表，如何擦除元素将取决于您如何处理冲突：您可能只需要用不再使用的sentinel值覆盖bucket，或者您可能不得不将另一个元素移到更接近其哈希到bucket的位置。这些因素可能会改变超时跟踪双端队列或LRU中存储的索引数据。
用C从头开始是一项重大任务，所以我建议您使用现有的数据结构库。尽管如此，在StackOverflow上，询问第三方资源的建议是不合适的，如果你还不知道自己的选择，这可能会让你感到沮丧。这些天我无法从C++回到C——太令人沮丧了——而且我不知道目前的产品有什么建议。。。。