4.2.6.1, 4.2.7.1 - Hash tables and dictionaries (VB.NET)
Map keys to values, apply a simple hash with collision handling, and use VB.NET dictionaries for retrieval and counting. This route uses written code with no Run: incomplete: runnable support pending.
Key-value structures
A key identifies a stored value without relying on its position in a sequence.
Dictionary
A collection of key-value pairs in which a value is accessed through its associated key.
A product catalogue can map a product code to its record; a word-frequency dictionary maps a word to its count. Keys must be unique within the dictionary, but values need not be: two products can have the same price. Updating a key changes its associated value rather than creating a second instance of that key.
A hash table implements key lookup by calculating a hash and using it to select a storage location. It is a data structure that maps keys to values; a dictionary describes the collection and its operations and need not be implemented using hashing. Keep the original key with its value so that lookup can distinguish keys that share a hash.
For a student system, mapping student ID to a record avoids scanning all records for ordinary retrieval. A suitable hash distributes keys across the available slots, reducing collisions. This concerns lookup efficiency; it does not mean the hash is an encryption function or that different keys always have different hashes.
Simple hashing
A simple hash transforms a key into a valid slot index.
For non-negative integer keys and a table of size 7, use . Key 10 maps to slot 3, 17 also maps to slot 3, and 6 maps to slot 6. The corresponding native expression is key Mod 7. The remainder is in the range 0 through 6 because these keys are non-negative. Negative keys need a specified normalisation rule because VB.NET's Mod can yield a negative result.
A string key can be transformed by summing character codes then taking a remainder. With the explicit simplified alphabet mapping A=1, B=2, …, Z=26, CAT has sum 3+1+20=24, so its slot is 3 in a seven-slot table. This deliberately simple teaching hash gives anagrams the same sum; a practical hash aims for a better distribution.
The table size, key transformation and any collision policy must be supplied before tracing. A large key is not itself a large array index after hashing. Two different keys may hash to the same slot even if their original values are far apart.
Collisions and rehashing
A collision occurs when two key values compute the same hash, requiring a rule for finding another place.
In this lesson rehashing uses the next candidate slot (slot + 1) Mod size, also called linear probing. This is a collision-resolution rule, distinct from rebuilding the whole table at a new capacity. Other supplied rehash functions can produce a different probe sequence.
For size 7, insert 10 at slot 3. Key 17 collides there and goes to 4; key 24 also hashes to 3, checks 3 then 4, and goes to 5. Lookup for 24 must follow the same sequence and compare stored keys, not merely return whatever is at slot 3. Stop at an unused slot or after checking the entire table. A fixed table is full when every slot is occupied; otherwise unrestricted probing could loop forever.
This function belongs inside a module and inserts or updates a non-negative key. Arrays have equal, nonzero length, used tracks occupancy, and values are Strings. Zero is a legitimate key, so a separate occupancy array is used.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account