HashMap底层就是一个数组结构，数组中的每一项又是一个链表。
jdk源码：
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
//.....
}
table就是一个Node类的数组，而Node类继承了Map.Entry<k,v>。每个 Map.Entry 其实就是一个键值对对，它还持有一个指向下一个元素的引用"next"，这就构成了链表。如下图：
table数组的索引在逻辑上叫做“桶”(bucket)，它存储了链表的第一个元素。而key的hashcode()方法用来找到Entry对象所在的桶，也就是寻找index。当两个key有相同的hash值，他们会被放在table数组的同一个桶里面。
好了，直接看HashMap的工作原理：
HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。
当两个不同的键对象的hashcode相同时会发生什么？ 它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。
实现demo：
public class HashMapDemo<K, V> {
private class Entry<K, V> {
int hash;
K key;
V value;
Entry<K, V> next;
Entry(int hash, K key, V value, Entry<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
private static final int DEFAULT_CAPACITY = 1 << 4;
private Entry<K, V>[] table;
private int capacity;
private int size;
public HashMapDemo() {
this(DEFAULT_CAPACITY);
}
public HashMapDemo(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException();
} else {
table = new Entry[capacity];
size = 0;
this.capacity = capacity;
}
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0 ? true : false;
}
private int hash(K key) {
double tmp = key.hashCode() * (Math.pow(5, 0.5) - 1) / 2;
double digit = tmp - Math.floor(tmp);
return (int) Math.floor(digit * capacity);
}
public void put(K key, V value) {
if (key == null) {
throw new IllegalArgumentException();
}
int hash = hash(key);
Entry<K, V> nEntry = new Entry<K, V>(hash, key, value, null);
Entry<K, V> entry = table[hash];
while (entry != null) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
entry = entry.next;
}
nEntry.next = table[hash];
table[hash] = nEntry;
size++;
}
public V get(K key) {
if (key == null) {
throw new IllegalArgumentException();
}
int hash = hash(key);
Entry<K, V> entry = table[hash];
while (entry != null) {
if (entry.key.equals(key)) {
return entry.value;
}
entry = entry.next;
}
return null;
}
public static void main(String[] args) {
HashMapDemo<String, String> map = new HashMapDemo<String, String>();
map.put("1", "11");
map.put("1", "22");
map.put("3", "33");
System.out.println(map.get("1"));
System.out.println(map.get("3"));
}
}
面试小问：“如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？”除非你真正知道HashMap的工作原理，否则你将回答不出这道题。默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。
-------------------待完善