Re: [PATCH] make light userdata a little bit heavier

[Coroutines <coroutines@...>]

On Tue, Apr 22, 2014 at 2:16 AM, Ross Bencina
<rossb-lists@audiomulch.com> wrote:

> A hash table has amortized O(1) insert/lookup.

>From what I understand, the memory added by maintaining a hash table
of addresses would be double a binary-searched array/vector (assuming
the keys are word-sized for quick access).  Also, while a hash table
would provide O(1) lookup time, the hash function itself could take a
while to do it's thing -- though I'm sure in most cases a simple
minimal hash function would beat a binary-search of a vector/array of
real-world size. :>

I wish I could find more information on creating simple hashing
functions for "perfect" or "minimal" hash tables (with collisions or
without to save on memory -- no vacant table slots).  There aren't a
lot of examples outside of cryptography-related stuff.  My college
didn't cover creating hashes either... -- not a very good college
though :]  I just have this impression that extra processing to
obscure what was hashed is time lost when you might not need that
protection for certain situations (like this).

I know of murmurhash and cityhash for non-crypto stuff, but I'm sure
they're oriented toward hashing data of variable-length and not
fixed-size numbers like a memory address.  Again these hashes seemed
more heavyweight and broad?  I'd love to find more examples on trivial
ways to build perfect & minimal hashes.  One recurring example is:
hash(key) = #table / key  -- obviously this produces collisions

Wikipedia hints at creating hash/indexes that scale along powers of 2
and to size hash tables appropriately for this.  (tuning the algorithm
for calculating indexes along powers of 2 I guess?)

Here's some stuff I could find:

http://en.wikipedia.org/wiki/Category:Hash_functions
http://en.wikipedia.org/wiki/Category:Cryptographic_hash_functions
http://en.wikipedia.org/wiki/Hash_table

Anyway, sorry for hijacking the thread with my own curiosity.  Back to
business people ^__^