StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You might not like this, because they're probably looking for a clever solution, but sometimes it pays to stick to your guns... A <strong>hash table already satisfies the requirements</strong> - probably better overall than anything else will (albeit obviously in amortised constant time, and with different compromises to other solutions).</p> <p>The requirement that's tricky is the "random element" selection: in a hash table, you would need to scan or probe for such an element.</p> <p>For closed hashing / open addressing, the chance of any given bucket being occupied is <code>size() / capacity()</code>, but crucially this is typically kept in a constant multiplicative range by a hash-table implementation (e.g. the table may be kept larger than its current contents by say 1.2x to ~10x depending on performance/memory tuning). This means on average we can expect to search 1.2 to 10 buckets - totally independent of the total size of the container; amortised O(1).</p> <p>I can imagine two simple approaches (and a great many more fiddly ones):</p> <ul> <li><p>search linearly from a random bucket</p> <ul> <li>consider empty/value-holding buckets ala "--AC-----B--D": you <em>can</em> say that the first "random" selection is fair even though it favours B, because B had no more probability of being favoured than the other elements, but if you're doing repeated "random" selections using the same values then clearly having B repeatedly favoured may be undesirable (nothing in the question demands even probabilities though)</li> </ul></li> <li><p>try random buckets repeatedly until you find a populated one</p> <ul> <li>"only" capacity() / size() <em>average</em> buckets visited (as above) - but in practical terms more expensive because random number generation is relatively expensive, and infinitely bad if infinitely improbable worst-case behaviour... <ul> <li>a faster compromise would be to use a list of pre-generated random offsets from the initial randomly selected bucket, %-ing them into the bucket count</li> </ul></li> </ul></li> </ul> <p>Not a great solution, but may still be a better overall compromise than the memory and performance overheads of maintaining a second index array at all times.</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