Linear Probing - Coursera Algorithms

Linear probing is used to resolve collisions in hashing. It takes less space and has better cache performance.

An array of size M > number of elements N is used such that:

1. Hash - map key to i between 0 and M-1.
2. Insert - at table index i, if not free - try i+1, i+2 etc

3. Search - search table index i, if occupied and no match - try i+1, i+2 etc

Following is the implementation :

	package hashTables;
	public class LinearProbing<Key,Value> {
	private int M=30001;
	private Value[] vals = (Value[]) new Object[M];
	private Key[] keys = (Key[]) new Object[M];
	private int hash(Key key) {
	return (key.hashCode() & 0x7fffffff)%M;
	}
	public void put(Key key, Value val) {
	int i;
	for(i=hash(key);keys[i]!=null;i=(i+1)%M)
	if(keys[i].equals(key))
	break;
	keys[i] = key;
	vals[i] = val;
	}
	public Value get(Key key) {
	for(int i=hash(key);keys[i]!=null;i=(i+1)%M)
	if(keys[i].equals(key))
	return vals[i];
	return null;
	}
	public void print() {
	int l = keys.length;
	for(int j=0;j<l;j++) {
	if(keys[j]!=null)
	System.out.println(j+"----"+keys[j]+"---"+vals[j]);
	}
	}
	public static void main(String[] args) {
	LinearProbing lp = new LinearProbing();
	for(int i=0;i<100;i++) {
	lp.put("key"+i,"val"+i);
	}
	lp.print();
	System.out.println("fetch key9 "+lp.get("key9"));
	}
	}

view raw LinearProbing.java hosted with ❤ by GitHub