title: What is the most efficient way to implement a C hash table with timeout on entries?
body: <p>I am currently developing a hash table to serve as a database data structure which may contain a large number of elements and which must be as much efficient as possible (especially on the operations to add a new elements and update an existing element).
  I am also forced to use only C (avoiding C++ or other languages which have existing classes or structures which could really help in this case).</p>
  <p>What I need to develop is a hash table with linked lists in which each entry has a timeout (let's say few minutes), after which it should automatically delete itself (or, as an alternative, the old entries should be &quot;garbage collected&quot; at a certain point in time, as elements may be added at a very fast rate and I do not want to use too much memory for entries which are too old).</p>
  <p>I was thinking about adding a timer field to each entry of the Hash Table:</p>
  <pre><code>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;
  };
  </code></pre>
  <p>Then, when a new entry is added, to start a timer (this project will only run on Linux, that's why I am considering to use <code>timer_t</code> - error checking is not performed in this sample code for the sake of brevity):</p>
  <pre><code>struct sigevent entryTimerEvent;
  struct itimerspec entryTimerTs;
  
  // Allocate a new entry for a given id (struct HTnode *entry)
  // ...
  
  memset(&amp;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,&amp;entryTimerEvent,&amp;(entry-&gt;entryTimer));
  
  timer_settime(entry-&gt;entryTimer,0,&amp;entryTimerTs,NULL);
  </code></pre>
  <p>When an entry is updated, instead, I would just rearm the timer with <code>timer_settime</code>.</p>
  <p>However, I fear that a solution like this could become problematic in terms of performance when I reach more than some thousands of entries, all with their own running timer (some active entries may be even updated with a sub-second granularity, causing very frequent calls to <code>timer_settime</code>), and I am currently struggling to find a good alternative.</p>
  <p>Are there better and more efficient solutions, in your opinion, maybe not requiring the usage of timers for each entry?</p>
  <p>Thank you very much in advance.</p>