Question

1) Using Java. Insert the key sequence [29, 33, 1, 37, 32, 26, 48, 11 , 40, 17, 36, 12, 41, 25, 30, 23, 28, 39, 6, 43] with hashing by chaining in a hash table with size 17. Use the hash function: h(k) = k mod 17.

a) Show the final table.

b) Indicate at which insertion the first collision occurred.

c) Indicate which index that has the longest chain.

Answer 1

1)following code impliments the hashing by chaining in java.

public class LinkedHashEntry {
private int key;
private int value;
private LinkedHashEntry next;

LinkedHashEntry(int key, int value) {
this.key = key;
this.value = value;
this.next = null;
}

public int getValue() {
return value;
}

public void setValue(int value) {
this.value = value;
}

public int getKey() {
return key;
}

public LinkedHashEntry getNext() {
return next;
}

public void setNext(LinkedHashEntry next) {
this.next = next;
}
}
public class HashMap {
private final static int TABLE_SIZE = 128;

LinkedHashEntry[] table;

HashMap() {
table = new LinkedHashEntry[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = null;
}

public int get(int key) {
int hash = (key % TABLE_SIZE);
if (table[hash] == null)
return -1;
else {
LinkedHashEntry entry = table[hash];
while (entry != null && entry.getKey() != key)
entry = entry.getNext();
if (entry == null)
return -1;
else
return entry.getValue();
}
}

public void put(int key, int value) {
int hash = (key % TABLE_SIZE);
if (table[hash] == null)
table[hash] = new LinkedHashEntry(key, value);
else {
LinkedHashEntry entry = table[hash];
while (entry.getNext() != null && entry.getKey() != key)
entry = entry.getNext();
if (entry.getKey() == key)
entry.setValue(value);
else
entry.setNext(new LinkedHashEntry(key, value));
}
}

public void remove(int key) {
int hash = (key % TABLE_SIZE);
if (table[hash] != null) {
LinkedHashEntry prevEntry = null;
LinkedHashEntry entry = table[hash];
while (entry.getNext() != null && entry.getKey() != key) {
prevEntry = entry;
entry = entry.getNext();
}
if (entry.getKey() == key) {
if (prevEntry == null)
table[hash] = entry.getNext();
else
prevEntry.setNext(entry.getNext());
}
}
}
}

following image explains the final hash table and collision chain that occurs.

here have even choose the 17 as the table size since it is the prime number.