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.

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;
}
}

Cuckoo hash table

As we all know search in a list is O(n), search in a binary search tree is O(logN), and hash is O(1).

There are two critical aspects for designing hash, one is the hash function; the other is the hash collision, which in worse case will turn a hash table into linked list, if the chaining approach is used in constructing hash.

There are several ways to build hash table without any collisions or pre-defined bucket size. Cuckoo hash table is one of them. Cuckoo is one kind of birds who kicks off the host's egg and put its own in. See this link http://www.nwf.org/news-and-magazines/national-wildlife/birds/archives/1997/bullies-of-the-bird-world.aspx

Cuckoo hash do exactly the same, there is one interesting paper written by a group of computer scientists from CMU, Cuckoo Filter: Practically Better Than Bloom, they developed a cuckoo algorithm which performs better than bloom function.

The below is my untested version of cuckoo hash.

import java.util.Collections;

import java.util.Random;

public class CuckooHash {

//the buckets

private Entry[] cache;

//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;

public CuckooHash(int iniCapacity, float loadfactor){
this(iniCapacity, loadfactor, new IntHashFuncI[]{new HashFunc(1) , new HashFunc(2)});
}

CuckooHash() {
this(16, 0.75f, new IntHashFuncI[]{new HashFunc(1) , new HashFunc(2)});
}

private CuckooHash(int iniCapacity, float loadfactor, IntHashFuncI[] hashFuncs){
cache = new Entry[iniCapacity];
loadFactor = loadfactor;
capacity = iniCapacity;
hashFunctions = hashFuncs;

}

public Object get(int id){

for(int i=0; i<2; i++){
int index = hashFunctions[i].hash(id, capacity);
if(cache[index]!=null && cache[index].id == id)
return cache[index].t;
}
return null;
}

boolean insert(int id, Object tags){
for(int i=0; i<2; i++){
int index = hashFunctions[i].hash(id, capacity);
if(cache[index]==null){
cache[index] = new Entry(id, t);
this.size++;

return true;

}
}

return false;

}

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);
}
}

 

void put(int id, Object t){
ensureCapacity(id);

if(this.insert(id, t))

return;

//start the cuckoo bullying process

Entry insert = new Entry(id, t);
Entry current = insert;
int counter = 0;
int index = hashFunctions[0].hash(id, capacity);
while(counter++<this.capacity || current!=insert ){
if(cache[index]==null){
cache[index] = current;
size++;

return;

}
Entry temp = cache[index];
cache[index] = current;
current = temp;

if(index == hashFunctions[0].hash(current.id, capacity))
index = hashFunctions[1].hash(current.id, capacity);

else

index = hashFunctions[0].hash(current.id, capacity);
}

rehash(this.capacity<<1);
put(id, t);
}

//double hash table size

private void rehash(int newSize) {
System.out.println("rehash to " + newSize);
int temp = this.size;
this.capacity = newSize;
Entry[] oldCache = cache;
cache = new Entry[newSize];
for(Entry e : oldCache){
if(e!=null)
this.put(e.id, e.tags);
}
this.size = temp;
System.out.println("rehash and size is " + this.size);
}

//int primitive HashMap entry

private class Entry {

private final int id;

private final Object t;
public Entry(int id, Object t) {
super();
this.id = id;
this.t = t;
}
}

static class HashFunc implements IntHashFuncI {
private static final Random GENERATOR = new Random();

private int round;

HashFunc(int loop){
round = loop;
}

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;
}
}

private static interface IntHashFuncI {

public int hash(int key, int range);
}

}

In-place rearrangement - Index-based sort - parking lot problem

Image we have a parking lot with 100 spots, there are 99 cars in each spot, and given one empty spot and array of random unique integers between 0 and 98, e.g. 1, 3, 5, 0, 2, 4.., we want to move cars at index i to array[i].  We can only move car from one spot to another spot, can't park car in any places except those designated spots.

The above similar is analogous to a problem we could face in sorting application, sometimes we have to rearrange the blocks in a disk so we can scan the blocks repeatedly in certain order.  If the disk is full, then we have to rearrange the blocks in-place. Loading one block into memory is to park one car in the extra spot.

This issue is also related to index-based sort problem, that is if the data sort we need to sort is big, in stead of sorting the data, we index the record then sort the indices in stead.

The basic in-place array rearrangement operation is called rotation. We can define a rotation operation at index i like this:

input: array[i], 3, 2, 1, n-1, ..., 0

int startPos = i;

int next_value = array[startPos];

while( startPos ! = next_value ){
       int next_index = next_value;
       next_value = array[next_index];

       array[next_index] = startPos;
       startPos  = next_index;

       if(next_index == i)
              break;
}

One thing we need to improve above is to label the item which we already process, we can simply do negation operation on it. Here is the code:

public static void circleArrange(int[] array){

for(int i=0; i<array.length; i++){

if(array[i]<0) //negative item is already moved

continue;

int startPos = i;

int next_value = array[startPos];

while( startPos != next_value ){

int next_index = next_value;

next_value = array[next_index];

array[next_index] = (startPos + 1) * -1; //mark it negative 

startPos  = next_index;

if(next_index == i)

break;

}

}

for(int i = 0; i< array.length; i++){

if(array[i]<0)

array[i] = array[i]*-1 -1;

}

}

Circular Sort: an improved insertion sort algorithm

Insertion sort is great, it is in place, online, and stable, usually faster than selection sort and bubble sort.
Selection sort is the one of the sort algorithm using the least number of swaps, which is usually when swap in memory operation is expensive such as in flash.

In reality if the input is partially sorted or input size is small, insertion sort is quicker than quick sort.
When the input size is small, some of the fast sorting algorithms implementation, e.g. in Java, when using quick sort, heap sort, merge sort will fall back to insertion sort. The problem with insertion sort is the numbers of potential moves or shifts in array could be O(n^2), e.g. if the array is in reverse order.

Circular sort is an improved version of insertion sort which using circular buffer or circular array to solve the insertion sort problem.

I strongly recommend you to read the wiki page about circular buffer (cb), http://en.wikipedia.org/wiki/Circular_buffer.

A simple CB implementation involves a start, end pointer and buffer size parameter. An elegant CB implementation using mirroring algorithm.

Here is the code doing circular sort, which essentially an insertion sort, but can append to front and end in O(1) time thanks to the circular buffer.

public static int[] circularSort(int[] nums){

int len = nums.length;

int[] cb = new int[len];

cb[len/2] = nums[0];

int start = len/2, end = len/2;

for(int i=1; i<len; i++){

//if nums[i] is the smallest, append to the front

if(nums[i]<=cb[start]){

start = start == 0? len-1:start-1;

cb[start] = nums[i];

//if nums[i] is the biggest, append to the end

}else if(nums[i]>=cb[end]){

end = end == len-1? 0 : end+1;

cb[end] = nums[i];

}else{

//if nums[i] falls into first half

if(nums[i]<cb[len/2]){

start = start == 0? len-1:start-1;

int p = start;

//shift the first half to left circularly 

while(cb[p]<nums[i]){

int next = p-1>=0? p-1: len-1;

cb[next] = cb[p];

p++;

}

cb[p] = nums[i];

//if nums[i] falls into second half

}else{

end = end == len-1? 0 : end+1;

int p = end;

//shift the second half to right circularly

while(cb[p]>nums[i]){

int next = p+1<len? p+1: 0;

cb[next] = cb[p];

p--;

}

cb[p] = nums[i];

}

}

}

return cb;

}

Algorithm analysis: 

The best case is when the input is already in increasing or decreasing order, because only append or prepend operations are required.  O(N).

For random order input data is handled much better than Insertion Sort, because the number of moves is less. 

Potential improvements or modifications:
1. using binary search to find the position for nuns[i] in either half of the buffer
2. using bigger buffer like 2*N-1 so we don't need to wrap-around operation in circular buffer.
3. doing the sort in place which is the cycle sort implementation.

Text Justification Algorithm - Dynamic programming and greedy algorithm

Problem: given a list of words and a window size of w, how to split them into multiple lines so that the fewest lines are used if possible.

Example: w = 10, input:  "given a list of words and a window size of w"

potential optimal alignment:

given      a
list         of
words and
a  window
size of    w

not a good alignment:

given
a  list
of words
and a
window
size of
w

This is a common problem faced by many editor application such as MS Words, Open Office.

First of all, given n words, there are 2^n-1 possible ways to alignment them in up to n lines.

Second, we need a way to measure the goodness or badness of each options. One way to measure goodness that is use the total length of words on each line divided by window size. The value is between 0 and 1, 1 means a perfect alignment, 0 means the worst one. Note value will always larger than 0. Another way to measure badness is to compute (w - length_of_words_on_each_line)^3, the higher the value is, the bad alignment is.

Let's assume we have a measurement of how good or bad each option is. A brute force solution is to exam all possible 2^n-1 options and find the best one based on the values mentioned above.  Simple, right? (Then we got fired by boss next day!)

Many of the string related problem can be solved by dynamic programming, e.g. longest substring problem, edit distance between two strings and etc. So let's try DP here.

If there is one word, measurement is easy, its badness is:
 if word.length > w, badness = INFINITY
 otherwise, badness = 0

If there are two words, w1, w2, how to calculate DP(w1) and DP(w2)?
DP(w2) is easy, see one word case above
DP(w1) = Min(badness(w1) + DP(w2), badness(w1, w2))

three words, w1, w2, w3,

DP(w3) is easy, see one word case above
DP(w2) see two words case above
DP(w1) = Min(badness(w1) + DP(w2), badness(w1, w2)+DP(w3), badness(w1, w2, w3))

Ok, I think we find the recursion formula! Let's code it up. Note in the following code, I use fullness or goodness measure. For badness measurement the logic will be the same except we will the maximize each DP value. And I provide sample badness measurement at the end too.

public static void textJustification(String[] words, int width){

int len = words.length;

double[] table = new double[len];

int[] indices = new int[len];

table[len-1] = fullness(words, len-1, len-1, width);

indices[len-1] = -1;

for(int k = len - 2; k<=0; k--){

table[k] = Integer.MIN_VALUE;

for(int i=0; k+i<len; i++){

double fullness = fullness(words, k, k+i, width);

if(fullness==0d)

break;

double dp = k+i+1<len?table[k+i+1]:0;

if(fullness + dp > table[k]){

table[k] = fullness + dp;

indices[k] = k+i+1;

}

}

}

for(int i = 0; i<len; i = indices[i]){

System.out.println(i);

}

}

public static double fullness(String[] words, int i, int j, int w){

int length = words[i].length();

for(int m = i+1; m<=j; m++)

length += words[i].length()+1;

return length<=w? (double)length/w :0;

}

//sample code for badness measurement

public static double badness(String[] words, int i, int j, int w){
 int length = words[i].length();
for(int m = i+1; m<=j; m++)
length += words[i].length()+1;
return length<=w? Math.pow(w - length, 3) : Integer.MAX_VALUE;
}

Given a number A and a set of given digits D, find the smallest number which is larger than A and consists of the digits only from the set D.

Problem statement:

Given digit[] D, and a number A. Find the smallest number which is larger than A, 

* and is consisted by the digit in D.

For example:

D = [0, 1, 8, 3], A = 8821. Result: 8830

D = [0, 1, 8, 3], A = 8310. Result: 8311

D = [0, 1, 8, 3], A = 12345. Result: 13000

Two steps algorithm:

case 1: some of the digits in the number A are not found in D

1. scan from left to right of the digits in the given number, find the digit is not in the set D, try to replace it with bigger digit in the set D, then replace all rest of the digits in the number with the smallest digit in the set D.

1a. if we can't find bigger digit for the digit not found in D, starting from left neighbor of current digit, scan from right to left, try to replace the digit with bigger digit in set D,

if 1a fail, then generate the smallest number which has more digits than A. 

case 2: all of the digits in the number A are found in D

2. If all digits in the number are found in the set, then go from right to left to scan all digits in the number, find the digit in the set which is larger than it, replace current digit with it and replace all rest of the digits on the right with smallest digit in the set D.

2a. if we can't find bigger digits in D for any digits in A, then generate the smallest number which has more digits than A. 

/*

 * Given digit[] D, and a number A. Find the smallest number which is larger than A, 

 * and is consisted by the digit in D.

For example:

D = [0, 1, 8, 3], A = 8821. Result: 8830

D = [0, 1, 8, 3], A = 8310. Result: 8311

D = [0, 1, 8, 3], A = 12345. Result: 13000

*/

public static int[] findSmallestNumberUsingDigits(int[] D, int source){
int len = 0, copy = source;
while(copy>0){
copy = copy/10; len++;
}
int[] digits = new int[len];
copy = source;
while(copy>0){
digits[--len] = copy%10;
copy = copy/10;
}

//java uses quick-sort if size is small then actually insertion sort

Arrays.sort(D);

//step 1

//scan from left to right find the one digit in the number not in D and try to replace it //with larger digit in D

//if succeed set flag to true, then replace the rest of digits on the right with smallest //digits in D

//if failed, then call getNextGreater()

boolean flag = false;

for(int i=0; i<digits.length; i++){
        if(flag){
        digits[i] = D[0];

continue;

}

int target = Arrays.binarySearch(D, digits[i]);
if(target<0){
int insertion = (target+1)*(-1);
if(insertion == D.length){

//throw new IllegalArgumentException("Not possible");

//now we scan to the left to increase the digit

int k = i-1;
for(; k>=0; k--){
target = Arrays.binarySearch(D, digits[k]);
if(target+1<D.length){
digits[k] = D[target+1];
i = k;
break;
}
}
if(k<0){
return getNextGreater(digits, D);
}

}else{
digits[i] = D[insertion];
}
flag = true;
}
}

if(flag)
return digits;

//step 2

//if all digits are in D

//then starting from right, find the larger digit in D than current digit,

//if found, replace current digit with the found digit and replace the rest of the digits on //the right with smallest digit in D

//otherwise call getNextGreater()

int i = digits.length-1;
for(; i>=0; i--){
int target = Arrays.binarySearch(D, digits[i]);
if(target+1<D.length){
digits[i] = D[target+1];
flag = true;
break;
}
}

if(!flag)
return getNextGreater(digits, D);

for(int j = i+1; j<digits.length; j++)
digits[j] = D[0];

return digits;

}

public static int[] getNextGreater(int[] digits, int[] D){
int[] ds = new int[digits.length+1];
ds[0] = D[0]==0?D[1]:D[0];
for(int id=1; id<ds.length; id++)
ds[id] = D[0];
return ds;
}