public class OpenAddressing {

    // A hash function digest a key to a smaller number which is used as the index of the given element
    // located in the hash map. There is a chance/possibility that two keys generates the same index.

    // The situation where a newly inserted key maps to an already occupied slot in the hash table is called
    // collision and must be handled using some collision handling technique. And here we introduce Open
    // Addressing method to address hash collision issue.

    public static void main(String[] args) {
        MyHashMap<Integer, String> ht = new OpenAddressing().new MyHashMap();

        Integer key = 1212;
        String value = "1111";

        ht.put(key, value);
        System.out.println(ht.get(key));
        System.out.println(ht.size());

        ht.remove(key);
        System.out.println(ht.get(key));
        System.out.println(ht.size());

        key = 1313;
        value = "1212";

        ht.put(key, value);
        System.out.println(ht.get(key));
        System.out.println(ht.size());

        key = 1313;
        value = "1414";

        ht.put(key, value);
        System.out.println(ht.get(key));
        System.out.println(ht.size());

        ht.enlarge();
        System.out.println(ht.get(key));
        System.out.println(ht.size());
    }

    class MyHashMap<K extends Comparable<K>, V> {

        private final static int DEFAULT_LINKED_LIST_SIZE = 16;
        private int size = 0;

        // Here we employ separate chaining method which makes each cell of hash table point
        // to a linked list of records that have same hash function value.

        private MyLinkedList<K, V>[] arr;

        public MyHashMap() {

            // Default initial capacity of the HashMap takes is 16

            this(DEFAULT_LINKED_LIST_SIZE);
        }

        public MyHashMap(int maxSize) {
            arr = new MyLinkedList[maxSize];
        }

        public void put(K key, V val) {
            int hashVal = hashCode(key);

            if (arr[hashVal] == null) {
                arr[hashVal] = new MyLinkedList();
            }

            int rst = arr[hashVal].add(new Item(key, val));

            // rst = 1 represents new node is inserted; rst=0 means update the already existing node.
            size += rst;

            // A HashMap with overload elements will degrade into a linear search, so you need
            // to keep them under 75% full.

            if (size * 1.0 / arr.length > 0.75) {
                enlarge();
            }
        }

        public V get(K key) {
            int hashVal = hashCode(key);

            if (arr[hashVal].get(key) == null) {
                return null;
            }

            return arr[hashVal].get(key).obj;
        }

        public V remove(K key) {
            int hashVal = hashCode(key);

            Item<K, V> item = arr[hashVal].delete(key);

            if (item != null) {
                size--;
            }

            return item.obj;
        }

        public int hashCode(K key) {
            return hashCode(key, arr.length);
        }

        private int hashCode(K key, int bound) {
            return key.hashCode() % bound;
        }

        public void enlarge() {

            // We can increase table size by copying old data if needed.

            MyLinkedList<K, V>[] newArr = new MyLinkedList[arr.length * 2];
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == null || arr[i].head == null) {
                    continue;
                }

                int hash = hashCode(arr[i].head.item.key, arr.length * 2);
                newArr[hash] = arr[i];
            }

            arr = newArr;
        }

        public int size() {
            return size;
        }

        public boolean isEmpty() {
            return size == 0;
        }


    }

    class MyLinkedList<K, V> {
        private Node<K, V> head;

        public MyLinkedList() {
            head = null;
        }

        public int add(Item<K, V> item) {

            // In this scheme, data always inserted at the head. But we can also keep probing
            // until reach the end of the list after which we append the new item.

            // Node node = new Node(item);
            // node.next = head;
            // head = node;

            Node<K, V> preHead = new Node(null);
            preHead.next = head;

            while (preHead.next != null) {

                if (!preHead.next.item.key.equals(item.key)) {
                    preHead = preHead.next;

                    continue;
                }

                preHead.next.item.obj = item.obj;

                // returning 0 means key exists, update the binding value
                return 0;
            }

            preHead.next = new Node(item);

            // Don't forget to update the head
            head = preHead.next;

            // returning 0 means key does not exist, add a new node
            return 1;
        }

        public Item<K, V> get(K key) {
            Node<K, V> ptr = head;

            while (ptr != null) {
                if (ptr.item.key.equals(key)) {
                    return ptr.item;
                }

                ptr = ptr.next;
            }

            return null;
        }

        public Item<K, V> delete(K key) {
            Node<K, V> preHead = new Node(null);
            preHead.next = head;

            Node<K, V> ptr1 = preHead;
            Node<K, V> ptr2 = ptr1.next;

            while (ptr2 != null) {
                if (!ptr2.item.key.equals(key)) {
                    ptr1 = ptr2;
                    ptr2 = ptr1.next;

                    continue;
                }

                ptr1.next = ptr2.next;

                // There are good chance the deleted node is the head
                head = preHead.next;

                return ptr2.item;
            }

            return null;
        }
    }

    class Item<K, V> {

        K key;
        V obj;

        public Item(K key, V obj) {
            this.key = key;
            this.obj = obj;
        }
    }

    class Node<K, V> {

        Item<K, V> item;
        Node<K, V> next;

        public Node(Item item) {
            this.item = item;
        }
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-05 11:01:08

results matching ""

    No results matching ""