Loading page…
Build safe composite keys, and avoid mutable keys, float keys, iteration-order bugs and inputs that force collisions (the rolling hash itself is A7).
After i requests, the set holds one key for each different pair, and two requests share a key exactly when both numbers are equal.
Use it when the thing you look up has several parts, is a collection, or is a number written in more than one way. Use it also when the order of the output must not depend on the table. Signal words: a key made of several fields, in any order, the same number written in different ways, the same on every server.
Start: decide what "the same" means for two items. Then write the key as one fixed value that is equal exactly for items that are the same.
Step: build the key from a copy of the item, never from a value that can change later. Look it up. Then add it, or count it.
Stop: when the items run out. Take the output order from the input, not from the table.
It does not answer questions about order or range, such as the next key above a value. A hash table has no order.
Cost: O(n) set steps on average, plus the cost of building and hashing one key for each item. For a key of k parts, that is O(n × k). The comparison of every pair costs O(n^2).
def distinct_pairs(firsts, seconds):
# [1] A set of keys, one for each different pair.
seen = set()
for i in range(len(firsts)):
# [2] The key keeps the pair as a pair, with both numbers in it.
# A tuple compares both parts and never glues them.
key = (firsts[i], seconds[i])
# [3] The same pair always gives the same key, and different pairs give different keys.
seen.add(key)
# [4] The number of different pairs.
return len(seen)public int distinctPairs(int[] firsts, int[] seconds) {
// [1] A set of keys, one for each different pair.
java.util.HashSet<Long> seen = new java.util.HashSet<>();
for (int i = 0; i < firsts.length; i++) {
// [2] The key keeps the pair as a pair, with both numbers in it.
// Pack both ints into one long, and mask the second so that its sign does not spill into the first.
long key = ((long) firsts[i] << 32) | (seconds[i] & 0xFFFFFFFFL);
// [3] The same pair always gives the same key, and different pairs give different keys.
seen.add(key);
}
// [4] The number of different pairs.
return seen.size();
}int distinctPairs(vector<int>& firsts, vector<int>& seconds) {
// [1] A set of keys, one for each different pair.
unordered_set<long long> seen;
for (size_t i = 0; i < firsts.size(); i++) {
// [2] The key keeps the pair as a pair, with both numbers in it.
// Pack both ints into one 64-bit number, and mask the second so that its sign does not spill into the first.
long long key = ((long long)firsts[i] << 32) | (unsigned int)seconds[i];
// [3] The same pair always gives the same key, and different pairs give different keys.
seen.insert(key);
}
// [4] The number of different pairs.
return (int)seen.size();
}function distinctPairs(firsts, seconds) {
// [1] A set of keys, one for each different pair.
const seen = new Set();
for (let i = 0; i < firsts.length; i++) {
// [2] The key keeps the pair as a pair, with both numbers in it.
// Join the two numbers with a separator that cannot appear in a number.
const key = firsts[i] + "," + seconds[i];
// [3] The same pair always gives the same key, and different pairs give different keys.
seen.add(key);
}
// [4] The number of different pairs.
return seen.size;
}def distinct_filter_sets(filters):
# [1] A set of keys, one for each different set of filters.
seen = set()
for row in filters:
# [2] The key is a copy of the filters in a fixed form that ignores order and repeats.
# A list cannot be a key in Python, and a frozenset can.
key = frozenset(row)
# [3] The copy never changes, even if the row is edited later.
seen.add(key)
# [4] The number of different sets.
return len(seen)public int distinctFilterSets(int[][] filters) {
// [1] A set of keys, one for each different set of filters.
java.util.HashSet<java.util.Set<Integer>> seen = new java.util.HashSet<>();
for (int[] row : filters) {
// [2] The key is a copy of the filters in a fixed form that ignores order and repeats.
// A new set compares by its contents, and the copy is separate from the row.
java.util.Set<Integer> key = new java.util.HashSet<>();
for (int tag : row) {
key.add(tag);
}
// [3] The copy never changes, even if the row is edited later.
seen.add(key);
}
// [4] The number of different sets.
return seen.size();
}int distinctFilterSets(vector<vector<int>>& filters) {
// [1] A set of keys, one for each different set of filters.
set<set<int>> seen;
for (const vector<int>& row : filters) {
// [2] The key is a copy of the filters in a fixed form that ignores order and repeats.
// unordered_set has no hash for a set, so an ordered set of sets does the comparing.
set<int> key(row.begin(), row.end());
// [3] The copy never changes, even if the row is edited later.
seen.insert(key);
}
// [4] The number of different sets.
return (int)seen.size();
}function distinctFilterSets(filters) {
// [1] A set of keys, one for each different set of filters.
const seen = new Set();
for (const row of filters) {
// [2] The key is a copy of the filters in a fixed form that ignores order and repeats.
// A string of the sorted, distinct tags works, because an array would be compared by identity.
const key = [...new Set(row)].sort((a, b) => a - b).join(",");
// [3] The copy never changes, even if the row is edited later.
seen.add(key);
}
// [4] The number of different sets.
return seen.size;
}This version writes the two numbers one after the other, and uses the text as the key. It looks fine on small numbers. Different pairs can give the same text.
This Java or C++ version packs the two numbers into one 64-bit number with |, and forgets to mask the second one. A negative int is widened with its sign bits, and those bits overwrite the first number.
In Python, a list or a set cannot be a key at all: {[1, 2]: "x"} raises TypeError: unhashable type: 'list', and so does a tuple that holds a list. Java and JavaScript accept a mutable key, which is worse.
A running total of amounts is kept as a floating-point number, and the total is used as a key. Floating-point numbers round.
A report is built by looping over a table, and its order is printed as it comes. A table keeps no order you can rely on, and each language gives its own.
A word count uses a plain object: counts[word] = (counts[word] || 0) + 1. An object has keys that you did not put there.
Your team lead asks for the first request after 09:00, or for the largest page number below 50. A hash table finds an equal key, and it has no order. Neither question is about an equal key.
systemdesignmastery.dev/dsa/cheatsheets/hashing-pitfalls