1. Define the class for each entry:

2. maintain an array of entries

3. hash(key) to get the hash#

4. form the hash#, mapped to the entry index.

5. When iterate the corresponding entry for the given key, which is actually a singly linked list, we need compare each of the entry in the list, if the key is the same as the key we want

public static class MyHashMap<String, Integer> {
	public static class Entry<String, Integer> {
		private final String key;
		private int value;
	 
		private Entry <String, Integer> next;
		public Entry(String key, int value) {
			this.key = key;
			this.value = value;
		}
	}

	private static final int DEFAULT_CAPACITY = 16;
	private static final float DEFAULT_LOAD_FACTOR = 0.75f;
	
	private Entry<String, Integer> [] buckets;
	private int capacity;
	private float loadFactor;
	private int size;

// 用户提供capacity和loadFactor版本
	public MyHahsMap(int capacity, float loadFactor) {
		this.capacity = capacity;
		this.loadFactor = loadFactor;
		this.size = 0;
		this.buckets = new Entry[capacity];
	}

// 用户不提供capacity和loadFactor版本
	public MyHahsMap() {
		this.capacity = DEFAULT_CAPACITY;
		this.loadFactor = DEFAULT_LOAD_FACTOR;
		this.size = 0;
		this.buckets = new Entry[capacity];
	}

//可以告诉我们当前的HashMap里有多少对 Key-Value pair
	public int size() {
		return this.size;
	}

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

	private boolean equalsValue(int val1, int val2) {
		return val1 == val2;
	}

	private boolean equalsKey (String key1, String key2) {
		return key1.equals(key2);
	}

// 给我一个key，给一个不为负数且不超界的hashCode
	private int hash(String key) {
		if (key == null) {
			return 0;
		}
		return key.hashCode() & 0X7FFFFFFF;
	}

//找到key对应的bucket
	private int getIndex(String key) {
		int hashCode = hash(key);
		return hashCode % this.capacity;

//如果当前hashMap里entry/capacity的ratio大于loadFactor，我们就应该rehashing
	private boolean needRehashing() {
		float ratio = (size + 0.0f) / capacity;
		return ratio >= this.loadFactor;

// Arrays.fill 把这个array 填成我们要的值,比如这里将整个hashMap清空，所以Array里全部都是null
	private void clear() {
		Arrays.fill(this.buckets, null)
		size = 0;
	}

// 给我一个key，我去找有没有对应值，如果有返回，如果没有就返回null
// 逻辑： 先找到这个key在那个bucket，再对这个bucket里的linkedlist进行遍历，看有没有对应key
	public Integer get(String key) {
		int index = getIndex(key);
		Entry<String, Integer> head = buckets[index];
		Entry<String, Integer> cur = head;
		while (cur != null) {
			if (cur.key.euqals(key)) {
				return cur.value;
			}
			cur = cur.next;
		}
		return null;
	}

// 给我一个key，如果hashMap里有就return true，没有就return false
	public boolean containsKey(String key) {
		int index = getIndex(key);
		Entry<String, Integer> head = buckets[index];
		Entry<String, Integer> cur = head;
		while (cur != null) {
			if (cur.key.equals(key)) {
				return true;
			}
			cur = cur.next;
		}
		return false;
	}

// 逻辑：往map里放入entry <key, value> 
// case 1: already exists, update it, return the previous value
// case 2: just insert this entry to the head of linkedList, return null;
// 有可能触发rehashing
	public Integer put(String key, Integer value) {
		int index = getIndex(key);
		Entry<String, Integer> head = buckets[index];
		Entry<String, Integer> cur = head;
		while (cur != null) {
			if (cur.key.equals(key)) {
				int result = cur.value;
				cur.value = value;
				return result;
			}
			cur = cur.next;
		}
	// 代码进行到这里说明map里没有对应的entry，我们得把新entry插在head；
		Entry<String, Integer> newEntry = new Entry<>(key, value);
		newEntry.next = head;
		buckets[index] = newEntry;
		this.size++;

	// check if needRehashing
		if (needRehashing()) {
			rehashing();
		}
		return null;
	}

// rehasing的逻辑不是抄以前bucket里面的linkedList，
// 而是把以前map里面的每个entry重新计算bucket重新放一遍。
	private void rehashing() {
		this.capacity = 2;
/*
或者自己定义SCALE_FACTOR
private static final int SCALE_FACTOR = 4;
this.capacity *= SCALE_FACTOR;
*/

		Entry<String, Intege>[] newBuckets = new Entry[this.capacity];
//拿出旧buckets里面的所有linkedList的head
		for (Entry<String, Integer> eachHead : buckets) {
//遍历每个linkedList的所有Entry
			Entry<String, Integer> eachCur = eachHead;
			while (eachCur != null) {
				Entry<String, Integer> next = eachCur.next;
				eachCur.next = null;
// 把eachCur放到新的map里
// 逻辑：算一下index，如果bucket对应index为空，则让它成为头；
// 如果不为空，就把它接在头上，和put（）类似
				int index = getIndex(eachCur.key);
				if (newBuckets[index] == null) {
					newBuckets[index] = eachCur;
				} else {
					eachCur.next = newBuckets[index];
					newBuckets[index] = eachCur;
				}
				eachCur = next;
			}
		}
		this.bucktes = newBuckets;
	}
	
// 逻辑：给我一个key，找到这个map里是否有对应的entry，如果有，就remove，并且返回对应value
// 如果没有，返回null
	private Integer remove(String key) {
		int index = getIndex(key);
		Entry<String, Integer> head = bucktes[index];
		Entry<String, Integer> cur = head;
		Entry<String, Integer> prev = null;
		while (cur != null) {
			if (cur.key.equals(key)) {
				if (prev == null) {
					buckets[index] = cur.next;
				} else {
					prev.next = cur.next;
				}
				this.size--;
				return cur.value;
			}
			prev = cur;
			cur = cur.next;
		}
		return null;
	}