Adam's Sick Map Tips

/*
BUCKETS
Entries in maps are stored in 'buckets'. To demonstrate with a simple example, you can imagine the following integer array and an imaginary map class:
*/

int[] nums = new int[]{1, 4, 8, 10};
AdamsMap<Integer,Integer> map = new AdamsMap<>();

/*
Now, imagine that we wish to store the 'nums' values into 'map'. We can 'hash' each value, to see which index in the map's underlying structure we should store the value at. For example, a simple hash that would work fine for this limited data set is something like this:
*/

public int hash(int num) {
        return num;
}

// Assume that inside of our map, we have a structure that looks like this:

public class SpecialMap<K, V> {
        Node[] nodes = new Node[11];

        public void put(K key, V value) {
                int hash = hash(key);
                Node node = new Node(key,val);
                nodes[hash] = node;
        }
}

public class Node<K,V> {
        private K key;
        private V val;
        private Node<K,V> next;

        public Node(K key, V val) { this.key = key; this.val = val; }
}

/*
Now, when we hash each value, the return result will tell us where in the underlying array that we wish to store the value at. So when we hash the first value, 1, we get the index 1. So now we know that we wish to store 1 at the index of 1 inside of our map. You can repeat this process for each value in the example array, and this will lead to a map that has an entry for each of these values. You can imagine that we are preserving some sort of value within the map by using the Node objects, so now we have a very simple key->value mapping that works for any set of integers between 0-10.
*/

/*
COLLISIONS - Let's make it a little harder now. Imagine an array that instead contains Strings!
*/

String[] strings = new String[]{"Adam", "Is", "Always", "Cool"}

/*
How do we hash this? Well, good question. Don't worry too much about that. hashCode(). But for the sake of example, let's do a much simpler hash. We will have to change our map structure a bit to compensate for this change. Consider this:
*/

public int hash(String key) {
        return String.valueOf(key.charAt(0)).toLowerCase();
}

public class SpecialMap<K, V> {
        Node[] nodes = new Node[123];

        public void put(K key, V value) {
                int hash = hash(key);
                Node node = new Node(key,val);
                nodes[hash] = node;
        }
}

/*
This is really similar, with the only changes being made to how the hash function works, and the initial size of the map's underlying array. As for the hash function,  now it just looks at the first letter in the string and returns the value of that specific character. Cool, so now we have a similar function like above with the integer array and we can once again just get the index we wish to store each value at. What happens when we attempt to store the 3rd string, "Always"?

We have now caused a hash collision! I know! Isn't it fun? Let's imagine what the map looks like after the first two values have been inserted:

a = 97
i = 105

So we know that the array is full of nulls except at these two indices. Map[97] contains a node with the information from the first element of the array, and Map[105] contains a node with information from the second element. But now we wish to store a value at Map[97] again! So what we do now, is the node at Map[97], the one where we have stored "Adam", we now make that Node into a LinkedList. Because traversing the elements of a LinkedList is very fast ( O(n) ), this allows us to access elements of the Map quickly even when there are many, many entries.

So let's rewrite the put() method to work with this new LinkedList idea.
*/

public class SpecialMap<K, V> {
        Node[] nodes = new Node[123];

        public void put(K key, V value) {
                int index = hashCode.charAt(0) - 'a';
                Node newNode = new Node(key, value);
                Node head = nodes[index];
                if (head == null) {
                        nodes[index] = newNode;
                } else {
                        while (head.hasNext()) {
                                head = head.getNext();
                        }
                        head.setNext(newNode);
        }
}