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

Find single-sourced shortest path - bellman-ford algorithm

Continue the journey from the last blog (http://blueocean-penn.blogspot.com/2015/02/dijkstra-algorithm-implementation.html) about find single-sourced shortest path in a graph, last time I implemented Dijkstra algorithm which can deal with graph with cycle with the constrain of all weights have to be non-negative.

The negative cycle issue is the nemesis for any shortest path graph algorithm, in this post I implemented Bellman-Ford algorithm which can find single-sourced shortest path and report negative cycle if there is one.

The algorithm itself is incredibly simple:

for each vertex in the graph except the source vertex
loop through each edge in the graph
do relaxation on (u, v, w), u, v are the vertex, w is the weight of the edge (u, v)

the following implementation assumes graph represented as adjacent matrix w[][]

/*

* O(VE) algorithm can report negative cycle

*/

int[] bellmanford(int source){

int[] distance = new int[this.size];

int[] parent = new int[this.size];

//initialize

for(int i=0;i<this.size; i++){

distance[i] = Integer.MAX_VALUE;

parent[i] = -1;

}

distance[source] = 0;

parent[source] = -1;

for(int i = 1; i< this.size; i++){

for(int u = 0; u<this.size; u++){

for(int v=0; v<this.size; v++){

if(w[u][v]!=0){//there is edge from u->v

//relaxation

if(distance[v] > distance[u] + w[u][v]){

distance[v] = distance[u] + w[u][v];

parent[v] = u;

}

}

}

}

}

for(int u = 0; u<this.size; u++){

for(int v=0; v<this.size; v++){

if(w[u][v]!=0){//there is edge from u->v

if(distance[v] > distance[u] + w[u][v]){

throw new IllegalStateException("Graph has negative cycle!");

}

}

}

}

return distance;

}

Find repeating sub-sequences in a string

This is a problem given by Peng Li (http://allenlipeng47.com/PersonalPage/index/list/1/nkey)
Given a string , find if there is any sub-sequence that repeats itself. Here, sub-sequence can be a non-contiguous pattern, with the same relative order. 

1. abab <------yes, ab is repeated
2. abba <---- No, a and b follow different order
3. acbdaghfb <-------- yes there is a followed by b at two places
4. abcdacb <----- yes a followed by b twice
5. aacc< ----yes, aacc, the underline ‘ac’ and red ‘ac’ are the repeating sub-sequences.

We can reduce this problem to the problem of finding common sub-sequence amount two strings, in this case, the two strings are identical. Also note the diagonal values of the DP table will be the string itself or identical sub-sequences which we should not consider.

For example:

negative example: abba

before and after we set diagonal values to 0

len(sub-seq)	a	b	b	a
a	1	1	1	2
b	1	2	2	2
b	1	2	3	3
a	1	2	3	4

len(sub-seq)	a	b	b	a
a	0	0	0	1
b	0	0	1	1
b	0	1	0	1
a	1	1	1	0

positive example: abab

len(sub-seq)	a	b	a	b
a	0	0	1	1
b	0	0	1	2
a	1	1	0	2
b	1	2	2	0

public static boolean findLongestSubsequence(String s1, String s2){

 int len1 = s1.length(), len2 = s2.length();

//part1 build DP table bottom-up

 int[][] table = new int[len1+1][len2+1];

     

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

     for(int j=1; j<len2+1; j++){

          if(i!=j){ <=== can not consider the subsequence sharing the same characters

          if(s1.charAt(i-1) == s2.charAt(j-1))

            table[i][j] = table[i-1][j-1]+1;

          else

            table[i][j] = Math.max(table[i-1][j], table[i][j-1]);        

          }

     }

 } 

  for(int i = 0; i<len2+1; i++){

     if(table[len1][i]>1)

        return true;

  }  

return false;

}