Note 6.5.3. Kotlin Note.
The
rehash method has been declared private; nobody outside of HashTableMap should need to call it.
Section 6.5 Implementing a Map and a Set with Hashing
Subsection 6.5.1 Hashtable Map implementation
While Kotlin does provide the
MutableMap class, we will learn more by implementing our own version of it. In Listing 6.5.1 we use a list to create a HashTableMap class that implements the map abstract data type. This list uses a data class named Entry, each of which holds a single key and value.
When we find the
Entry for a key, that same Entry will hold the associated data value. The list of Entries, then will be treated as a hash table using the ideas presented earlier, where the key is used as the input for the hash function. Note that the initial size for the hash table has been chosen to be 11. Although this is arbitrary, it is important that the size be a prime number so that the collision resolution algorithm can be as efficient as possible.
class HashTableMap<K, V> : MapADT<K, V> {
// Each Entry contains a key and a value
data class Entry<K, V>(val key: K, var value: V)
// slots is a list consisting of Entry objects
val size = 11
var slots: MutableList<Entry<K, V>?> = MutableList(size) { null }
// more code here...
}
Now we move on to the process of inserting an entry into the hash table.
In order to make implementation of data structures such as
HashMap easier, every Kotlin object has a hashCode method that returns an integer value. When two objects are equal (as evaluated by the equals method), they are guaranteed to have the same value for their hash codes. There is no guarantee that two different objects will not hash to the same value, but, as the documentation says: “As far as is reasonably practical, the hashCode method defined by class Object returns distinct integers for distinct objects.”
For the
Int class, hashCode returns the integer value. This guarantees distinct integers for distinct objects. For the String class, hashCode uses a formula based on the individual characters in the string. Since hashCode returns an integer, we will then need to use the usual remainder approach to turn it into an index for our list of slots.
For most situations, using these built-in
hashCode methods is sufficient for successfully hashing the data. For the rare situation where we believe our data is systematically skewed in such a way that the built-in approach is not appropriate, typically we would then create a new class (or subclass) representing the type for the key, and override hashCode with our own function.
Aside: How to find out more information about the built-in hash functions.
Listing 6.5.2, shows an implementation of the
put method. The collision resolution technique is linear probing with a “plus 1” rehash value. The put method assumes that there will eventually be an empty slot unless the key is already present in the slots. It computes the original hash value and if that slot is not empty, iterates the rehash function until an empty slot occurs (lines 6–9). If a nonempty slot already contains the key, the old data value is replaced with the new data value.
put method// Assumes that a slot will eventually be found.
override fun put(key: K, value: V) {
var hashSlot = key.hashCode() % slots.count()
var currentEntry = slots[hashSlot]
while (currentEntry != null && (currentEntry.key != key)) {
hashSlot = rehash(hashSlot, slots.count())
currentEntry = slots[hashSlot]
}
if (currentEntry == null) {
slots[hashSlot] = Entry(key, value)
} else {
currentEntry.value = value
}
}
private fun rehash(oldHash: Int, size: Int): Int {
return (oldHash + 1) % size
}
The
get function (see Listing 6.5.4) begins by computing the initial hash value. If the value is not in the initial slot, rehash is used to locate the next possible position. Line 12 guarantees that the search will terminate by checking to make sure that we have not returned to the initial slot. If that happens, we have exhausted all possible slots and the item must not be present.
override fun get(key: K): V? {
val startSlot = key.hashCode() % slots.count()
var position = startSlot
var currentEntry = slots[position]
while (currentEntry != null) {
if (currentEntry.key == key) {
return currentEntry.value
} else {
position = rehash(position, slots.count())
currentEntry = slots[position]
if (position == startSlot) {
return null
}
}
}
return null
}
Listing 6.5.5 shows the
HashTableMap class in action. First we will create a hash table and store some items with integer keys (US postal codes) and string data values (the city with that code), then access and modify values. For each postal code, we show the initial hash value.
HashTableMap ImplementationThe complete hash table example can be found in Listing 6.5.6.
HashTableMap Codeclass HashTableMap<K, V> : MapADT<K, V> {
// Each Entry contains a key and a value
data class Entry<K, V>(val key: K, var value: V)
// slots is a list consisting of Entry objects
val size = 11
var slots: MutableList<Entry<K, V>?> = MutableList(size) { null }
override fun toString(): String {
return slots.toString()
}
// Assumes that a slot will eventually be found.
override fun put(key: K, value: V) {
var hashSlot = key.hashCode() % slots.count()
var currentEntry = slots[hashSlot]
while (currentEntry != null && (currentEntry.key != key)) {
hashSlot = rehash(hashSlot, slots.count())
currentEntry = slots[hashSlot]
}
if (currentEntry == null) {
slots[hashSlot] = Entry(key, value)
} else {
currentEntry.value = value
}
}
private fun rehash(oldHash: Int, size: Int): Int {
return (oldHash + 1) % size
}
override fun get(key: K): V? {
val startSlot = key.hashCode() % slots.count()
var position = startSlot
var currentEntry = slots[position]
while (currentEntry != null) {
if (currentEntry.key == key) {
return currentEntry.value
} else {
position = rehash(position, slots.count())
currentEntry = slots[position]
if (position == startSlot) {
return null
}
}
}
return null
}
// Returns the number of key/value pairs stored in the map
override fun size(): Int {
return slots.count()
}
// Removes the key from the map.
// Returns the matching value stored in the map, or null otherwise.
// Not implemented yet: see exercises below.
override fun remove(key: K): V? {
throw NotImplementedError()
}
// Returns true if the key is in the map, false otherwise.
// Not implemented yet: see exercises below.
override fun containsKey(key: K): Boolean {
throw NotImplementedError()
}
}
Exercises Exercises
1.
Implement the
remove and containsKey methods as described at the beginning of Subsection 6.5.1. As you do this, you may notice that you are duplicating the code involved in finding a key’s slot. Hint: implement a findSlot(key) method that returns a slot number for the key (or -1 if the key is not found), and then rewrite some of the existing code to make use of this new method. This is known as refactoring your code, and that’s what we did when we implemented those methods. Also note that when removing, there’s an added catch in that you need to leave behind some kind of indication that something had been there and was removed. Without doing so, rehashing might fail when looking up something.
2.
If you do implement the
findSlot method, should it be public or private? It is possible to make valid arguments for either choice. Explain what motivated your choice and what factors you considered.
3.
Code a
HashTableSet class, which implements the SetADT interface using a hash table. Use the HashTableMap as a starting point; the code should be very similar. You should be able to get rid of the Entry class completely, and instead make the slot array of the type of the elements being stored in the set.
You have attempted of activities on this page.
