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

Separate Chaining - Coursera Algorithms

To deal with collisions in hashing, separate chaining implementation can be used, where M linked lists(<number of elements N) are used such that :

1. Hash - map key to i between 0 and M-1.
2. Insert - at the front of ith chain.

3. Search - in ith chain.

Easier to implement and clustering less sensitive to poorly designed hash function.

Following is the implementation:

	package hashTables;
	public class SeparateChaining<Key,Value> {
	private int M=97;
	private Node[] st = new Node[M];
	private static class Node{
	private Object key;
	private Object val;
	private Node next;
	Node(Object key,Object val,Node next) {
	this.key = key;
	this.val=val;
	this.next=next;
	}
	}
	private int hash(Key key) {
	return (key.hashCode() & 0x7fffffff)%M;
	}
	public Value get(Key key) {
	int i = hash(key);
	for(Node x=st[i];x!=null;x=x.next)
	if(key.equals(x.key))
	return (Value) x.val;
	return null;
	}
	public void put(Key key, Value val) {
	int i = hash(key);
	for(Node x=st[i];x!=null;x=x.next) {
	if(key.equals(x.key)) {
	x.val=val;
	return;
	}
	}
	st[i] = new Node(key,val,st[i]);
	}
	public void print() {
	SeparateChaining sc = new SeparateChaining();
	for(int i=0;i<M;i++) {
	Node n = st[i];
	if(n!=null) {
	System.out.print(i+"----"+sc.hash(i)+":"+n.val);
	while(n.next!=null) {
	n = n.next;
	System.out.print(", "+n.val);
	}
	System.out.println();
	}
	}
	}
	public static void main(String[] args) {
	SeparateChaining sc = new SeparateChaining();
	for(int i=0;i<100;i++) {
	sc.put("key"+i,"val"+i);
	}
	sc.print();
	System.out.println("fetch key99 "+sc.get("key99"));
	}
	}

view raw SeparateChaining.java hosted with ❤ by GitHub

Hash Functions - Coursera Algorithms

We can do better than the sequential/binary search or search through BST/red-black BST, by storing the data in key-indexed table. Hash functions compute the array index from key. We need to handle the hash implementation, equality test and collision resolution when two keys hash to the same index.

There are several hashing implementations, some of them being :
1. 31*initial_hash_value+ current element value or current object hashcode.
2. Modular - Math.abs(key.hashCode() & 0x7fffffff)%M returning a hash between 0 and M-1

Following code experiments with what happens when we override equals/hashcode:

	package hashTables;
	import java.util.HashMap;
	import java.util.Map;
	public class ExperimentEqHC {
	static int M=97;
	public static class Person0<Key,Value>{
	int id;
	public Person0(int id) {
	this.id = id;
	}
	public int hashCode() {
	return this.id;//(key.hashCode() & 0x7fffffff)%M;
	}
	}
	public static class Person1<Key,Value>{
	int id;
	public Person1(int id) {
	this.id = id;
	}
	public boolean equals(Object p) {
	if(((Person1)p).id==this.id)
	return true;
	else
	return false;
	}
	}
	public static class Person2<Key,Value>{
	int id;
	public Person2(int id) {
	this.id = id;
	}
	@Override
	public int hashCode() {
	//return (key.hashCode() & 0x7fffffff)%M;
	return this.id;
	}
	public boolean equals(Person2 p) {
	if(p.id==this.id)
	return true;
	else
	return false;
	}
	}
	public static class Person3<Key,Value>{
	int id;
	public Person3(int id) {
	this.id = id;
	}
	public int hashCode() {
	return this.id;//(key.hashCode() & 0x7fffffff)%M;
	}
	public boolean equals(Object p) {
	if(((Person3)p).id==this.id)
	return true;
	else
	return false;
	}
	}
	public static void main(String[] args) {
	Person0 p01 = new Person0(1);
	Person0 p02 = new Person0(1);
	System.out.println("p0 hashcodes "+p01.hashCode()+"---"+p02.hashCode());//1
	Map<Person0,Integer> m1 = new HashMap<>();
	m1.put(p01, 10);
	m1.put(p02, 20);
	for(Person0 p : m1.keySet()) {
	System.out.println(m1.get(p).toString()+"---"+m1.get(p).hashCode());
	}
	if(p01.equals(p02))
	System.out.println("hash overriden and equal");//not equal - doesn't print
	Person1 p11 = new Person1(1);
	Person1 p12 = new Person1(1);
	System.out.println("p1 hashcodes "+p11.hashCode()+"---"+p12.hashCode());//random values
	Map<Person1,Integer> m2 = new HashMap<>();
	m2.put(p11, 10);
	m2.put(p12, 20);
	for(Person1 p : m2.keySet()) {
	System.out.println(m2.get(p).toString()+"---"+m2.get(p).hashCode());
	}
	if(p11.equals(p12))
	System.out.println("equals overriden and equal");//equal
	Person2 p21 = new Person2(1);
	Person2 p22 = new Person2(1);
	System.out.println("p2 hashcodes "+p21.hashCode()+"---"+p22.hashCode());//1
	Map<Person2,Integer> m3 = new HashMap<>();
	m3.put(p21, 10);
	m3.put(p22, 20);
	for(Person2 p : m3.keySet()) {
	System.out.println(m3.get(p).toString()+"---"+m3.get(p).hashCode());
	}
	if(p21.equals(p22))
	System.out.println("hash+equals person overriden and equal");//equal
	Person3 p31 = new Person3(1);
	Person3 p32 = new Person3(1);
	System.out.println("p3 hashcodes "+p31.hashCode()+"---"+p32.hashCode());//1
	Map<Person3,Integer> m4 = new HashMap<>();
	m4.put(p31, 10);
	m4.put(p32, 20);
	for(Person3 p : m4.keySet()) {
	System.out.println(m4.get(p).toString()+"---"+m4.get(p).hashCode());//only one element - as hash matches, first one gets replaced
	}
	if(p31.equals(p32))
	System.out.println("hash+equals obj overriden and equal");//equal
	}
	}

view raw ExperimentEqHC.java hosted with ❤ by GitHub

Heap Sort - Coursera Algorithms

Heap Sort is an in place sort that builds a max binary heap and then repeatedly deletes the maximum element. It's not stable and it's inner loop takes longer than Quick Sort. It has poor cache usage. To build a heap, it takes O(N) and for sort, it takes O(NlogN).

Following is the program:

	package sorting.heapSort;
	public class HeapSort<Key extends Comparable<Key>> {
	public void sort(Comparable[] a) {
	int indx = a.length-1;
	for(int k=indx/2;k>=1;k--) {
	sink(a,k,indx);
	}
	print(a); //max heap
	while(indx>1) {
	exchange(a,1,indx);
	sink(a,1,--indx);
	}
	}
	public boolean less(Comparable[] a,int aa, int bb) {
	return a[aa].compareTo(a[bb])<0;
	}
	public void exchange(Comparable[] a,int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	public void print(Comparable[] a) {
	System.out.println();
	int indx = a.length-1;
	for(int i=1;i<=indx;i++) {
	System.out.print(a[i]+"--");
	}
	}
	private void sink(Comparable[] a,int k, int indx) {
	while(2*k <= indx) {
	int j = 2*k;
	if(j<indx && less(a,j,j+1)) j++;
	if(!less(a,k,j)) break;
	exchange(a,k, j);
	k=j;
	}
	}
	public static void main(String[] args) {
	HeapSort<String> pq = new HeapSort<String>();
	Integer[] a = {-1,5,2,4,6,1,3};
	// String[] a = {"*","S","O","R","T","E","X","A","M","P","L","E"};
	pq.print(a);
	pq.sort(a);
	pq.print(a);
	}
	}

view raw HeapSort.java hosted with ❤ by GitHub

Related Posts:

Binary Heap

Binary Heap - Coursera Algorithms

A binary tree is either empty or points to a root node with links to left and right binary trees. A tree is complete if it is balanced perfectly, excluding the bottom level. A binary heap is an array representation of a heap ordered complete binary tree.

Max node is root at a[1]. For a node k, it's parent is at k/2 and it's children are at 2k and 2k+1.
Swim: When a child node is greater than parent, keep exchanging them till they are ordered.
Sink: When a parent node is lesser than child, keep exchanging them till they are ordered.
In insert operation, add the child at end and swim it. --> O(logN)
In delete operation, exchange root with node at end and sink the top node. -->O(logN)

Following is the program:

	package priorityQueue;
	public class BinaryHeap<Key extends Comparable<Key>> {
	private Key[] pq;
	private int indx;
	public BinaryHeap(int cap) {
	pq = (Key[]) new Comparable[cap+1];
	}
	public boolean less(int a, int b) {
	return pq[a].compareTo(pq[b])<0;
	}
	public void exchange(int i, int j) {
	Key tmp = pq[i];
	pq[i] = pq[j];
	pq[j] = tmp;
	}
	public boolean isEmpty() {
	return (indx==0);
	}
	public void resize(int cap) {
	Key[] copy = (Key[])new Comparable[cap];
	for(int i=1;i<indx;i++) {
	copy[i]=pq[i];
	}
	pq = copy;
	}
	public void insert(Key k) {
	int l = pq.length;
	if(++indx==l) {
	resize(2*l);
	}
	pq[indx]=k;
	swim(indx);
	}
	public Key delMax() {
	Key max=pq[1];
	exchange(1, indx--);
	sink(1);
	pq[indx+1] = null;
	return max;
	}
	public void print() {
	System.out.println();
	for(int i=1;i<indx+1;i++) {
	System.out.print(pq[i]+"--");
	}
	}
	private void swim(int k) {
	while(k>1 && less(k/2,k)) {
	exchange(k,k/2);
	k=k/2;
	}
	}
	private void sink(int k) {
	while(2*k <= indx) {
	int j = 2*k;
	if(j<indx && less(j,j+1)) j++;
	if(!less(k,j)) break;
	exchange(k, j);
	k=j;
	}
	}
	public static void main(String[] args) {
	BinaryHeap<Integer> pqi = new BinaryHeap<Integer>(5);
	pqi.insert(5);
	pqi.insert(2);
	pqi.insert(4);
	pqi.insert(6);
	pqi.insert(1);
	pqi.insert(3);
	pqi.insert(7);
	pqi.print();
	System.out.println("delMax "+pqi.delMax());
	pqi.print();
	BinaryHeap<String> pq = new BinaryHeap<String>(5);
	pq.insert("P");
	pq.insert("Q");
	pq.insert("E");
	pq.print();
	System.out.println("delMax "+pq.delMax());
	pq.print();
	pq.insert("X");
	pq.insert("A");
	pq.insert("M");
	pq.print();
	System.out.println("delMax "+pq.delMax());
	pq.print();
	}
	}

view raw BinaryHeap.java hosted with ❤ by GitHub

Maximum Priority Queue - Coursera Algorithms

Max priority queues pick the maximum element for deletion instead of picking the first in element as done in Queues. It takes O(N) for extracting the max. Following is the program:

	package priorityQueue;
	public class UnorderedMaxPQ<Key extends Comparable<Key>>{
	private Key[] pq;
	private int indx;
	public UnorderedMaxPQ(int cap) {
	pq = (Key[]) new Comparable[cap];
	}
	public boolean less(int a, int b) {
	return pq[a].compareTo(pq[b])<0;
	}
	public void exchange(int i, int j) {
	Key tmp = pq[i];
	pq[i] = pq[j];
	pq[j] = tmp;
	}
	public boolean isEmpty() {
	return (indx==0);
	}
	public void insert(Key k) {
	pq[indx++]=k;
	}
	public Key delMax() {
	int max=0;
	for(int i=1;i<indx;i++)
	if(less(max,i)) max=i;
	exchange(max, indx-1);
	return pq[--indx];
	}
	public void print() {
	System.out.println();
	for(int i=0;i<indx;i++) {
	System.out.print(pq[i]+"--");
	}
	}
	public static void main(String[] args) {
	UnorderedMaxPQ<String> pq = new UnorderedMaxPQ<String>(5);
	pq.insert("P");
	pq.insert("Q");
	pq.insert("E");
	pq.print();
	System.out.println("delMax "+pq.delMax());
	pq.print();
	pq.insert("X");
	pq.insert("A");
	pq.insert("M");
	pq.print();
	System.out.println("delMax "+pq.delMax());
	pq.print();
	}
	}

view raw UnorderedMaxPQ.java hosted with ❤ by GitHub

Three Way Quick Sort - Coursera Algorithms

Three Way Quick Sort uses multiple partition elements, such that the there are no larger entries to their left and no smaller entries to their right. It is in place, but not a stable sort. This is used to deal with duplicate elements.

Time complexity: O(NlgN)


Following is the program, partition elements are from lt to gt:

	package sorting.quickSort;
	import sorting.insertionSort.InsertionSort;
	public class ThreeWayQuickSort {
	public static boolean less(Comparable a, Comparable b) {
	return a.compareTo(b)<0;
	}
	public static void exchange(Comparable[] a, int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	public static void shuffle(Comparable[] a) {
	int n = a.length;
	for(int i=0;i<n;i++) {
	int r = (int)Math.random()*(i+1);
	exchange(a, i, r);
	}
	}
	public static void sort(Comparable[] a, int lo, int hi) {
	int cutoff=7;
	if(hi<=lo+ cutoff -1) {
	InsertionSort is = new InsertionSort();
	is.sort(a);
	}
	if(hi<=lo) return;
	int lt=lo,gt=hi;
	Comparable v=a[lo];
	int i=lo;
	while(i<=gt) {
	int cmp = a[i].compareTo(v);
	if(cmp<0) exchange(a,lt++,i++);
	else if(cmp>0) exchange(a,i,gt--);
	else i++;
	}
	sort(a,lo,lt-1);
	sort(a,gt+1,hi);
	}
	public static void sort(Comparable[] a) {
	shuffle(a);
	sort(a,0,a.length-1);
	}
	public static void print(Comparable[] a) {
	int n = a.length;
	System.out.println();
	for(int i=0;i<n;i++) {
	System.out.print(a[i]+"--");
	}
	}
	public static void main(String[] args) {
	Comparable[] a = {5,2,3,1,1,3,2,4,5,6,7,2,2,8,4,3,2,9,6};
	//Comparable[] a = {5,2,4,6,1,3,5,2,4,6,1,3};
	print(a);
	sort(a);
	print(a);
	}
	}

view raw ThreeWayQuickSort.java hosted with ❤ by GitHub

Related Posts: 

Quick Sort

Insertion Sort