http://www.algolist.net/Data_structures/Hash_table/Open_addressing
As it was mentioned above, table may need resizing in two cases: it is filled too tight (loadFactor > thresholdMax) or it is filled too rare (loadFactor < thresholdMin). We consider only the first case here to maintain simplicity. Java implementation is done for open addressing based hash table and C++ one is done for hash table with chaining. Highlighted code strings refer to functionality responsible for resizing.
Removal operation
There are several nuances, when removing a key from hash table with open addressing. Consider following situation:
If algorithm simply frees "Sandra Miller" bucket, structure of the table will get broken. Algorithm won't succeed trying to find "Andrew Wilson" key. Indeed, "Andrew Wilson" key is hashed to the "red slot". The slot contains different key and linear probing algorithm will try to find "Andrew Wilson" in the consequent bucket, but it is empty:
The solution is as following. Instead of just erasing the key, algorithm writes special "DELETED" value to the slot.
Now lookup algorithm will work properly. Insertion algorithm should reuse deleted slots, when possible.
Note. This algorithm resolves problem, but with time hash table will become clogged with "DELETED" entries, which badly affects performance. If hash table should allow items' removal, then chaining is more preferable way to resolve collisions.
Open addressing vs. chaining
| Chaining | Open addressing | |
| Collision resolution | Using external data structure | Using hash table itself |
| Memory waste | Pointer size overhead per entry (storing list heads in the table) | No overhead 1 |
| Performance dependence on table's load factor | Directly proportional | Proportional to (loadFactor) / (1 - loadFactor) |
| Allow to store more items, than hash table size | Yes | No. Moreover, it's recommended to keep table's load factor below 0.7 |
| Hash function requirements | Uniform distribution | Uniform distribution, should avoid clustering |
| Handle removals | Removals are ok | Removals clog the hash table with "DELETED" entries |
| Implementation | Simple | Correct implementation of open addressing based hash table is quite tricky |
public class HashEntry {
private int key;
private int value;
}
public class DeletedEntry extends HashEntry {
private static DeletedEntry entry = null;
private DeletedEntry() {
super(-1, -1);
}
public static DeletedEntry getUniqueDeletedEntry() {
if (entry == null)
entry = new DeletedEntry();
return entry;
}
}
public class HashMap {
private final static int TABLE_SIZE = 128;
HashEntry[] table;
HashMap() {
table = new HashEntry[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = null;
}
public int get(int key) {
int hash = (key % TABLE_SIZE);
int initialHash = -1;
while (hash != initialHash
&& (table[hash] == DeletedEntry.getUniqueDeletedEntry() ||table[hash] != null
&& table[hash].getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
hash = (hash + 1) % TABLE_SIZE;
}
if (table[hash] == null || hash == initialHash)
return -1;
else
return table[hash].getValue();
}
public void put(int key, int value) {
int hash = (key % TABLE_SIZE);
int initialHash = -1;
int indexOfDeletedEntry = -1;
while (hash != initialHash
&& (table[hash] == DeletedEntry.getUniqueDeletedEntry() ||table[hash] != null
&& table[hash].getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
if (table[hash] == DeletedEntry.getUniqueDeletedEntry())
indexOfDeletedEntry = hash;
hash = (hash + 1) % TABLE_SIZE;
}
if ((table[hash] == null || hash == initialHash)
&& indexOfDeletedEntry != -1)
table[indexOfDeletedEntry] = new HashEntry(key, value);
else if (initialHash != hash)
if (table[hash] != DeletedEntry.getUniqueDeletedEntry()
&& table[hash] != null && table[hash].getKey() == key)
table[hash].setValue(value);
else
table[hash] = new HashEntry(key, value);
}
public void remove(int key) {
int hash = (key % TABLE_SIZE);
int initialHash = -1;
while (hash != initialHash
&& (table[hash] == DeletedEntry.getUniqueDeletedEntry() ||table[hash] != null
&& table[hash].getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
hash = (hash + 1) % TABLE_SIZE;
}
if (hash != initialHash && table[hash] != null)
table[hash] = DeletedEntry.getUniqueDeletedEntry();
}
}
http://www.algolist.net/Data_structures/Hash_table/Dynamic_resizingAs it was mentioned above, table may need resizing in two cases: it is filled too tight (loadFactor > thresholdMax) or it is filled too rare (loadFactor < thresholdMin). We consider only the first case here to maintain simplicity. Java implementation is done for open addressing based hash table and C++ one is done for hash table with chaining. Highlighted code strings refer to functionality responsible for resizing.
public class HashMap {
private final int DEFAULT_TABLE_SIZE = 128;
private float threshold = 0.75f;
private int maxSize = 96;
private int size = 0;
HashEntry[] table;
HashMap() {
table = new HashEntry[DEFAULT_TABLE_SIZE];
for (int i = 0; i < DEFAULT_TABLE_SIZE; i++)
table[i] = null;
}
void setThreshold(float threshold) {
this.threshold = threshold;
maxSize = (int) (table.length * threshold);
}
public int get(int key) {
int hash = (key % table.length);
int initialHash = -1;
while (hash != initialHash
&& (table[hash] == DeletedEntry.getUniqueDeletedEntry()
|| table[hash] != null
&& table[hash].getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
hash = (hash + 1) % table.length;
}
if (table[hash] == null || hash == initialHash)
return -1;
else
return table[hash].getValue();
}
public void put(int key, int value) {
int hash = (key % table.length);
int initialHash = -1;
int indexOfDeletedEntry = -1;
while (hash != initialHash
&& (table[hash] == DeletedEntry.getUniqueDeletedEntry()
|| table[hash] != null
&& table[hash].getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
if (table[hash] == DeletedEntry.getUniqueDeletedEntry())
indexOfDeletedEntry = hash;
hash = (hash + 1) % table.length;
}
if ((table[hash] == null || hash == initialHash)
&& indexOfDeletedEntry != -1) {
table[indexOfDeletedEntry] = new HashEntry(key, value);
size++;
} else if (initialHash != hash)
if (table[hash] != DeletedEntry.getUniqueDeletedEntry()
&& table[hash] != null && table[hash].getKey() == key)
table[hash].setValue(value);
else {
table[hash] = new HashEntry(key, value);
size++;
}
if (size >= maxSize)
resize();
}
private void resize() {
int tableSize = 2 * table.length;
maxSize = (int) (tableSize * threshold);
HashEntry[] oldTable = table;
table = new HashEntry[tableSize];
size = 0;
for (int i = 0; i < oldTable.length; i++)
if (oldTable[i] != null
&& oldTable[i] != DeletedEntry.getUniqueDeletedEntry())
put(oldTable[i].getKey(), oldTable[i].getValue());
}
public void remove(int key) {
int hash = (key % table.length);
int initialHash = -1;
while (hash != initialHash
&& (table[hash] == DeletedEntry.getUniqueDeletedEntry()
|| table[hash] != null
&& table[hash].getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
hash = (hash + 1) % table.length;
}
if (hash != initialHash && table[hash] != null) {
table[hash] = DeletedEntry.getUniqueDeletedEntry();
size--;
}
}
}
https://highlyscalable.wordpress.com/2011/12/29/ultimate-sets-and-maps-for-java-p1/public class OpenAddressingSet { protected int keys[]; protected int capacity; protected int size; protected static final int FREE = -1; public OpenAddressingSet(int capacity, double loadFactor) { this.capacity = capacity; int tableSize = MathUtils.nextPrime( ((int)(capacity / loadFactor)) ); keys = new int[tableSize]; Arrays.fill(keys, FREE); } public boolean contains(int key) { return indexOfKey(key) >= 0; } public boolean add(int key) { if(size >= capacity) { throw new IllegalArgumentException("Set is full"); } boolean result; result = addInternal(key); if(result) { size++; } return result; } protected boolean addInternal(int key) { int position = indexOfKey(key); boolean added = false; if(position < 0) { position = -position-1; added = true; } keys[position] = key; return added; } private int indexOfKey(int key) { final int length = keys.length; int startPosition = key % length; // the first hash function int step = 1 + (key % (length-2)); // the second hash function while (keys[startPosition] != key && keys[startPosition] != FREE) { startPosition -= step; if (startPosition < 0) { startPosition += length; } } if(keys[startPosition] == FREE) { return -startPosition-1; } return startPosition; }}