Hash Tables
Loading
Loading
Hash Tables
Designing a canonical key so that things belonging together collide deliberately.
By the end of this chapter
Comparing every item with every other to decide who belongs together is quadratic. If instead each item can be reduced to a key that is identical for everything in its group, the hash table does the grouping for free.
["eat", "tea", "tan", "ate"]"eat" → "aet"sorted characters"tea" → "aet"same key, same group"tan" → "ant"different key"ate" → "aet"joins the first group2 groupsdef group_by_signature(words): groups = {} for word in words: key = "".join(sorted(word)) # discards order, keeps multiset groups.setdefault(key, []).append(word) return list(groups.values())| Equivalence rule | Key |
|---|---|
| Same characters, any order | Sorted characters, or a count tuple |
| Same shape of differences | Tuple of consecutive differences |
| Same remainder | value modulo k |
| Same normalised text | lowercased, punctuation stripped |
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: try 1 practice problem.