I'm studying on hash table with chaining in java by its implementation. The trouble is about get() method. An index value is determined with key.hashCode() % table.length. Assume that the table size is 10 and key.hashCode() is 124 so index is found as 4. In for each loop table[index] is started from table[4], AFAIK index is being incremented one by one 4,5,6,7... so on. But what about indices 0,1,2,3? Are they been checked? (I think no) Isn't there any possibility that occurring of key on one of the indices? (I think yes). The other issue that there are null checks but initially there is no any null assignment for key and value. So how can the checking work? Is null assigned as soon as private LinkedList<Entry<K, V>>[] table is declared?
// Data Structures: Abstraction and Design Using Java, Koffman, Wolfgang
package KW.CH07;
import java.util.AbstractMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.StringJoiner;
/**
* Hash table implementation using chaining.
* @param <K> The key type
* @param <V> The value type
* @author Koffman and Wolfgang
**/
public class HashtableChain<K, V>
// Insert solution to programming project 7, chapter -1 here
implements KWHashMap<K, V> {
/** The table */
private LinkedList<Entry<K, V>>[] table;
/** The number of keys */
private int numKeys;
/** The capacity */
private static final int CAPACITY = 101;
/** The maximum load factor */
private static final double LOAD_THRESHOLD = 3.0;
// Note this is equivalent to java.util.AbstractMap.SimpleEntry
/** Contains key-value pairs for a hash table.
@param <K> the key type
@param <V> the value type
*/
public static class Entry<K, V>
// Insert solution to programming project 6, chapter -1 here
{
/** The key */
private final K key;
/** The value */
private V value;
/**
* Creates a new key-value pair.
* @param key The key
* @param value The value
*/
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
/**
* Retrieves the key.
* @return The key
*/
@Override
public K getKey() {
return key;
}
/**
* Retrieves the value.
* @return The value
*/
@Override
public V getValue() {
return value;
}
/**
* Sets the value.
* @param val The new value
* @return The old value
*/
@Override
public V setValue(V val) {
V oldVal = value;
value = val;
return oldVal;
}
// Insert solution to programming exercise 3, section 4, chapter 7 here
}
// Constructor
public HashtableChain() {
table = new LinkedList[CAPACITY];
}
// Constructor for test purposes
HashtableChain(int capacity) {
table = new LinkedList[capacity];
}
/**
* Method get for class HashtableChain.
* @param key The key being sought
* @return The value associated with this key if found;
* otherwise, null
*/
@Override
public V get(Object key) {
int index = key.hashCode() % table.length;
if (index < 0) {
index += table.length;
}
if (table[index] == null) {
return null; // key is not in the table.
}
// Search the list at table[index] to find the key.
for (Entry<K, V> nextItem : table[index]) {
if (nextItem.getKey().equals(key)) {
return nextItem.getValue();
}
}
// assert: key is not in the table.
return null;
}
/**
* Method put for class HashtableChain.
* @post This key-value pair is inserted in the
* table and numKeys is incremented. If the key is already
* in the table, its value is changed to the argument
* value and numKeys is not changed.
* @param key The key of item being inserted
* @param value The value for this key
* @return The old value associated with this key if
* found; otherwise, null
*/
@Override
public V put(K key, V value) {
int index = key.hashCode() % table.length;
if (index < 0) {
index += table.length;
}
if (table[index] == null) {
// Create a new linked list at table[index].
table[index] = new LinkedList<>();
}
// Search the list at table[index] to find the key.
for (Entry<K, V> nextItem : table[index]) {
// If the search is successful, replace the old value.
if (nextItem.getKey().equals(key)) {
// Replace value for this key.
V oldVal = nextItem.getValue();
nextItem.setValue(value);
return oldVal;
}
}
// assert: key is not in the table, add new item.
table[index].addFirst(new Entry<>(key, value));
numKeys++;
if (numKeys > (LOAD_THRESHOLD * table.length)) {
rehash();
}
return null;
}
/** Returns true if empty
@return true if empty
*/
@Override
public boolean isEmpty() {
return numKeys == 0;
}
}
Assume that the table size is 10 and key.hashCode() is 124 so index is found as 4. In for each loop table[index] is started from table[4]
Correct.
there are null checks but initially there is no any null assignment for key and value. So how can the checking work?
When an array of objects is initialized, all values are set to null.
index is being incremented one by one 4,5,6,7... so on. But what about indices 0,1,2,3? Are they been checked? (I think no) Isn't there any possibility that occurring of key on one of the indices? (I think yes).
Looks like there's some misunderstanding here. First, think of the data structure like this (with data having already been added to it):
table:
[0] -> null
[1] -> LinkedList -> item 1 -> item 2 -> item 3
[2] -> LinkedList -> item 1
[3] -> null
[4] -> LinkedList -> item 1 -> item 2
[5] -> LinkedList -> item 1 -> item 2 -> item 3 -> item 4
[6] -> null
Another important point is that the hash code for a given key should not change, so it will always map to the same index in the table.
So say we call get with a value who's hash code maps it to 3, then we know that it's not in the table:
if (table[index] == null) {
return null; // key is not in the table.
}
If another key comes in that maps to 1, now we need to iterate over the LinkedList:
// LinkedList<Entry<K, V>> list = table[index]
for (Entry<K, V> nextItem : table[index]) {
// iterate over item 1, item 2, item 3 until we find one that is equal.
if (nextItem.getKey().equals(key)) {
return nextItem.getValue();
}
}