public class Rehash {

	private static class Node {
		int data;
		Node next;

		private Node(int item) {
			data = item;
			next = null;
		}
	}

	public static void main (String[] args) {

		int x, hash;
		int pnum;
		Node[] hashtable1 = new Node[389];
		Node[] hashtable2 = new Node[769];

		System.out.println("Using 389 Buckets");
		System.out.println("Building Table\n");
		for (x = 0; x < 1000; x++) {
			pnum = (int)(Math.random() * 8000000 + 2000000);
			hash = pnum % 389;
			Node n = new Node(pnum);
			n.next = hashtable1[hash];
			hashtable1[hash] = n;
		}
		hist(hashtable1);

		System.out.println("\nRehashing into 769 buckets");
		System.out.println("Building Table\n");
		for (Node p : hashtable1) {
			while (p != null) {
				hash = p.data % 769;
				Node n = new Node(p.data);
				n.next = hashtable2[hash];
				hashtable2[hash] = n;
				p = p.next;
			}
		}
		hashtable1 = null; // send first table to collector
		hist(hashtable2);
	}

	public static void hist(Node[] ht) {
		int x, hash, largest=0, smallest=Integer.MAX_VALUE;
		int numempty=0;

		// calculate bucket depth
		for (x = 0; x < ht.length; x++) {
			Node p = ht[x];
			int l=0;
			if ( p == null )
				numempty++;
			while (p != null) {
				l++;
				p = p.next;
			}
			System.out.printf("%d numbers in bucket %d.\n",
					l, x);
			if ( l > largest )
				largest = l;
			if ( l < smallest )
				smallest = l;
		}

		System.out.printf("%d Buckets\n", ht.length);
		System.out.printf("Deep bucket is %d entries\n", largest);
		System.out.printf("Shallow bucket is %d entries\n", smallest);
		System.out.printf("Empty buckets: %d\n", numempty);
	}
}