Hash table. Collision resolution by chaining (closed addressing)
Chaining is a possible way to resolve collisions. Each slot of the array contains a link to a singly-linked list containing key-value pairs with the same hash. New key-value pairs are added to the end of the list. Lookup algorithm searches through the list to find matching key. Initially table slots contain nulls. List is being created, when value with the certain hash is added for the first time.
Chaining illustration
Complexity analysis
Assuming, that hash function distributes hash codes uniformly and table allows dynamic resizing, amortized complexity of insertion, removal and lookup operations is constant. Actual time, taken by those operations linearly depends on table's load factor.
Note. Even substantially overloaded hash table, based on chaining, shows well performance. Assume hash table with 1000 slots storing 100000 items (load factor is 100). It requires a bit more memory (size of the table), than a singly-linked list, but all basic operations will be done about 1000 times faster on average. Draw attention, that computational complexity of both singly-linked list and constant-sized hash table is O(n).
Chaining vs. open addressing
See open addressing vs. chaining.
Code snippets
Code given below implements chaining with list heads. It means, that hash table entries contain first element of a linked-list, instead of storing pointer to it.
Java implementation
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());
}
}
}
}
C++ implementation
class LinkedHashEntry {
private:
int key;
int value;
LinkedHashEntry *next;
public:
LinkedHashEntry(int key, int value) {
this->key = key;
this->value = value;
this->next = NULL;
}
int getKey() {
return key;
}
int getValue() {
return value;
}
void setValue(int value) {
this->value = value;
}
LinkedHashEntry *getNext() {
return next;
}
void setNext(LinkedHashEntry *next) {
this->next = next;
}
};
const int TABLE_SIZE = 128;
class HashMap {
private:
LinkedHashEntry **table;
public:
HashMap() {
table = new LinkedHashEntry*[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = NULL;
}
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();
}
}
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 = entry->getNext();
if (entry->getKey() == key)
entry->setValue(value);
elseentry->setNext(new LinkedHashEntry(key, value));
}
}
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) {
LinkedHashEntry *nextEntry = entry->getNext();
delete entry;
table[hash] = nextEntry;
} else {
LinkedHashEntry *next = entry->getNext();
delete entry;
prevEntry->setNext(next);
}
}
}
}
~HashMap() {
for (int i = 0; i < TABLE_SIZE; i++)
if (table[i] != NULL) {
LinkedHashEntry *prevEntry = NULL;
LinkedHashEntry *entry = table[i];
while (entry != NULL) {
prevEntry = entry;
entry = entry->getNext();
delete prevEntry;
}
}
delete[] table;
}
};
| Previous: The very simple hash table example | Next: Open addressing |
Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.
Every dollar helps!