3 ms·

I am interested in finding a hash function that helps me fill an array in a more compact way, without too many empty spaces. I.E. if I have 10k words to hash I

I am interested in finding a hash function that helps me fill an array in a more compact way, without too many empty spaces. I.E. if I have 10k words to hash I don't want to use a 20k array.

eesmith 3y ago
The choice depends on your circumstances. If you have 10K arbitrary words and want a 50% chance of collision then using a good hash means you'll need 20K entries (assuming you aren't using chaining). If you know the 10K words beforehand, then you can create a perfect hash function (https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function) so that only invalid words result in a collision. If you allow a higher collision rate then you can use fewer empty slots and do more probing.
- CodesInChaos 3y ago
  > If you have 10K arbitrary words and want a 50% chance of collision then using a good hash means you'll need 20K entries You'd need closer to 100M entries, since the birthday problem applies to collisions.
  - eesmith 3y ago
    You are thinking of a different calculation. I was referring to the average number of probes needed to find an unused slot, not the number needed to have a very low chance of collision for the 10,000 elements in the hash table. If the slot is already unused, then only one probe is needed. If the slot is used, then either you have a match or you need to test the next slot(s). With 50% of the slots occupied and 50% free, you should expect 1 + 0.5 + 0.25 + ... = 2.0 probes until you find an empty slot. Here are my results from testing three different probing techniques, using 10,000 items inserted into 20,000 slots, following by generating 10,000 new random words and seeing how many probes are needed to find an empty slot (#probes / num words): linear_probe: 24899 / 10000 = 2.49 quadratic_probe: 21131 / 10000 = 2.11 k_independent_probe: 19925 / 10000 = 1.99 This shows that with a really good probing algorithm (each probe uses a new sha256 calculation), on average you really do have only have a 50% chance of collision, and even with linear probing (which has is easy to develop, quick to re-probe, and has good cache coherency) you don't take a big hit due to collisions. Here's the code for the above: import random, hashlib, itertools rng = random.Random() # Create a random 'word' - the details don't matter as I assume there's a good hash def get_word(): return rng.randbytes(10) # Return a really good hash of size 2**256. def get_hash(word, attempt): sha256 = hashlib.sha256(attempt.to_bytes(4, "little") + word) return int.from_bytes(sha256.digest(), "little") N = 20_000 # The following code requires a `slots` list, which should # be initialized as: # slots = [None] * N # Use a new hash for each probe def k_independent_probe(word): for attempt in itertools.count(1): h = get_hash(word, attempt) % N if slots[h] is None: return (attempt, h) # Increment the hash by 1 for each probe (good cache locality) def linear_probe(word): h = get_hash(word, 0) % N for attempt in itertools.count(1): if slots[h] is None: return (attempt, h) h = (h + 1) % N # Increment the hash by attempt**2 for each probe def quadratic_probe(word): h = get_hash(word, 0) % N for attempt in itertools.count(1): if slots[h] is None: return (attempt, h) h = (h + attempt ** 2) % N # Add the word to the hash. # Must set the module variable `probe` to one of the above functions. def insert(word): _, h = probe(word) slots[h] = word # Test out the probe functions. for probe in (linear_probe, quadratic_probe, k_independent_probe): slots = [None] * N # Add 10,000 entries for i in range(10_000): word = get_word() insert(word) # See how many probes are needed to find an empty slot num_tests = 10_000 total_num_probes = 0 for i in range(num_tests): word = get_word() num_attempts, _ = probe(word) total_num_probes += num_attempts print(f"{probe.__name__}: {total_num_probes} / {num_tests} = {total_num_probes/num_tests:.2f}")
BiteCode_dev 3y ago
Depending of the context which I lack, a bloom filter could be an alternative to hashes there.
vlmutolo 3y ago
This may be more about the indexing strategy than the hash function. Meaning: once we have the hash(es), how do we decide what index to use for the key? Open-addressing schemes like linear probing, quadratic probing, certain variants of Robinhood hashing (which is kind of on a different axis anyway) commonly have 50–70% expected space efficiency. Performance is bad above 90%. But Cuckoo hash tables can get above 90% with great lookup performance (non-amortized constant time) and decent insert performance. Insert performance tends to suffer closer to 100%. Whether or not cuckoo hash tables qualify as “open addressing” will depend on the implementation, but the main point is that the addressing/indexing strategy mainly determines the operable “load factor” of the hash table. This is a great article on open addressing schemes (including cuckoo): https://thenumb.at/Hashtables/ https://thenumb.at/Hashtables/

I am interested in finding a hash function that helps me fill an array in a more compact way, without too many empty spaces. I.E. if I have 10k words to hash I don't want to use a 20k array.

eesmith 3y ago

The choice depends on your circumstances. If you have 10K arbitrary words and want a 50% chance of collision then using a good hash means you'll need 20K entries (assuming you aren't using chaining). If you know the 10K words beforehand, then you can create a perfect hash function (https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function) so that only invalid words result in a collision. If you allow a higher collision rate then you can use fewer empty slots and do more probing.

CodesInChaos 3y ago
> If you have 10K arbitrary words and want a 50% chance of collision then using a good hash means you'll need 20K entries You'd need closer to 100M entries, since the birthday problem applies to collisions.
- eesmith 3y ago
  You are thinking of a different calculation. I was referring to the average number of probes needed to find an unused slot, not the number needed to have a very low chance of collision for the 10,000 elements in the hash table. If the slot is already unused, then only one probe is needed. If the slot is used, then either you have a match or you need to test the next slot(s). With 50% of the slots occupied and 50% free, you should expect 1 + 0.5 + 0.25 + ... = 2.0 probes until you find an empty slot. Here are my results from testing three different probing techniques, using 10,000 items inserted into 20,000 slots, following by generating 10,000 new random words and seeing how many probes are needed to find an empty slot (#probes / num words): linear_probe: 24899 / 10000 = 2.49 quadratic_probe: 21131 / 10000 = 2.11 k_independent_probe: 19925 / 10000 = 1.99 This shows that with a really good probing algorithm (each probe uses a new sha256 calculation), on average you really do have only have a 50% chance of collision, and even with linear probing (which has is easy to develop, quick to re-probe, and has good cache coherency) you don't take a big hit due to collisions. Here's the code for the above: import random, hashlib, itertools rng = random.Random() # Create a random 'word' - the details don't matter as I assume there's a good hash def get_word(): return rng.randbytes(10) # Return a really good hash of size 2**256. def get_hash(word, attempt): sha256 = hashlib.sha256(attempt.to_bytes(4, "little") + word) return int.from_bytes(sha256.digest(), "little") N = 20_000 # The following code requires a `slots` list, which should # be initialized as: # slots = [None] * N # Use a new hash for each probe def k_independent_probe(word): for attempt in itertools.count(1): h = get_hash(word, attempt) % N if slots[h] is None: return (attempt, h) # Increment the hash by 1 for each probe (good cache locality) def linear_probe(word): h = get_hash(word, 0) % N for attempt in itertools.count(1): if slots[h] is None: return (attempt, h) h = (h + 1) % N # Increment the hash by attempt**2 for each probe def quadratic_probe(word): h = get_hash(word, 0) % N for attempt in itertools.count(1): if slots[h] is None: return (attempt, h) h = (h + attempt ** 2) % N # Add the word to the hash. # Must set the module variable `probe` to one of the above functions. def insert(word): _, h = probe(word) slots[h] = word # Test out the probe functions. for probe in (linear_probe, quadratic_probe, k_independent_probe): slots = [None] * N # Add 10,000 entries for i in range(10_000): word = get_word() insert(word) # See how many probes are needed to find an empty slot num_tests = 10_000 total_num_probes = 0 for i in range(num_tests): word = get_word() num_attempts, _ = probe(word) total_num_probes += num_attempts print(f"{probe.__name__}: {total_num_probes} / {num_tests} = {total_num_probes/num_tests:.2f}")

BiteCode_dev 3y ago

Depending of the context which I lack, a bloom filter could be an alternative to hashes there.

vlmutolo 3y ago

This may be more about the indexing strategy than the hash function. Meaning: once we have the hash(es), how do we decide what index to use for the key? Open-addressing schemes like linear probing, quadratic probing, certain variants of Robinhood hashing (which is kind of on a different axis anyway) commonly have 50–70% expected space efficiency. Performance is bad above 90%. But Cuckoo hash tables can get above 90% with great lookup performance (non-amortized constant time) and decent insert performance. Insert performance tends to suffer closer to 100%. Whether or not cuckoo hash tables qualify as “open addressing” will depend on the implementation, but the main point is that the addressing/indexing strategy mainly determines the operable “load factor” of the hash table. This is a great article on open addressing schemes (including cuckoo): https://thenumb.at/Hashtables/ https://thenumb.at/Hashtables/