Get is not a search by value
Updated
Get is keyed. Finding which key stores a given value is a scan of entries, expected O(n), not O(1). If you needed value→key, you built the wrong direction, or you need a second map.
What to focus on
contains-value is also a scan unless you maintain a reverse index. Do not loop values hoping the hash will help. The hash is on keys.
Worked examples
forward
a = [4, 1, 9] as {4:2,1:8,9:3}, get 1- O(1) expected
Result: 8
reverse scan
a = [4, 1, 9] as {4:2,1:8,9:3}, find key for value 8- must walk entries
Result: key 1, O(n)
duplicate values
a = [4, 1] as {4:2,1:2}, find key for 2- two answers
Result: 4 or 1 — get cannot pick
Try it
Write get(m, k) and findKey(m, v). m is the hash map. k is a key. v is a value. get is expected O(1) by key. findKey walks entries, O(n). Duplicate values are ambiguous. a = [4, 1, 9] as {4:2,1:8,9:3}, get 1 → 8. a = [4, 1, 9] as {4:2,1:8,9:3}, find key for value 8 → key 1, O(n). a = [4, 1] as {4:2,1:2}, find key for 2 → 4 or 1 — get cannot pick.
keys and values are integers. The map is non-empty.