I instrumented the hasher in the repo’s two-sum solution. It hashed the same key three times to produce one answer.
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut map = HashMap::new();
for (i, num) in nums.iter().enumerate() {
let complement = target - num;
if map.contains_key(&complement) {
return vec![map[&complement], i as i32];
}
map.insert(num, i as i32);
}
vec![]
}
Two of those hashes are waste. contains_key asks whether the complement is in the map. map[&complement] asks where it is. Same question, two costumes, and the second costume is the one that can kill the process.
Indexing is a promise
map[&complement] is not a lookup with a safe fallback. It is HashMap’s Index implementation, and the contract it enforces is that the key must already be there. Miss, and the program dies:
thread 'main' panicked at src/main.rs:95:31:
no entry found for key
That message came from a scratch run: a map holding one key, asked for a key that was not in it.
So the line is safe only because of the line above it. contains_key proves the key is present, and the index operator takes that proof on faith. A two-step protocol where the second step re-derives the first step’s result at runtime, hashing the key again to get it.
Counting the hashes
I replaced the map’s hasher with one that counts how many times it is asked to hash a key, then ran both versions on nums = [2, 7, 11, 15] with target = 9:
path A (contains_key + Index): 3 hash computations, result Some([0, 1])
path B (get): 2 hash computations, result Some([0, 1])
Three against two. The extra hash is the duplicate probe on the hit: contains_key hashes the complement, finds it, and then map[&complement] hashes the same complement again to read a value that had already been found.
Asking once
if let Some(&j) = map.get(&complement) {
return vec![j, i as i32];
}
get returns Option<&i32>: one hash, one probe, and the answer arrives with the value attached. if let Some(&j) destructures the reference, so j is an i32 that can be copied straight into the result.
This is my version. The repo still ships the two-step form.
The cast the signature forced
enumerate() produces usize. The signature wants Vec<i32>. So i as i32 shows up twice: once on the index being returned, once on the index being stored.
An as cast between integers truncates. It does not saturate and it does not check. I measured it:
4294967296usize as i32 = 0
The problem constrains 2 <= nums.len() <= 10^4, so an index never passes 9999 and the cast cannot lose anything under the spec. The cast is not a bug here. But the thing keeping it harmless is the problem statement, not the type system, and the function says nothing about that.
Keeping the map as HashMap<i32, usize> and casting once at the return boundary would put the conversion where the output type forces it, instead of in two places where nothing forces it.
The two-step version has to be right about something it cannot see
There is a temptation to read contains_key plus map[...] as the careful version and get as the lazy one. It is the other way around. The two-step version has to be right about something it cannot see: that a different call, on a different line, already proved the key exists. The one-step version cannot be wrong that way, because there is no second step to be wrong in.
The panic was never the real problem. It was the loud symptom of a lookup that had been split in two, and the split cost a hash on every call and an assumption on every hit.
The habit I kept from this: when a lookup is followed by an index on the same key, there is probably a get waiting to replace both.