Int to Int hashMap using linear probing.

The key motivation of linear probing hash table is to make the number of entries at each bucket small and constant, such as one. Couple things are noticed in the following implementation:
1. linear probing using a hash function hash(key, step) to generate unique index at each step in order to probe the table.
2. the hash capacity has to set to a primer in order to loop through all possible slots in the table
3. the hash function use random function's nextInt(capacity) to get a random number between 0 and capacity -1.
4. during the steps of probing, the value at the index could be empty or deleted. To differentiate EMPTY slot and DELETED slot, two special flags are used, so this hash doesn't allow value equal to both EMPTY or DELETED.



The current implementation is still in draft stage and may have bugs.

	package org.blueocean.hash;
	import java.util.Arrays;
	import java.util.Random;
	/*
	* an implementation of int to int hash based on open addressing linear probing approach
	*
	* only int[] array is maintained, <k, v> is inserted using a serial of steps and
	* based on a hash function hash(k, step) to find a open slot
	*
	* in order to probe the entire table, the hash capacity has to be a prime
	* when deletion happens a special indicator is used to differentiate it
	* from empty slot.
	*
	*/
	public class IntIntHash {
	private static final int DELETED = Integer.MAX_VALUE;
	private static final int EMPTY = Integer.MIN_VALUE;
	int[] keys;
	int[] values;
	private int capacity;
	private int size;
	private float loadFactor;
	public IntIntHash(){
	capacity = 17;
	size = 0;
	loadFactor = 0.75f;
	keys = new int[capacity];
	values = new int[capacity];
	for(int i = 0; i < capacity; i++)
	values[i] = EMPTY;
	}
	public boolean remove(int k){
	for(int i=0; i<this.capacity; i++){
	int index = hash(k, i);
	if(keys[index] == k && values[index] != EMPTY && values[index] != DELETED){
	values[index] = DELETED;
	return true;
	}
	}
	return false;
	}
	public int get(int k){
	for(int i=0; i<this.capacity; i++){
	int index = hash(k, i);
	if(values[index]==EMPTY)
	return EMPTY;
	if(keys[index] == k ){
	if(values[index] != DELETED)
	return values[index];
	else
	return EMPTY;
	}
	}
	return EMPTY;
	}
	public void put(int k, int v){
	ensureCapacity();
	for(int i=0; i<this.capacity; i++){
	int index = hash(k, i);
	if(values[index] == EMPTY || values[index] == DELETED){
	values[index] = v;
	keys[index] = k;
	size++;
	System.out.format("put key %d value %d at index %d in %d round \n", k, v, index, i);
	return;
	}
	}
	System.out.println("no empty slot found");
	resize(nextPrime(this.capacity+13));
	put(k, v);
	}
	private void ensureCapacity() {
	if(this.size>this.capacity*this.loadFactor)
	resize(nextPrime(this.capacity+13));
	}
	private void resize(int size) {
	System.out.format("capacity %d size %d new capacity %d \n", this.capacity, this.size, size);
	int[] oldValues = values;
	int[] oldKeys = keys;
	this.capacity = size;
	this.size = 0;
	keys = new int[capacity];
	values = new int[capacity];
	for(int i = 0; i < capacity; i++)
	values[i] = EMPTY;
	for(int i=0; i<oldValues.length; i++){
	if(oldValues[i] != EMPTY && oldValues[i] != DELETED){
	put(oldKeys[i], oldValues[i]);
	}
	}
	}
	public int capacity(){
	return this.capacity;
	}
	public int size(){
	return this.size;
	}
	private static final Random GENERATOR = new Random();
	public int hash(int key, int step){
	GENERATOR.setSeed(key);
	int hash = GENERATOR.nextInt(this.capacity);
	for(int i=0; i<step; i++)
	hash = GENERATOR.nextInt(this.capacity);
	return hash;
	// k *= 0xb4b82e39;
	// int shift = 31 - Integer.numberOfTrailingZeros(this.capacity);
	// return (k ^ (k >>> shift)) & (this.capacity - 1);
	//return (k + step) % (this.capacity - 1);
	}
	//the following code is borrowed from Trove Java libary
	public static final int largestPrime;
	private static final int[] primeCapacities = {
	//chunk #1
	5,11,23,47,97,197,397,797,1597,3203,6421,12853,25717,51437,102877,205759,
	411527,823117,1646237,3292489,6584983,13169977,26339969,52679969,105359939,
	210719881,421439783,842879579,1685759167,
	//chunk #2
	433,877,1759,3527,7057,14143,28289,56591,113189,226379,452759,905551,1811107,
	3622219,7244441,14488931,28977863,57955739,115911563,231823147,463646329,927292699,
	1854585413,
	//chunk #3
	953,1907,3821,7643,15287,30577,61169,122347,244703,489407,978821,1957651,3915341,
	7830701,15661423,31322867,62645741,125291483,250582987,501165979,1002331963,
	2004663929,
	//chunk #4
	1039,2081,4177,8363,16729,33461,66923,133853,267713,535481,1070981,2141977,4283963,
	8567929,17135863,34271747,68543509,137087021,274174111,548348231,1096696463,
	//chunk #5
	31,67,137,277,557,1117,2237,4481,8963,17929,35863,71741,143483,286973,573953,
	1147921,2295859,4591721,9183457,18366923,36733847,73467739,146935499,293871013,
	587742049,1175484103,
	//chunk #6
	599,1201,2411,4831,9677,19373,38747,77509,155027,310081,620171,1240361,2480729,
	4961459,9922933,19845871,39691759,79383533,158767069,317534141,635068283,1270136683,
	//chunk #7
	311,631,1277,2557,5119,10243,20507,41017,82037,164089,328213,656429,1312867,
	2625761,5251529,10503061,21006137,42012281,84024581,168049163,336098327,672196673,
	1344393353,
	//chunk #8
	3,7,17,37,79,163,331,673,1361,2729,5471,10949,21911,43853,87719,175447,350899,
	701819,1403641,2807303,5614657,11229331,22458671,44917381,89834777,179669557,
	359339171,718678369,1437356741,
	//chunk #9
	43,89,179,359,719,1439,2879,5779,11579,23159,46327,92657,185323,370661,741337,
	1482707,2965421,5930887,11861791,23723597,47447201,94894427,189788857,379577741,
	759155483,1518310967,
	//chunk #10
	379,761,1523,3049,6101,12203,24407,48817,97649,195311,390647,781301,1562611,
	3125257,6250537,12501169,25002389,50004791,100009607,200019221,400038451,800076929,
	1600153859
	};
	static { //initializer
	// The above prime numbers are formatted for human readability.
	// To find numbers fast, we sort them once and for all.
	Arrays.sort(primeCapacities);
	largestPrime = primeCapacities[primeCapacities.length - 1];
	}
	public static int nextPrime(int desiredCapacity) {
	if (desiredCapacity >= largestPrime) {
	return largestPrime;
	}
	int i = Arrays.binarySearch(primeCapacities, desiredCapacity);
	if (i<0) {
	// desired capacity not found, choose next prime greater
	// than desired capacity
	i = -i -1;
	}
	return primeCapacities[i];
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Generic Int Cuckoo Hash With Stash Implementation

This hash table implementation is based on open addressing approach using Cuckoo algorithm. There are few benefit of it compared to JDK's HashMap:

1. primitive int keys are allowed, compared to only Integer type keys are allowed in JDK's hashMap
2. since there is only one entry per bucket, the worse case of GET/Update operation is O(1), compared to amortized O(1) for JDK's HashMap
3. Internally two arrays are maintained, one is int[] for mapping index to a key, another is the V[] to store the values.

Limitation: all keys must be positive numbers. This can be easily fixed.

import java.io.BufferedReader;

/*
 * this class solves a specific problem, that is, given millions of ids and their assoiciated data, how to build a in-memory cache
 * to store the mapping from id to the data.
 *
 * ids are positive numeric numbers
 *
 * Cuckoo hash is part of open addressing family HashTable, the key of open addressing is that cache collision is controlled or avoided, so the
 * worse case time complexity of GET operation is constant time.
 *
 * id to tags hash table cache implemented by Cuckoo algorithm, cache can be preloaded by parsing a file
 *
 * add a stash to accommodate a few overflow entry
 *
 *
 * for simplicity, all keys are positive
 *
 * @author junminliu@bloomberg.net
 */
public class CuckooIntHashMap<V> {
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private static final int DEFAULT_INIT_CAPACITY = 16;
private volatile static boolean ready;

/*
* public method to create cache singleton
*/
public static <T> CuckooIntHashMap<T> getInstance() throws FileNotFoundException, IOException{

return (CuckooIntHashMap<T>)INSTANCE;
}

//the key index array, map indices of buckets to keys
private int[] keys;
//the buckets
private V[] cache;
//the stash
private Entry<V>[] stash;
private int stashSize;
//the size of the buckets
private int capacity;
//the number of filled buckets
private int size;
//the maximum ratio of size over capacity until resizing
private final float loadFactor;

private final transient IntHashFuncI[] hashFunctions;
static final int PRIME_NUMBER2 =0xb4b82e39;
static final int PRIME_NUMBER3 =0xced1c241;
private static final IntHashFuncI[] HASH_FUNCS = new IntHashFuncI[]{new BitOpHash(PRIME_NUMBER2) , new BitOpHash(PRIME_NUMBER3)};

private static final CuckooIntHashMap<?> INSTANCE = new CuckooIntHashMap();




//this two packaged protected constructors are mainly for unit tests purpose
CuckooIntHashMap() {
this(DEFAULT_INIT_CAPACITY, DEFAULT_LOAD_FACTOR, HASH_FUNCS);
}

CuckooIntHashMap(int iniCapacity, float loadfactor, IntHashFuncI[] hashFuncs){
keys = new int[iniCapacity];
cache = (V[])new Object[iniCapacity];
stash = (Entry<V>[]) new Entry[(int) Math.max(3, Math.log(iniCapacity))];
loadFactor = loadfactor;
capacity = iniCapacity;
hashFunctions = hashFuncs;
hashFunctions[0].reset(capacity);
hashFunctions[1].reset(capacity);
ready = true;
}



public V get(int id){
if(!ready)
throw new IllegalStateException("cache is not ready yet");
for(int i=0; i<2; i++){
int index = //keys[id];
hashFunctions[i].hash(id, capacity);
if(keys[index] == id &&  cache[index]!=null)
return cache[index];
}

for(Entry e: stash){
if(e!=null && e.id == id)
return (V)e.tags;
}

return null;
}

boolean insert(int id, V tags){
return insert(id, tags, true);
}

/*
* boolean flag indicating if it is new insertion (true) or rehashing (false)
*/
boolean insert(int id, V tags, boolean flag){
for(int i=0; i<2; i++){
int index = hashFunctions[i].hash(id, capacity);
if(cache[index]==null){
cache[index] = tags;
keys[index] = id; // map index to key
if(flag)
this.size++;
return true;
}
}
return false;
}

void put(int id, V tags){
put(id, tags, true);
}

void put(int id, V tags, boolean flag){
//tags = Collections.unmodifiableSet(tags);
ensureCapacity(id);

if(this.insert(id, tags, flag))
return;
//start the cuckoo bullying process
V insert = tags;
V current = tags;

int currentId = id;
int counter = 0;
int index = hashFunctions[0].hash(id, capacity);
while(counter++<this.capacity || current!=insert ){
if(cache[index]==null){
cache[index] = current;
keys[index] = currentId;
if(flag)
size++;
return;
}

int tempId = keys[index];
V tempSet = cache[index];

keys[index] = currentId;
cache[index] = current;

current = tempSet;
currentId = tempId;

if(index == hashFunctions[0].hash(currentId, capacity))
index = hashFunctions[1].hash(currentId, capacity);
else
index = hashFunctions[0].hash(currentId, capacity);
}

//try stashing before rehash
if(stash(id, tags, flag))
return;
System.out.println("stash is full " + this.stashSize);
rehash(this.capacity<<1);
put(id, tags, flag);
}

boolean stash(int id, V tags, boolean flag){
if(stashSize+1<=stash.length){
stash[stashSize++] = new Entry<V>(id, tags);
return true;
}
return false;
}

/*
* since stash size is small, it won't count toward loadFactor
*/
private void ensureCapacity (int id) {
if(this.size>=this.loadFactor*this.capacity){
System.out.format("ensureCapacity %d, %d %d %f", id, this.size, this.capacity,  this.loadFactor);
rehash(this.capacity<<1);
}
}

/*
* rehash the entries by increasing hash table size to next power of 2
*/
private void rehash(int newSize) {
System.out.println("rehash to " + newSize);
int temp = this.size;
this.capacity = newSize;
hashFunctions[0].reset(capacity);
hashFunctions[1].reset(capacity);
V[] oldCache = cache;
Entry<V>[] oldStash = stash;
int[] oldKeys = keys;

cache = (V[])new Object[newSize];
stash = (Entry<V>[])new Entry[(int) Math.max(3, Math.log(capacity))];
stashSize = 0;
keys = new int[newSize];
for(int i=0; i< oldKeys.length; i++){
if(oldKeys[i]!=0 && oldCache[i]!=null)
this.put(oldKeys[i], oldCache[i], false);
}

for(Entry<V> e : oldStash){
if(e!=null)
this.put(e.id, e.tags, false);
}

this.size = temp;
System.out.format("rehash done and size excluding stash is %d and stash size is %d \n",  this.size, this.stashSize);
}

//int-keyed entity tags HashMap entry, immutable
final class Entry<V> {
private final int id;
private final V tags;
public Entry(final int id, final V tags) {
this.id = id;
this.tags = tags;
}
int getId(){
return id;
}

public V getTags() {
return tags;
}
}

//implementation of hash function using bit operation
static class BitOpHash implements IntHashFuncI {
private final int prime;
private int shift;

BitOpHash(int prime){
this.prime = prime;
}
@Override
public int hash(int key, int range){
key *= prime;
   return (key ^ (key >>> shift)) & (range - 1);
}

@Override
public void reset(int range) {
shift = 31 - Integer.numberOfTrailingZeros(range);
}
}

//implementation of hash function using random generator
static class HashFunc implements IntHashFuncI {
private static final Random GENERATOR = new Random();
private int round;
HashFunc(int loop){
round = loop;
}
@Override
public int hash(int key, int range){
GENERATOR.setSeed(key);
int hash = GENERATOR.nextInt(range);
for(int i=0; i<this.round; i++)
hash = GENERATOR.nextInt(range);
return hash;
}
@Override
public void reset(int range){}
}

static interface IntHashFuncI {
public int hash(int key, int range);
public void reset(int range);
}

/*
* a special implementation of string intern which is faster than JDK version
*/
private static final ConcurrentMap<String, String> TAG_POOL = new ConcurrentHashMap<String, String>();
public static String intern(String s) {
String result = TAG_POOL.get(s);
if (result == null) {
result = TAG_POOL.putIfAbsent(s, s);
if (result == null)
result = s;
}
return result;
}

public int size(){
return this.size;
}

public int capacity(){
return this.capacity;
}
}