http://www.algolist.net/Data_structures/Hash_table
Hash table and load factor
Chaining is a possible way to resolve collisions. Each slot of the array contains a link to a singly-linked listcontaining 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.
With the growth of hash table's load factor, number of collisions increases, which leads to the decrease of overall table's performance. It is bearable for hash tables with chaining, but unacceptable for hash tables based on open addressing due to essential performance drop. The solution is to resize table, when its load factor exceeds given threshold.
Hash table and load factor
Basic underlying data strucutre used to store hash table is an array. The load factor is the ratio between the number of stored items and array's size. Hash table can whether be of a constant size or being dynamically resized, when load factor exceeds some threshold. Resizing is done before the table becomes full to keep the number of collisions under certain amount and prevent performance degradation.
Collisions
What happens, if hash function returns the same hash value for different keys? It yields an effect, calledcollision. Collisions are practically unavoidable and should be considered when one implements hash table. Due to collisions, keys are also stored in the table, so one can distinguish between key-value pairs having the same hash. There are various ways of collision resolution. Basically, there are two different strategies:
- Closed addressing (open hashing). Each slot of the hash table contains a link to another data structure (i.e. linked list), which stores key-value pairs with the same hash. When collision occures, this data structure is searched for key-value pair, which matches the key.
- Open addressing (closed hashing). Each slot actually contains a key-value pair. When collision occurs, open addressing algorithm calculates another location (i.e. next one) to locate a free slot. Hash tables, based on open addressing strategy experience drastic performance decrease, when table is tightly filled (load factor is 0.7 or more).
Chaining is a possible way to resolve collisions. Each slot of the array contains a link to a singly-linked listcontaining 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.
public class LinkedHashEntry {
private int key;
private int value;
private LinkedHashEntry 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());
}
}
}
}
Hash table. Dynamic resizingWith the growth of hash table's load factor, number of collisions increases, which leads to the decrease of overall table's performance. It is bearable for hash tables with chaining, but unacceptable for hash tables based on open addressing due to essential performance drop. The solution is to resize table, when its load factor exceeds given threshold.
class HashMap {
private:
float threshold;
int maxSize;
int tableSize;
int size;
LinkedHashEntry **table;
void resize() {
int oldTableSize = tableSize;
tableSize *= 2;
maxSize = (int) (tableSize * threshold);
LinkedHashEntry **oldTable = table;
table = new LinkedHashEntry*[tableSize];
for (int i = 0; i < tableSize; i++)
table[i] = NULL;
size = 0;
for (int hash = 0; hash < oldTableSize; hash++)
if (oldTable[hash] != NULL) {
LinkedHashEntry *oldEntry;
LinkedHashEntry *entry = oldTable[hash];
while (entry != NULL) {
put(entry->getKey(), entry->getValue());
oldEntry = entry;
entry = entry->getNext();
delete oldEntry;
}
}
delete[] oldTable;
}
public:
HashMap() {
threshold = 0.75f;
maxSize = 96;
tableSize = DEFAULT_TABLE_SIZE;
size = 0;
table = new LinkedHashEntry*[tableSize];
for (int i = 0; i < tableSize; i++)
table[i] = NULL;
}
void setThreshold(float threshold) {
this->threshold = threshold;
maxSize = (int) (tableSize * threshold);
}
int get(int key) {
int hash = (key % tableSize);
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 % tableSize);
if (table[hash] == NULL) {
table[hash] = new LinkedHashEntry(key, value);
size++;
} else {
LinkedHashEntry *entry = table[hash];
while (entry->getNext() != NULL)
entry = entry->getNext();
if (entry->getKey() == key)
entry->setValue(value);
else {
entry->setNext(new LinkedHashEntry(key, value));
size++;
}
}
if (size >= maxSize)
resize();
}
void remove(int key) {
int hash = (key % tableSize);
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);
}
size--;
}
}
}
~HashMap() {
for (int hash = 0; hash < tableSize; hash++)
if (table[hash] != NULL) {
LinkedHashEntry *prevEntry = NULL;
LinkedHashEntry *entry = table[hash];
while (entry != NULL) {
prevEntry = entry;
entry = entry->getNext();
delete prevEntry;
}
}
delete[] table;
}
};
Read full article from HASH TABLE :: CHAINING (Java, C++) | Algorithms and Data Structures