= Solution
Assume the supplied <hash function> is stable and produces valid table indices. The <representation invariant> places each name in its hashed bucket, permits at most one entry per name, and requires finite acyclic, disjoint bucket chains.
``
def store(name: String, number: String): Unit = {
val bucket = hash(name)
val entry = find(name, table(bucket))
if (entry == null) {
table(bucket) = new Entry(name, number, table(bucket))
} else {
entry.number = number
}
}
``
If the key exists, updating its associated number implements map override without creating a duplicate entry. Otherwise a new entry is prepended to the correct bucket and leaves every existing mapping unchanged. Its immutable name preserves bucket membership. Thus \b[the mapping afterwards is the old mapping overridden at precisely the supplied key]. <Hash collisions> between different names do not imply key equality and are handled by <separate chaining>.
Back to article page
