HashMap和HashTable的实现原理

一、HashMap

1.HashMap概述：

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

2.HashMap的数据结构：

在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。如下图，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。

源码：

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

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

3.HashMap的存储实现：

public V put(K key, V value) {      // HashMap允许存放null键和null值。      // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。      if (key == null)          return putForNullKey(value);      // 根据key的keyCode重新计算hash值。      int hash = hash(key.hashCode());      // 搜索指定hash值在对应table中的索引。      int i = indexFor(hash, table.length);      // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。      for (Entry 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;          }      }      // 如果i索引处的Entry为null，表明此处还没有Entry。      modCount++;      // 将key、value添加到i索引处。      addEntry(hash, key, value, i);      return null;  }  

从源码得：当我们往HashMap中put元素时，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组的位置（下标），如果数组该位置已经存放了其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

addEntry(hash,key,value,i)方法根据计算出的hash值，将Key-Value对放在数组table的i索引处。addEntry是HashMap提供的一个包访问权限的方法，方法如下：

void addEntry(int hash, K key, V value, int bucketIndex) {      // 获取指定 bucketIndex 索引处的 Entry       Entry e = table[bucketIndex];      // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry      table[bucketIndex] = new Entry(hash, key, value, e);      // 如果 Map 中的 key-value 对的数量超过了极限      if (size++ >= threshold)      // 把 table 对象的长度扩充到原来的2倍。          resize(2 * table.length);  }  

当系统决定存储HashMap中的Key-Value对时，完全没有考虑Entry中的Value，仅仅只是根据key来计算并决定每个Entry的存储位置。即当系统决定了key的存储位置之后，value随之保存在那里即可。

hash(int h)方法根据key的hashCode重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的hash冲突。

static int hash(int h) {      h ^= (h >>> 20) ^ (h >>> 12);      return h ^ (h >>> 7) ^ (h >>> 4);  }  

我们得知在HashMap中要找到某个元素，需要根据key得到hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。上面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap中的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大的优化了查询的效率。

对于任意给定的对象，只要它的HashCode()返回值相同，那么程序调用Hash(int h)方法所计算得到的hash值总是相同的。我们首先想到的就是把Hash值对数组的长度取模运算，这么一来，元素的分布相对来说是比较均匀的。但是模运算的消耗还是比较大的，HashMap中：调用indexFor(int h,int length)方法来计算该对象应该保存在table数组的哪个索引处。

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

HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。

当数组长度为2的n次幂的时候，不同的Key算得的index相同的几率较小，那么数据在数组上分布就比较均匀，也就是碰撞的几率·比较小。相对的，查询的时候就不用遍历某个位置上的链表，这样查询的效率也就比较高了。

4.HashMap的读取实现：

public V get(Object key) {      if (key == null)          return getForNullKey();      int hash = hash(key.hashCode());      for (Entry e = table[indexFor(hash, table.length)];          e != null;          e = e.next) {          Object k;          if (e.hash == hash && ((k = e.key) == key || key.equals(k)))              return e.value;      }      return null;  }  

从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一个元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。即：HashMap在底层将key-Value当成一个整体进行处理，这个整体就是一个Entry对象。HashMap底层采用了一个Entry[]数组来保存所有的键值对，当需要存储一个Entry对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，在根据equals方法从该位置上的链表中取出该Entry。

5.HashMap的resize(rehash)：

当hashMap中的元素越来越多的时候，hash冲突的几率也越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。当HashMap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩容为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

6.Fail-Fast机制：

我们知道HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了Map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现是用过modCount域（修改次数）对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectModCount。在迭代过程中，判断modCount跟expectModCount是否相等，如果不想等就表示已经有其他线程修改了Map。（modCount声明为volatile，保证了线程之间的可见性）。

final Entry nextEntry() {         if (modCount != expectedModCount)             throw new ConcurrentModificationException(); 

7.关于HashMap的问题：

为什么String、Integer这样的wrapper类适合作为键？

String、Integer这样的wrapper类作为HashMap的键是在适合不过了，而且String最为常用，因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算HashCode(),就要防止键值改变，如果键值在放入时和获取时返回不同的hashCode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的，那么请这么做。因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashCode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。

我们可以使用自定义的对象作为键吗？

这是前一个问题的延伸。当然你可能使用任何对象作为键，只要它遵循了equals()和hashCode()方法的定义规则，并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的，那么它已经满足了作为键的条件，因为当它创建之后就已经不能改变了。

我们可以使用ConcurrentHashMap来代替HashTable吗？

这是另外一个很热门的面试题，因为ConcurrentHashMap越来越多人用了。我们知道HashTable是synchronized的，但是ConcurrentHashMap同步性能更好，因为它仅仅根据同步级别对Map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable，但是HashTable提供更强的线程安全性。

二、HashTable

1.HashTable概述：

和HashMap一样，HashTable也是一个散列表，它存储的内容是键值对映射。HashTable继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。HashTable的函数都是同步的，这意味着它是线程安全的。它的Key、Value都不可以为null。此外，HashTable中的映射不是有序的。

HashTable的实例有两个参数影响其性能：初始容量和加载因子。容量是哈希表中桶的数量，初始容量就是哈希表创建时的容量。注意，哈希表的状态为open：在发生“哈希冲突”的情况下，单个桶会存储多个条目，这些条目必须按顺序搜索。加载因子是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用rehash方法的具体细节则依赖于该实现。通常，默认加载因子是0.75。

2.Hash Table的数据结构：

HashTable与Map关系如下

public class Hashtable      extends Dictionary      implements Map, Cloneable, java.io.Serializable 

HashTable并没有去继承AbstractMap，而是选择继承了Dictionary类，Dictionary是个被废弃的抽象类。

3.实现原理：

成员变量跟HashMap基本类似，但是HashMap更加规范，HashMap内部还定义了一些常量，比如默认的负载因子，默认的容量，最大容量等。

public Hashtable(int initialCapacity, float loadFactor) {//可指定初始容量和加载因子          if (initialCapacity <0)              throw new IllegalArgumentException("Illegal Capacity: "+                                                 initialCapacity);          if (loadFactor <= 0 || Float.isNaN(loadFactor))              throw new IllegalArgumentException("Illegal Load: "+loadFactor);          if (initialCapacity==0)              initialCapacity = 1;//初始容量最小值为1          this.loadFactor = loadFactor;          table = new Entry[initialCapacity];//创建桶数组          threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);//初始化容量阈值          useAltHashing = sun.misc.VM.isBooted() &&                  (initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);      }      /**      * Constructs a new, empty hashtable with the specified initial capacity      * and default load factor (0.75).      */      public Hashtable(int initialCapacity) {          this(initialCapacity, 0.75f);//默认负载因子为0.75      }      public Hashtable() {          this(11, 0.75f);//默认容量为11，负载因子为0.75      }      /**      * Constructs a new hashtable with the same mappings as the given      * Map.  The hashtable is created with an initial capacity sufficient to      * hold the mappings in the given Map and a default load factor (0.75).      */      public Hashtable(Map t) {          this(Math.max(2*t.size(), 11), 0.75f);          putAll(t);      }  

——HashTable的默认容量为11，默认负载因子为0.75。（HashMap默认容量是16，默认负载因子也是0.75）

——HashTable的容量可以为任意整数，最小值为1，而HashMap的容量始终为2的n次方。

——为避免扩容带来的性能问题，建议指定合理容量。跟HashMap一样，HashTable内部也有一个静态类叫Entry，其实是个键值对，保存了键和值的引用。也可以理解为一个单链表的节点，因为其持有下一个Entry对象的引用。

4.HashTable的存取实现：

HashTable和HashMap存储的都是键值对对象，而不是单独的键或值。

public synchronized V put(K key, V value) {//向哈希表中添加键值对          // Make sure the value is not null          if (value == null) {//确保值不能为空              throw new NullPointerException();          }          // Makes sure the key is not already in the hashtable.          Entry tab[] = table;          int hash = hash(key);//根据键生成hash值---->若key为null，此方法会抛异常          int index = (hash & 0x7FFFFFFF) % tab.length;//通过hash值找到其存储位置          for (Entry e = tab[index] ; e != null ; e = e.next) {/遍历链表              if ((e.hash == hash) && e.key.equals(key)) {//若键相同，则新值覆盖旧值                  V old = e.value;                  e.value = value;                  return old;              }          }          modCount++;          if (count >= threshold) {//当前容量超过阈值。需要扩容              // Rehash the table if the threshold is exceeded              rehash();//重新构建桶数组，并对数组中所有键值对重哈希，耗时！              tab = table;              hash = hash(key);              index = (hash & 0x7FFFFFFF) % tab.length;//这里是取摸运算          }          // Creates the new entry.          Entry e = tab[index];          //将新结点插到链表首部          tab[index] = new Entry<>(hash, key, value, e);//生成一个新结点          count++;          return null;      }  

public synchronized V get(Object key) {//根据键取出对应索引        Entry tab[] = table;        int hash = hash(key);//先根据key计算hash值        int index = (hash & 0x7FFFFFFF) % tab.length;//再根据hash值找到索引        for (Entry e = tab[index] ; e != null ; e = e.next) {//遍历entry链            if ((e.hash == hash) && e.key.equals(key)) {//若找到该键                return e.value;//返回对应的值            }        }        return null;//否则返回null    }  

——HashTable并不允许值和键为空，若为空，则抛出空指针异常。

——HashMap计算索引的方式是h&(length-1)，而HashTable用的是模运算，效率上是低于HashMap的。

——HashTable计算索引时将hash值先与上0x7fffffff，这是为了保证hash值始终为整数。

——HashTable中若干方法都添加了synchronized关键字，也就意味着这个HashTable是个线程安全的类，这是它与HashMap最大的不同点。

——HashTable每次扩容都是旧容量的2倍加2，而HashMap为旧容量的2倍。