从手写HashMap说起，解析HashMap原理（未完待续）

最近面试时，经常被问到hashmap相关的问题。作为一名java程序员，有必要了解hashmap的底层原理。网上相关资料很多，我个人认为还是要从源码入手。直接看源码不容易理解，那么我们可以尝试自己写一个hashmap然后再逐步分析并参考源码来思考。

需求分析

首先从需求角度来想，明确什么是hashmap，为什么要用hashmap？
简单说，hashmap就是个存储键值对的集合，那么手写hashmap需要满足如下几点需求：
（1）可以存放多个键值对数据
（2）具有put和get方法，用于存取数据
（3）key值不可重复，当存入数据的key值存在时，覆盖原value
（4）既然叫hashmap，就要利用hash的特性提高效率，否则就是一种map而已称不上hashmap

编码思路

简单总结如上4点吧，现在开始写：
（1）创建一个名叫hashmap的类，类中写两个方法分别是put和get
（2）考虑到要写的是个集合，首先想到能利用的就是数组了，于是给hashmap类增加一个数组类型的成员变量table，以及整型的初始容量CAPACITY
(3)然而存放的数据是键值对，我们就需要创造这样一个“键值对”形式的对象。暂时取名叫Entry。

    class Entry<K, V> {
        public K key;
        public V value;
        public Entry<K, V> next;

        public Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }

这个Entry对象起码需要有两个成员变量，分别是key和value。然而考虑到hash冲突的问题，我们将Entry对象设计成链表的形式，实现在数组同一个index上存放多个Entry对象。当发生冲突时，将新的Entry对象的next变量指向前一个Entry对象（也就是插入前的table[index]），然后将table[index]上放入新的Entry对象（table[index]=newEntry）
（4）进一步完善put和get方法得到最终的hashmap类
需要完善如下几点问题：
1、完成从hash值到数组index下标的映射，这里采用取余的方式。
2、put方法中，当映射的index下标一致时，采用链表形式在index处存放Entry对象
3、get方法中，当映射的index下标一致时，遍历链表获取key值对应的value
4、当key值相同时，覆盖原有value
最终代码

public class MyHashMap<K, V> {

    private Entry<K, V>[] table;
    private static final Integer CAPACITY = 8;
    private int size;

    public void put(K k, V v) {
        if (table == null) {
            inflate();
        }
        //save entry
        int hashCode = hashCodeMethod(k);
        int index = getIndexOfHashCode(hashCode);

        for (Entry<K, V> entry = table[index]; entry != null; entry = entry.next) {
            if (entry.key.equals(k)) {
                entry.value = v;
                return;
            }
        }
        addEntry(k, v, index);

    }

    public V get(K k) {
        int hashCode = hashCodeMethod(k);
        int index = getIndexOfHashCode(hashCode);

        for (Entry<K, V> entry = table[index]; entry != null; entry = entry.next) {
            if (entry.key.equals(k)) {
                return entry.value;
            }
        }
        return null;
    }

    private void addEntry(K k, V v, int index) {
        Entry<K, V> newEntry = new Entry<>(k, v, table[index]);
        table[index] = newEntry;
        size++;
    }

    private int getIndexOfHashCode(int hashCode) {
        return hashCode % table.length;
    }

    private int hashCodeMethod(K k) {
        return k.hashCode();
    }

    private void inflate() {
        table = new Entry[CAPACITY];
    }

    class Entry<K, V> {
        public K key;
        public V value;
        public Entry<K, V> next;

        public Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }

    public static void main(String[] args) {
        MyHashMap<String,String> myHashMap = new MyHashMap<>();
        myHashMap.put("1","v");
        myHashMap.put("2","2v");
        myHashMap.put("2","3v");
        System.out.println(myHashMap.get("2"));
    }
}

深入思考

显然，这样的hashmap还存在很多问题，这些问题也正是我们要思考的：
1、数组的容量设置为了8，如果数据量较大时该怎么办？如何扩容？
2、完成从hash值到数组index下标的映射，这里采用取余的方式。
然而取余这种操作比较耗时，能否进一步提高效率？
3、get方法中，当映射的index下标一致时，遍历链表获取key值对应的value。然而遍历这种操作比较耗时，能否进一步提高效率？