<story><title>Diving into the world of hash tables</title><url>http://www.zeroequalsfalse.press/2017/02/20/hashtables/</url></story><parent_chain></parent_chain><comment><author>VHRanger</author><text>If you care about performance, it&amp;#x27;s important to note how the underlying representation of a dictionary data structure.&lt;p&gt;For instance, the unordered_hash_map in C++ is based around a linked list of key&amp;#x2F;value pair buckets. This means iterating through the keys or values is very slow (lots of cache misses!), but insertion is fast. Retrieving a key is O(logn) but a very slow O(logn), because of the cache misses.&lt;p&gt;Other implementations is to keep a sorted vector of keys and a respective vector of values. There&amp;#x27;s loki::assocvector, booost::flat_unordered_map that do this for instance. Now insertion is slow, but iteration and retrieval are very fast (a fast O(logn) by binary search with few cache misses). It&amp;#x27;s also memory efficient, since no pointers between elements.&lt;p&gt;If you have one big dictionary you would use throughout an application, and know the data up front, a good strategy is to reserve the necessary memory in an array, fill it with keys&amp;#x2F;values, sort it once over the keys and coindex the value array. Now you have a memory efficient and extremely fast dictionary data structure.&lt;p&gt;One other strategy any intermediate coder can implement is to have two unsorted coindexed arrays. You don&amp;#x27;t even need a hash function for this. Now iterating and insertion through the table is extremely fast, and it is memory efficient, but finding a key is just a fast O(n). So this is good for smaller tables. In C++ you could implement it as a std::pair&amp;lt;vector&amp;lt;key&amp;gt;, vector&amp;lt;value&amp;gt;&amp;gt;. If you need a quick small map in a function this is often the fastest data structure you can implement without too many headaches.</text></comment>
<story><title>Diving into the world of hash tables</title><url>http://www.zeroequalsfalse.press/2017/02/20/hashtables/</url></story><parent_chain></parent_chain><comment><author>emeraldd</author><text>This is one of those data structures that everyone should try building at least once, kind of like linked lists, etc. Semi-unrelated, I built a couple of toy implementations a few years ago using the same basic ideas:&lt;p&gt;* This one is the my original written in something halfway resembling scheme:
&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;arlaneenalra&amp;#x2F;Bootstrap-Scheme&amp;#x2F;blob&amp;#x2F;master&amp;#x2F;lib&amp;#x2F;hash.scm&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;arlaneenalra&amp;#x2F;Bootstrap-Scheme&amp;#x2F;blob&amp;#x2F;master...&lt;/a&gt;&lt;p&gt;* And this implementation is part of a half finished byte code scheme that I haven&amp;#x27;t touched in a few years. Another project I need to get back to.
Interface: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;arlaneenalra&amp;#x2F;insomniac&amp;#x2F;blob&amp;#x2F;master&amp;#x2F;src&amp;#x2F;include&amp;#x2F;hash.h&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;arlaneenalra&amp;#x2F;insomniac&amp;#x2F;blob&amp;#x2F;master&amp;#x2F;src&amp;#x2F;in...&lt;/a&gt;
Internals: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;arlaneenalra&amp;#x2F;insomniac&amp;#x2F;tree&amp;#x2F;master&amp;#x2F;src&amp;#x2F;libinsomniac_hash&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;arlaneenalra&amp;#x2F;insomniac&amp;#x2F;tree&amp;#x2F;master&amp;#x2F;src&amp;#x2F;li...&lt;/a&gt;&lt;p&gt;They were kind of fun to build and I&amp;#x27;d recommend giving, especially if you have some skill but don&amp;#x27;t &lt;i&gt;think&lt;/i&gt; you have the chops. To get a working toy isn&amp;#x27;t really all that hard once you understand the principals.</text></comment>