StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I see the point on utilization but this was my reasoning for trying this particular hashing scheme. Please ket me know if I missed something.</p> <p>To my knowledge, possible alternatives to hashtables to create a dynamic dictionary are (balanced) binary trees and skiplists. Just for discussion let's abstract from the key and value types and let's assume that we will access values through a <code>void *</code>.</p> <p>For a binary tree I would have:</p> <pre><code>struct node { void *key; void *value; struct node *left; struct node *right; } </code></pre> <p>So, assuming pointers have all the same size <em>s</em>, to store <em>n</em> items I will need 4 <em>s</em> bytes.</p> <p>Skiplists are almost the same as the average number of pointers in a node is 2.</p> <p>In an hashtable I would have:</p> <pre><code>struct slot { void *key; void *value; } </code></pre> <p>So, each item will only requre 2 <em>s</em> bytes to be stored. If the load factor is 50%, to store <em>n</em> items I will need the same 4 <em>s</em> bytes as trees.</p> <p>It doesn't seem too bad to me: the cuckoo hashtable will occupy more or less the same amount of memory as a binary tree but will give me O(1) access time rather than O(log n). </p> <p>Not counting the complexity of keeping the tree balanced and the additional info that could be required to store balancing information in the node.</p> <p>Other hashing schemes could achieve a better load factor (say 75% or 80%) with no guarantee on the worst case access time (that could even be O(n) ). </p> <p>By the way, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.5337" rel="nofollow noreferrer">d-ary cuckoo hashing</a> and "<a href="http://research.microsoft.com/users/uwieder/papers/stash-full.pdf" rel="nofollow noreferrer">cuckoo hashing with a stash</a>" seem to be able to increase the load factor while still keeping constant access time.</p> <p>Cuckoo hashing seems a valuable technique to me and I thought it was already explored; that's the reason of my question. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload