4 ms·

> 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, si

> 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}")

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}")