import org.w3c.dom.Node;

public class HTMap<K, V> {

	public static void main(String[] args) {
		HTMap<String, Integer> htmap = new HTMap<>();

		htmap.put("radiohead", 10);

		htmap.put("kanye", 9);

		htmap.put("t swizzle", 3);

		htmap.put("black sabbath", 8);

		System.out.println(htmap.containsKey("black sabbath"));

		System.out.println(htmap.containsValue(10));

		System.out.println(htmap.toString());

	}

	private class Entry<K, V> {
		K key;
		V value;

		@Override
		public int hashCode() {
			return key.hashCode();
		}
	}

	private Entry<K, V>[] table;
	private int size;

	public HTMap() {
		table = (Entry<K, V>[]) new Entry[10];
	}

	public V put(K key, V value) {
		int i = Math.abs(key.hashCode()) % table.length;
		while (table[i] != null && !table[i].key.equals(key))
			i = (i + 1) % table.length;
		if (table[i] == null) {
			Entry<K, V> entry = new Entry<>();
			entry.key = key;
			entry.value = value;
			table[i] = entry;
			size++;
			if (((double) size) / table.length > 0.75)
				rehash();
			return null;
		} else {
			V old = table[i].value;
			table[i].value = value;
			return old;
		}
	}

	public V get(K key) {
		int i = Math.abs(key.hashCode()) % table.length;
		while (table[i] != null && !table[i].key.equals(key))
			i = (i + 1) % table.length;
		if (table[i] == null)
			return null;
		else
			return table[i].value;
	}

	public int size() {
		return size;
	}

	private void rehash() {
		Entry<K, V>[] small = table;
		table = (Entry<K, V>[]) new Entry[size + size];
		size = 0;
		for (int i = 0; i < small.length; i++)
			if (small[i] != null)
				put(small[i].key, small[i].value);
		System.out.println("Rehash! (" + size + ")");
	}

	// Returns true if the map contains the given key.
	public boolean containsKey(K key) {
		return get(key) != null ? true : false;
	}

	// Returns true if the map contains the given value.
	public boolean containsValue(V value) {
		for (int i = 0; i < table.length; i++) {
			if (table[i] != null && table[i].value == value)
				return true;
		}
		return false;
	}

	// Returns the map formatted as a string (details below).
	@Override
	public String toString() {
		if (size() == 0)
			return "[]";

		int found = 0;

		String s = "[";
		for (int i = 0; i < table.length; i++) {

			if (table[i] == null)
				continue;

			found++;

			if (found < size()) {
				s += "{" + table[i].key + "|" + table[i].value + "}, ";
			} else {
				s += "{" + table[i].key + "|" + table[i].value + "}]";
			}
		}

		return s;

	}
}