package com.collection;

 public interface Map<K, V> {

     public V put(K k, V v);

     public V get(K k);

     public int size();

     interface Entry<K, V> {

         public K getKey();

         public V getValue();

     }

 }

 package com.collection;

 public class HashMap<K, V> implements Map<K, V> {

     private Entry<K, V>[] table = null;

     private int size = 0;

     private static int defaultLength = 16;

     public HashMap() {

         table = new Entry[defaultLength];

     }

     @Override

     public V put(K k, V v) {

         int index = hash(k);

         Entry<K, V> entry = table[index];

         if (entry == null) {

             table[index] = new Entry<K, V>(k, v, null, index);

             size++;

         } else {

             table[index] = new Entry<K, V>(k, v, entry, index);

         }

         return table[index].getValue();

     }

     private int hash(K k) {

         int index = k.hashCode() & (defaultLength - 1);

         return Math.abs(index);

     }

     @Override

     public V get(K k) {

         if (size == 0) {

             return null;

         }

         int index = hash(k);

         Entry<K, V> entry = getEntry(k, index);

         return entry == null ? null : entry.getValue();

     }

     private Entry<K, V> getEntry(K k, int index) {

         for (Entry<K, V> entry = table[index]; entry != null; entry = entry.next) {

             if (entry.hash == index && (k == entry.getKey() || k.equals(entry.getKey()))) {

                 return entry;

             }

         }

         return null;

     }

     @Override

     public int size() {

         return 0;

     }

     class Entry<K, V> implements Map.Entry<K, V> {

         K k;

         V v;

         Entry<K, V> next;

         int hash;

         public Entry(K k, V v, Entry<K, V> next, int hash) {

             this.k = k;

             this.v = v;

             this.next = next;

             this.hash = hash;

         }

         @Override

         public K getKey() {

             return k;

         }

         @Override

         public V getValue() {

             return v;

         }

     }

 }

 package com.collection;

 public class TestHashMap {

     public static void main(String[] args) {

         com.collection.HashMap map = new com.collection.HashMap<>();

         for (int i = 0; i < 6666; i++) {

             map.put("Monkey" + i, "計算方法的事實");

             System.out.println(map.get("Monkey"));

         }

         System.out.println(map);

     }

 }