Hashmap工作原理

在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

  
/** 
 * The table, resized as necessary. Length MUST Always be a power of two. 
 */  
transient Entry[] table;  
  
static class Entry<K,V> implements Map.Entry<K,V> {  
    final K key;  
    V value;  
    Entry<K,V> next;  
    final int hash;  
    ……  
}  

可以看出，Entry就是数组中的元素，每个 Map.Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用，这就构成了链表。

添加元素时，根据key的hash值得到这个元素在数组中的位置，把元素放到对应的位置上。 如果这个位置上有其他元素则以链表的形式存放，新进的放在链头，之前的放在链尾。 取元素时，先通过key的hash获取数组位置，再通过key的equals方法获取链表中的元素。

如果数组的大小不足以存放元素时，就需要进行扩容(resize)，此操作非常消耗性能应尽量避免。

扩展链接:

Java 8系列之重新认识HashMap