HashMap工作原理

数组

数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；
数组的特点是：寻址容易，插入和删除困难；

链表

链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。
链表的特点是：寻址困难，插入和删除容易。

哈希表

那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表。
哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。

基本原理

表达式：hash(key)%arr.length(这里hash(key)是f(k),即我们常说的散列函数)

f(k1)=f(k2)则散列到数组的同一个下标中，通过链表next依次存放，通过匹配key，获取值。
f(null)会被存放在arr[0]中,只能存一个元素，再次存取会返回oldValue;两个key相同时也是采取这种策略，新的值替换旧值，并返回旧值。

public V put(K key, V value) {  
      if (key == null)  
          return putForNullKey(value);  
      int hash = hash(key.hashCode());  
      int i = indexFor(hash, table.length);  
      for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
          Object k;  
          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
              V oldValue = e.value;  
              e.value = value;  
              e.recordAccess(this);  
              return oldValue;  
          }  
      }  
 
      modCount++;  
      addEntry(hash, key, value, i);  
      return null;  
  }

定位数组中的位置

书本上是采用 % 模运算
而实际是用的 & 按位与运算，“模”运算的消耗还是比较大的

1
2
3

static int indexFor(int h, int length) {  
       return h & (length-1);  
   }

巧妙之处：通过哈希值和length 按位与获得位置
一个简单的情况：length = 16,length-1 = 15,二进制码是1111,那么任意一个h（如1110，1111）按位与都是它自身h,而且没有冲突。

哈希表长度

length总是2^n(2的倍数),每次超过阈值之后会采用一个,这也是为什么length总是2^n(2的倍数)

1 2	if (size++ >= threshold) resize(2 * table.length);

threshold = capacity * loadFactor,loadFactor默认为0.75.

HashTable和HashMap

Hashtable的轻量级实现（非线程安全的实现），他们都完成了Map接口，主要区别在于HashMap允许空（null）键值（key）,由于非线程安全，在只有一个线程访问的情况下，效率要高于Hashtable。
HashMap允许将null作为一个entry的key或者value，而Hashtable不允许。
HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解。
Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现。
最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap 就必须为之提供外同步。
Hashtable和HashMap采用的hash/rehash算法都大概一样，所以性能不会有很大的差异。同步上的性能，HashMap会更优秀

就HashMap与HashTable主要从三方面来说，

历史原因:Hashtable是基于陈旧的Dictionary类的，HashMap是Java 1.2引进的Map接口的一个实现
同步性:Hashtable是线程安全的，也就是说是同步的，而HashMap是线程序不安全的，不是同步的
值：只有HashMap可以让你将空值作为一个表的条目的key或value

Reference

HashMap实现原理分析
 HashMap源码分析