最近面试时，经常被问到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。然而遍历这种操作比较耗时，能否进一步提高效率？
