public class Entry
{
	private int key;
	private int value;
	private Entry next;

	public Entry(int k, int v)
	{
		key = k;
		value = v;
	}

	public int getKey()
	{
		return key;
	}

	public int getValue()
	{
		return value;
	}

	public Entry getNext()
	{
		return next;
	}

	public void setNext(Entry n)
	{
		next  = n;
	}

	public String toString()
	{
		return "["+key+", "+value+"]";
	}
}
			

public class Hashtable
{
	private Entry [] bucket;
	private int bucketSize;
	private int count;

	public Hashtable()
	{
		bucketSize = 10;
		bucket = new Entry[bucketSize];
		count++;
	}

	// O(1)
	public void put(int k, int v)
	{
		Entry e = new Entry(k, v);
		if(bucket[hashCode(k)] == null)
			bucket[hashCode(k)] = e;
		else
		{
			e.setNext(bucket[hashCode(k)]);
			bucket[hashCode(k)] = e;
		}
	}

	// O(1)
	public int hashCode(int k)
	{
		return k%bucketSize;
	}

	// O(n)
	public int get(int k)
	{
		Entry walker = bucket[hashCode(k)];
		if(walker == null)
			return -1;
		while(walker != null)
		{
			if(k == walker.getKey())
				return walker.getValue();
		}
		return -1;
	}

	// O(n)
	public String toString()
	{
		String s = "";
		for(int i = 0; i < bucketSize; i++)
		{
			s = s+"Bucket "+i+": ";
			Entry walker;
			walker = bucket[i];
			while(walker != null)
			{
				s=s+walker.toString()+" ";
				walker = walker.getNext();
			}
			s = s+"\n";
		}

		return s;
	}
}
			

public class HashtableTest
{
	public static void main(String args[])
	{
		Hashtable t = new Hashtable();

		t.put(11, 1);
		t.put(21, 2);
		t.put(7, 3);
		t.put(34, 4);

		System.out.println(t);

		System.out.println(t.get(21));
	}
}