How Sets Work: Hashing
Sets achieve their blazing speed using
an algorithmic approach called hashing.
A hash function takes any value as input and returns an integer. The function returns the same integer each time it is called on a given value, and should generally return different integers for different values, though that does not always need to be the case. We actually don't need to build the hash function ourselves, as Python has one already, a built-in function called hash.
Python stores items in a set by creating a hash table, which is a list of
N lists (called 'buckets'). Python chooses the bucket for an element based on its
hash value, using hash(element) % n. Values in each bucket are not sorted,
but the size of each bucket is limited to some constant K.
We get O(1) (constant-time) adding like so:
- Compute the bucket index
hash(element) % n -- takes O(1).
- Retrieve the bucket hashTable[bucketIndex] -- takes O(1).
- Append the element to the bucket -- takes O(1).
We get O(1) (constant-time) membership testing ('in') like so:
- Compute the bucket index
hash(element) % n -- takes O(1).
- Retrieve the bucket hashTable[bucketIndex] -- takes O(1).
- Check each value in the bucket if it equals the element -- takes O(1) because
there are at most K values in the bucket, and K is a constant.
Q: How do we guarantee that each bucket is no larger than size K?
A: Good question! If we need to add a (K+1)th value to a bucket, instead we
resize our hashtable, making it say twice as big, and then we rehash
every value, basically adding it to the new hashtable. This takes O(N) time,
but we do it very rarely, so the amortized worst case remains O(1).
A practical example of how sets are faster than lists is shown below:
# 0. Preliminaries
import time
n = 1000
# 1. Create a list [2,4,6,...,n] then check for membership
# among [1,2,3,...,n] in that list.
# don't count the list creation in the timing
a = list(range(2,n+1,2))
print("Using a list... ", end="")
start = time.time()
count = 0
for x in range(n+1):
if x in a:
count += 1
end = time.time()
elapsed1 = end - start
print(f'count={count} and time = {elapsed1:0.5f} seconds')
# 2. Repeat, using a set
print("Using a set.... ", end="")
start = time.time()
s = set(a)
count = 0
for x in range(n+1):
if x in s:
count += 1
end = time.time()
elapsed2 = end - start
print(f'count={count} and time = {elapsed2:0.5f} seconds')
print(f'At n={n}, sets ran ~{elapsed1/elapsed2:0.1f} times faster than lists!')
print("Try a larger n to see an even greater savings!")