Use null to indicate that the requested key is absent:
private def find(name: String, head: Entry): Entry = {
var cursor = head
while (cursor != null && cursor.name != name) {
cursor = cursor.next
}
cursor
}The loop invariant is that the skipped string prefix contains no entry with the requested name and
cursor starts the unsearched string suffix of the unchanged bucket. Its remaining length is a loop variant. Short-circuit evaluation prevents accessing a null entry. On exit, either cursor is null and the whole bucket has been ruled out, or its name equals the key. No list links or stored numbers are modified. String comparison here uses value equality; node deletion elsewhere uses reference identity.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 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.
Membership is exactly whether the bucket search finds an entry:
def isInBook(name: String): Boolean = {
find(name, table(hash(name))) != null
}By the bucket-placement representation invariant, an entry with this name can occur only in this bucket. The
find contract therefore proves true exactly for keys in the map's domain, with no state change. One hash calculation and one bucket traversal suffice; no insertion is performed during the query.Find the entry once and check the abstract membership precondition on that result:
def recall(name: String): String = {
val entry = find(name, table(hash(name)))
require(entry != null, "name is not in the book")
entry.number
}The check turns an invalid call into an explicit precondition failure rather than an accidental null dereference or an invented default number. For a valid call, the unique matching entry contains exactly the mapped value, so the stored number is returned and the map is unchanged. Testing membership by calling
isInBook first would traverse the same bucket twice; retaining the found reference avoids that redundant work.The relevant quantity is the hash-table load factor , where is the number of distinct keys and the bucket count. With a suitable distribution of hashes, separate chaining has expected operation cost , treating key operations as constant-cost. Keeping only one hundred buckets while grows therefore increases average search length.
Balanced binary search trees could reduce a bucket search from linear time in its occupancy to logarithmic time. Unbalanced binary search trees provide no such guarantee: insertion order can produce a chain. Even balanced trees add comparison and node-management overhead, which may dominate for small buckets.
A usual first remedy is grow the table and rehash its entries, keeping the load factor bounded. Geometric growth gives amortized constant resizing overhead per insertion; with suitable hashing, expected lookup, update and insertion costs remain constant. Resizing is when performed and is not a worst-case constant-time guarantee for that particular operation. Balanced buckets can still be useful for heavy or adversarial collisions, but replacing every bucket tree does not by itself repair a poor hash function. For variable-length strings, hashing and string comparisons add their own character-processing costs.
A single bucket holding about a quarter of all keys suggests severely nonuniform hashing or a strongly skewed/adversarial key set, rather than ordinary load growth alone. With one hundred well-used buckets the expected fraction in one fixed bucket is about one hundredth. Persistent concentration near one quarter is evidence to investigate, not a proof identifying one particular implementation bug.
Inspect the bucket histogram, raw hash outputs and patterns in the names. A hash depending only on an initial character, weak mixing of common prefixes, or an indexing rule using few possible buckets could create this behavior. Improve the hash so that it uses the complete key and spreads this workload across the table, then rehash every stored entry. Check the valid-index rule as well, including negative machine hash values.
Increasing the table size is useful if index reduction caused the concentration; it cannot separate keys that all receive the same raw hash. For maliciously chosen keys, randomized or keyed hashing and balanced collision structures may be appropriate. The observed occupancy does not justify assuming uniformly random hashes in a performance claim.
Articles by others on the same topic
There are currently no matching articles.