Contains-key versus contains-value
Updated
contains-key hashes. contains-value walks every entry until it finds that value, or finishes. One is expected O(1). The other is O(n). If you call contains-value in a loop, you probably wanted a reverse map or a set of values.
What to focus on
Several keys may contain the same value, so contains-value is exists at least one, not the key is.
Worked examples
key hit
a = [4, 1, 9] as {4:2,1:8,9:3}, hasKey 9- hash 9
Result: true, expected O(1)
value hit
a = [4, 1, 9] as {4:2,1:8,9:3}, hasValue 8- scan until 1→8
Result: true, O(n)
value miss
a = [4, 1, 9] as {4:2,1:8,9:3}, hasValue 7- scan all
Result: false, O(n)
Try it
Write hasKey(m, k) and hasValue(m, v). m is the hash map. k is a key. v is a value. hasKey is expected O(1). hasValue is O(n). a = [4, 1, 9] as {4:2,1:8,9:3}, hasKey 9 → true, expected O(1). a = [4, 1, 9] as {4:2,1:8,9:3}, hasValue 8 → true, O(n). a = [4, 1, 9] as {4:2,1:8,9:3}, hasValue 7 → false, O(n).
keys and values are integers. The map is non-empty.