<story><title>How to implement a hash table in C</title><url>https://benhoyt.com/writings/hash-table-in-c/</url></story><parent_chain><item><author>OskarS</author><text>It’s usually not the right call to use a hash table like you’re describing. You’re not saving any work (all keys have to be migrated sooner or later) and by doing it like this you incur a non-trivial amount of overhead on most operations.&lt;p&gt;Hash tables generally work on the assumption that operations are O(1) in the amortized sense, that individual inserts might be expensive because of rehashing, but in aggregate they are very cheap. In practice, this is almost always a fine assumption, and it is how the vast majority of hash tables in all programming languages work.&lt;p&gt;The kinds of hash tables you are talking about have their uses in places where you have soft real-time constraints, but that is honestly a pretty niche use case.</text></item><item><author>thamer</author><text>&amp;gt; When the hash table gets too full, we need to allocate a larger array and move the items over. This is absolutely required when the number of items in the hash table has reached the size of the array, but usually you want to do it when the table is half or three-quarters full.&lt;p&gt;Yes, but &lt;i&gt;how&lt;/i&gt; you resize is important too: if you have a threshold size (like 3&amp;#x2F;4 full) at which you block and re-distribute all elements into a new array, you will incur a significant pause when this happens, e.g.  &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;log.kv.io&amp;#x2F;post&amp;#x2F;2009&amp;#x2F;05&amp;#x2F;15&amp;#x2F;leaky-hashtables&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;log.kv.io&amp;#x2F;post&amp;#x2F;2009&amp;#x2F;05&amp;#x2F;15&amp;#x2F;leaky-hashtables&lt;/a&gt;&lt;p&gt;Instead, when you reach the threshold amount you can create the new array and then gradually migrate the keys in small batches either with each operation or with a background thread. So on `get` if we&amp;#x27;re in the process of resizing: first check the new table, then the old one, and before returning migrate N keys from the old table to the new one. Free the old array once all the keys are migrated.&lt;p&gt;I wrote a small hash table implementation with gradual re-hashing a while back, search for DICT_MAX_LOAD and dict_rehash here: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;nicolasff&amp;#x2F;ht&amp;#x2F;blob&amp;#x2F;master&amp;#x2F;dict.c#L193&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;nicolasff&amp;#x2F;ht&amp;#x2F;blob&amp;#x2F;master&amp;#x2F;dict.c#L193&lt;/a&gt;</text></item></parent_chain><comment><author>pjam</author><text>The progressive rehashing described in the article is very similar to what Redis does [1].&lt;p&gt;Just thought I&amp;#x27;d share a example of a use case where the incremental rehashing logic makes sense.&lt;p&gt;[1]: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;redis&amp;#x2F;redis&amp;#x2F;blob&amp;#x2F;unstable&amp;#x2F;src&amp;#x2F;dict.c&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;redis&amp;#x2F;redis&amp;#x2F;blob&amp;#x2F;unstable&amp;#x2F;src&amp;#x2F;dict.c&lt;/a&gt;</text></comment>
<story><title>How to implement a hash table in C</title><url>https://benhoyt.com/writings/hash-table-in-c/</url></story><parent_chain><item><author>OskarS</author><text>It’s usually not the right call to use a hash table like you’re describing. You’re not saving any work (all keys have to be migrated sooner or later) and by doing it like this you incur a non-trivial amount of overhead on most operations.&lt;p&gt;Hash tables generally work on the assumption that operations are O(1) in the amortized sense, that individual inserts might be expensive because of rehashing, but in aggregate they are very cheap. In practice, this is almost always a fine assumption, and it is how the vast majority of hash tables in all programming languages work.&lt;p&gt;The kinds of hash tables you are talking about have their uses in places where you have soft real-time constraints, but that is honestly a pretty niche use case.</text></item><item><author>thamer</author><text>&amp;gt; When the hash table gets too full, we need to allocate a larger array and move the items over. This is absolutely required when the number of items in the hash table has reached the size of the array, but usually you want to do it when the table is half or three-quarters full.&lt;p&gt;Yes, but &lt;i&gt;how&lt;/i&gt; you resize is important too: if you have a threshold size (like 3&amp;#x2F;4 full) at which you block and re-distribute all elements into a new array, you will incur a significant pause when this happens, e.g.  &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;log.kv.io&amp;#x2F;post&amp;#x2F;2009&amp;#x2F;05&amp;#x2F;15&amp;#x2F;leaky-hashtables&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;log.kv.io&amp;#x2F;post&amp;#x2F;2009&amp;#x2F;05&amp;#x2F;15&amp;#x2F;leaky-hashtables&lt;/a&gt;&lt;p&gt;Instead, when you reach the threshold amount you can create the new array and then gradually migrate the keys in small batches either with each operation or with a background thread. So on `get` if we&amp;#x27;re in the process of resizing: first check the new table, then the old one, and before returning migrate N keys from the old table to the new one. Free the old array once all the keys are migrated.&lt;p&gt;I wrote a small hash table implementation with gradual re-hashing a while back, search for DICT_MAX_LOAD and dict_rehash here: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;nicolasff&amp;#x2F;ht&amp;#x2F;blob&amp;#x2F;master&amp;#x2F;dict.c#L193&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;nicolasff&amp;#x2F;ht&amp;#x2F;blob&amp;#x2F;master&amp;#x2F;dict.c#L193&lt;/a&gt;</text></item></parent_chain><comment><author>jeffffff</author><text>iirc memcached either uses or used to use &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Linear_hashing&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Linear_hashing&lt;/a&gt; to avoid rehashing induced pauses. it definitely makes sense for that use case but you&amp;#x27;re correct that it&amp;#x27;s not the right call for a general purpose hash table implementation.</text></comment>