之前转载过一篇HashMap相关分析文章，快速链接：HashMap实现原理分析

既然有前辈已经将源码分析总结了出来，我们在继续学习研究源码实现的时候不妨借鉴借鉴前人的总结与经验~

本文转自：https://blog.csdn.net/hefenglian/article/details/79763634 深度好文，先转载过来，慢慢研究。

一、底层数据结构

二、HashMap的实现原理：

JDK1.7中的HashMap

JDK1.8中的HashMap

三、HashMap加载因子

四、HashMap的构造函数

五、如何获取： get(object key) 方法

六、如何存储：put(k,v) 方法

七、HasMap的扩容机制resize()

八、JDK1.8使用红黑树的改进

九、如何解决hash冲突

十、hashMap与Hashtable区别

十、面试官提问

一、底层数据结构

在JDK1.6，JDK1.7中，HashMap采用位桶+链表实现，即使用链表处理冲突,同一hash值的键值对会被放在同一个位桶里，当桶中元素较多时，通过key值查找的效率较低。而JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）,时，将链表转换为红黑树，这样大大减少了查找时间。

二、HashMap的实现原理：

JDK1.7中的HashMap

HashMap底层维护一个数组，数组中的每一项都是一个Entry

transient Node<k,v>[] table;//存储（位桶）的数组</k,v>

我们向 HashMap 中所放置的对象实际上是存储在该数组当中；而Map中的key，value则以Entry的形式存放在数组中

static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;int hash;
}

而这个Entry应该放在数组的哪一个位置上（这个位置通常称为位桶或者hash桶，即hash值相同的Entry会放在同一位置，用链表相连），是通过key的hashCode来计算的。

final int hash(Object k) {int h = 0;h ^= k.hashCode();h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}

通过hash计算出来的值将会使用indexFor方法找到它应该所在的table下标：

static int indexFor(int h, int length) {return h & (length-1);//length=2 的整数次幂}

这个方法其实相当于对table.length取模。这里哈希值与上(length-1)，length=传入的容量是16的话，16-1=15，二进制1111，即对h取低四位，从而对应0-15个位桶。即无论我们指定的容量为多少，构造方法都会将实际容量设为不小于指定容量的2的次方的一个数，且最大值不能超过2的30次方

当两个key通过hashCode计算相同时，则发生了hash冲突(碰撞)，HashMap解决hash冲突的方式是用链表。

当发生hash冲突时，则将存放在数组中的Entry设置为新值的next（这里要注意的是，比如A和B都hash后都映射到下标i中，之前已经有A了，当map.put(B)时，将B放到下标i中，A则为B的next，所以新值存放在数组中，旧值在新值的链表上）

所以当hash冲突很多时，HashMap退化成链表。

总结一下map.put后的过程：

当向 HashMap 中 put 一对键值时，它会根据 key的 hashCode 值计算出一个位置，该位置就是此对象准备往数组中存放的位置。如果该位置没有对象存在，就将此对象直接放进数组当中；如果该位置已经有对象存在了，则顺着此存在的对象的链开始寻找(为了判断是否是否值相同，map不允许

private V putForNullKey(V value) {for (Entry<K,V> e = table[0]; e != null; e = e.next) {if (e.key == null) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;addEntry(0, null, value, 0);return null;}

当size大于threshold时，会发生扩容。 threshold等于capacity*load factor

void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);}

jdk7中resize，只有当 size>=threshold并且 table中的那个槽中已经有Entry时，才会发生resize。即有可能虽然size>=threshold，但是必须等到每个槽都至少有一个Entry时，才会扩容。还有注意每次resize都会扩大一倍容量

HashMap 原理图如下：

JDK1.8中的HashMap

一直到JDK7为止，HashMap的结构都是这么简单，基于一个数组以及多个链表的实现，hash值冲突的时候，就将对应节点以链表的形式存储。

这样子的HashMap性能上就抱有一定疑问，如果说成百上千个节点在hash时发生碰撞，存储一个链表中，那么如果要查找其中一个节点，那就不可避免的花费O(N)的查找时间，这将是多么大的性能损失。这个问题终于在JDK8中得到了解决。再最坏的情况下，链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。

JDK7中HashMap采用的是位桶+链表的方式，即我们常说的散列链表的方式，而JDK8中采用的是位桶+链表/红黑树（有关红黑树请查看红黑树）的方式，也是非线程安全的。当某个位桶的链表的长度达到某个阀值的时候，这个链表就将转换成红黑树。

JDK8中，当同一个hash值的节点数不小于8时，将不再以单链表的形式存储了，会被调整成一颗红黑树（上图中null节点没画）。这就是JDK7与JDK8中HashMap实现的最大区别。

接下来，我们来看下JDK8中HashMap的源码实现。

1.位桶数组
JDK中Entry的名字变成了Node，原因是和红黑树的实现TreeNode相关联。

transient Node<k,v>[] table;//存储（位桶）的数组</k,v>

2.数组元素Node

//Node是单向链表，它实现了Map.Entry接口  
static class Node<k,v> implements Map.Entry<k,v> {  final int hash;  final K key;  V value;  Node<k,v> next;  //构造函数Hash值 键 值 下一个节点  Node(int hash, K key, V value, Node<k,v> next) {  this.hash = hash;  this.key = key;  this.value = value;  this.next = next;  }  public final K getKey()        { return key; }  public final V getValue()      { return value; }  public final String toString() { return key + = + value; }  public final int hashCode() {  return Objects.hashCode(key) ^ Objects.hashCode(value);  }  public final V setValue(V newValue) {  V oldValue = value;  value = newValue;  return oldValue;  }  //判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true  public final boolean equals(Object o) {  if (o == this)  return true;  if (o instanceof Map.Entry) {  Map.Entry<!--?,?--> e = (Map.Entry<!--?,?-->)o;  if (Objects.equals(key, e.getKey()) &&  Objects.equals(value, e.getValue()))  return true;  }  return false;  }

3.红黑树

//红黑树  
static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {  TreeNode<k,v> parent;  // 父节点  TreeNode<k,v> left; //左子树  TreeNode<k,v> right;//右子树  TreeNode<k,v> prev;    // needed to unlink next upon deletion  boolean red;    //颜色属性  TreeNode(int hash, K key, V val, Node<k,v> next) {  super(hash, key, val, next);  }  //返回当前节点的根节点  final TreeNode<k,v> root() {  for (TreeNode<k,v> r = this, p;;) {  if ((p = r.parent) == null)  return r;  r = p;  }  }

三、HashMap加载因子

加载因子（默认0.75）：为什么需要使用加载因子，为什么需要扩容呢？

因为如果填充比很大，说明利用的空间很多，如果一直不进行扩容的话，链表就会越来越长，这样查找的效率很低，因为链表的长度很大（当然最新版本使用了红黑树后会改进很多），扩容之后，将原来链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置，这样就减少了每个链表的长度，增加查找效率

如果加载因子越大，对空间的利用更充分，但是查找效率会降低（链表长度会越来越长）；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成严重浪费。如果我们在构造方法中不指定，则系统默认加载因子为0.75，这是一个比较理想的值，一般情况下我们是无需修改的。

public class HashMap<k,v> extends AbstractMap<k,v> implements Map<k,v>, Cloneable, Serializable {  private static final long serialVersionUID = 362498820763181265L;  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量  static final float DEFAULT_LOAD_FACTOR = 0.75f;//填充比  //当add一个元素到某个位桶，其链表长度达到8时将链表转换为红黑树  static final int TREEIFY_THRESHOLD = 8;  static final int UNTREEIFY_THRESHOLD = 6;  static final int MIN_TREEIFY_CAPACITY = 64;  transient Node<k,v>[] table;//存储元素的数组  transient Set<map.entry<k,v>> entrySet;  transient int size;//存放元素的个数  transient int modCount;//被修改的次数fast-fail机制  int threshold;//临界值 当实际大小(容量*填充比)超过临界值时，会进行扩容   final float loadFactor;//填充比（......后面略）

四、HashMap的构造函数

HashMap的构造方法有4种，主要涉及到的参数有，指定初始容量，指定填充比和用来初始化的Map

//构造函数1  
public HashMap(int initialCapacity, float loadFactor) {  //指定的初始容量非负  if (initialCapacity < 0)  throw new IllegalArgumentException(Illegal initial capacity:  +  initialCapacity);  //如果指定的初始容量大于最大容量,置为最大容量  if (initialCapacity > MAXIMUM_CAPACITY)  initialCapacity = MAXIMUM_CAPACITY;  //填充比为正  if (loadFactor <= 0 || Float.isNaN(loadFactor))  throw new IllegalArgumentException(Illegal load factor:  +  loadFactor);  this.loadFactor = loadFactor;  this.threshold = tableSizeFor(initialCapacity);//新的扩容临界值  
}  //构造函数2  
public HashMap(int initialCapacity) {  this(initialCapacity, DEFAULT_LOAD_FACTOR);  
}  //构造函数3  
public HashMap() {  this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted  
}  //构造函数4用m的元素初始化散列映射  
public HashMap(Map<!--? extends K, ? extends V--> m) {  this.loadFactor = DEFAULT_LOAD_FACTOR;  putMapEntries(m, false);  
}

五、如何获取： get(object key) 方法

下面简单说下 get(key) 的过程：
get(key)方法时获取key的hash值，计算hash&(n-1)得到在链表数组中的位置first=tab[hash&(n-1)],先判断first（即数组中的那个，看图1）的key是否与参数key相等，不等就遍历后面的链表找到相同的key值返回对应的Value值即可

public V get(Object key) {  Node<K,V> e;  return (e = getNode(hash(key), key)) == null ? null : e.value;  }  /** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */  final Node<K,V> getNode(int hash, Object key) {  Node<K,V>[] tab;//Entry对象数组  Node<K,V> first,e; //在tab数组中经过散列的第一个位置  int n;  K k;  /*找到插入的第一个Node，方法是hash值和n-1相与，tab[(n - 1) & hash]*/  //也就是说在一条链上的hash值相同的  if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {  /*检查第一个Node是不是要找的Node*/  if (first.hash == hash && // always check first node  ((k = first.key) == key || (key != null && key.equals(k))))//判断条件是hash值要相同，key值要相同  return first;  /*检查first后面的node*/  if ((e = first.next) != null) {  if (first instanceof TreeNode)  return ((TreeNode<K,V>)first).getTreeNode(hash, key);  /*遍历后面的链表，找到key值和hash值都相同的Node*/  do {  if (e.hash == hash &&  ((k = e.key) == key || (key != null && key.equals(k))))  return e;  } while ((e = e.next) != null);  }  }  return null;  }

六、如何存储：put(k,v) 方法

下面简单说下添加键值对put(key,value)的过程：

判断键值对数组tab[]是否为空或为null，否则以默认大小resize()；
根据键值key计算hash值得到插入的数组索引i，如果tab[i]==null，直接新建节点添加，否则转入3
判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理

疑问：如果两个key通过hash%Entry[].length得到的index相同，会不会有覆盖的危险？
　　这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。打个比方，第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素，其它元素都在后面链表。到这里为止，HashMap的大致实现，我们应该已经清楚了。

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab;Node<K,V> p; int n, i;//如果当前map中无数据，执行resize方法。并且返回nif ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//如果要插入的键值对要存放的这个位置刚好没有元素，那么把他封装成Node对象，放在这个位置上就完事了if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);//否则的话，说明这上面有元素else {Node<K,V> e; K k;//如果这个元素的key与要插入的一样，那么就替换一下，也完事。if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//1.如果当前节点是TreeNode类型的数据，执行putTreeVal方法else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//还是遍历这条链子上的数据，跟jdk7没什么区别for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//2.完成了操作后多做了一件事情，判断，并且可能执行treeifyBin方法if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null) //true || --e.value = value;//3.afterNodeAccess(e);return oldValue;}}++modCount;//判断阈值，决定是否扩容if (++size > threshold)resize();//4.afterNodeInsertion(evict);return null;}

treeifyBin()就是将链表转换成红黑树。之前的indefFor()方法消失了，直接用(tab.length-1)&hash，所以看到这个，代表的就是数组的下角标。

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

七、HasMap的扩容机制resize()

构造hash表时，如果不指明初始大小，默认大小为16（即Node数组大小16），如果Node[]数组中的元素达到（填充比*Node.length）重新调整HashMap大小变为原来2倍大小,扩容很耗时

/** * Initializes or doubles table size.  If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */  final Node<K,V>[] resize() {  Node<K,V>[] oldTab = table;  int oldCap = (oldTab == null) ? 0 : oldTab.length;  int oldThr = threshold;  int newCap, newThr = 0;  /*如果旧表的长度不是空*/  if (oldCap > 0) {  if (oldCap >= MAXIMUM_CAPACITY) {  threshold = Integer.MAX_VALUE;  return oldTab;  }  
/*把新表的长度设置为旧表长度的两倍，newCap=2*oldCap*/  else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  oldCap >= DEFAULT_INITIAL_CAPACITY)  /*把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/  newThr = oldThr << 1; // double threshold  }  /*如果旧表的长度的是0，就是说第一次初始化表*/  else if (oldThr > 0) // initial capacity was placed in threshold  newCap = oldThr;  else {               // zero initial threshold signifies using defaults  newCap = DEFAULT_INITIAL_CAPACITY;  newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  }  if (newThr == 0) {  float ft = (float)newCap * loadFactor;//新表长度乘以加载因子  newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?  (int)ft : Integer.MAX_VALUE);  }  threshold = newThr;  @SuppressWarnings({"rawtypes","unchecked"})  
/*下面开始构造新表，初始化表中的数据*/  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];  table = newTab;//把新表赋值给table  if (oldTab != null) {//原表不是空要把原表中数据移动到新表中      /*遍历原来的旧表*/        for (int j = 0; j < oldCap; ++j) {  Node<K,V> e;  if ((e = oldTab[j]) != null) {  oldTab[j] = null;  if (e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置  newTab[e.hash & (newCap - 1)] = e;  else if (e instanceof TreeNode)  ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  
/*如果e后边有链表,到这里表示e后面带着个单链表，需要遍历单链表，将每个结点重*/  else { // preserve order保证顺序  新计算在新表的位置，并进行搬运  Node<K,V> loHead = null, loTail = null;  Node<K,V> hiHead = null, hiTail = null;  Node<K,V> next;  do {  next = e.next;//记录下一个结点  //新表是旧表的两倍容量，实例上就把单链表拆分为两队，  //e.hash&oldCap为偶数一队，e.hash&oldCap为奇数一对  if ((e.hash & oldCap) == 0) {  if (loTail == null)  loHead = e;  else  loTail.next = e;  loTail = e;  }  else {  if (hiTail == null)  hiHead = e;  else  hiTail.next = e;  hiTail = e;  }  } while ((e = next) != null);  if (loTail != null) {//lo队不为null，放在新表原位置  loTail.next = null;  newTab[j] = loHead;  }  if (hiTail != null) {//hi队不为null，放在新表j+oldCap位置  hiTail.next = null;  newTab[j + oldCap] = hiHead;  }  }  }  }  }  return newTab;  }

八、JDK1.8使用红黑树的改进

在java jdk8中对HashMap的源码进行了优化，在jdk7中，HashMap处理“碰撞”的时候，都是采用链表来存储，当碰撞的结点很多时，查询时间是O（n）。

在jdk8中，HashMap处理“碰撞”增加了红黑树这种数据结构，当碰撞结点较少时，采用链表存储，当较大时（>8个），采用红黑树（特点是查询时间是O（logn））存储（有一个阀值控制，大于阀值(8个)，将链表存储转换成红黑树存储）

问题分析：
你可能还知道哈希碰撞会对hashMap的性能带来灾难性的影响。如果多个hashCode()的值落到同一个桶内的时候，这些值是存储到一个链表中的。最坏的情况下，所有的key都映射到同一个桶中，这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)。

随着HashMap的大小的增长，get()方法的开销也越来越大。由于所有的记录都在同一个桶里的超长链表内，平均查询一条记录就需要遍历一半的列表。

JDK1.8HashMap的红黑树是这样解决的：

如果某个桶中的记录过大的话（当前是TREEIFY_THRESHOLD = 8），HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好，是O(logn)，而不是糟糕的O(n)。

它是如何工作的？前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面，这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的，不过如果实现了当然最好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了。

九、如何解决hash冲突

hash定义：

翻译为“散列”，就是把任意长度的输入，通过散列算法，变成固定长度的输出，该输出就是散列值。
这种转换是一种压缩映射，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。

解决hash冲突的办法:

开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）

开放定址法就是:一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

查找时：首先散列值所指向的槽，如果没有找到匹配，则继续从该槽遍历hash表，直到：（1）找到相应的元素；（2）找到一个空槽，指示查找的元素不存在，（所以不能随便删除元素）；（3）整个hash表遍历完毕（指示该元素不存在并且hash表是满的）

Hi = (H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列。di可有下列三种取法：

（1）di=1,2,3,…, m-1，称为线性探测再散列；

（2）di=1^2, -(1^2), 2^2, -(2^2), 3^2, …, ±(k^2),(k<=m/2)，称二为次探测再散列；

（3）di=伪随机数序列，称为伪随机探测再散列。

（所谓伪随机数，用同样的随机种子，将得到相同的数列。)

比如说，我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34},表长为12。我们用散列函数f(key) = key mod l2
当计算前S个数{12,67,56,16,25}时，都是没有冲突的散列地址，直接存入：

计算key = 37时，发现f(37) = 1，此时就与25所在的位置冲突。
于是我们应用上面的公式f(37) = (f(37)+1) mod 12 = 2。于是将37存入下标为2的位置：

链地址法（拉链法）

将所有哈希地址相同的元素都链接到同一个链表中。

再哈希法（再散列，多重散列）

产生冲突时，使用第二个，第三个、、、哈希函数计算地址，直到冲突不再发生为止。增加了计算时间。
Java中hashmap的解决办法就是采用的链地址法。

建立一个公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表.。

查找时，对给定key通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出表进行顺序查找。

十、hashMap与Hashtable区别

继承的父类不同

Hashtable继承自Dictionary类，而HashMap继承自AbstractMap类。但二者都实现了Map接口。

线程安全性不同

Hashtable 线程安全：因为它每个方法中都加入了Synchronize，对整个table加锁
HashMap是线程不安全的：
HashMap底层是一个Entry数组，当发生hash冲突的时候，hashmap是采用链表的方式来解决的，在对应的数组位置存放链表的头结点。对链表而言，新加入的节点会从头结点加入。

我们来分析一下多线程访问：
1）在hashmap做put操作的时候会调用addEntry方法：
现在假如A线程和B线程同时对同一个桶调用addEntry，两个线程会同时得到现在的头结点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。

2）**调用删除键值对方法**removeEntryForKey(Object key)
多个线程对同一个桶操作时，同时得到数组中的头结点，并发访问和修改，会造成修改覆盖

3）put新的键值对后，若键值对总数量超过门限值的时候会调用一个resize操作：
这个操作会新生成一个新的容量的数组，然后对原数组的所有键值对重新进行计算和写入新的数组，之后指向新生成的数组。
当多个线程同时检测到总数量超过门限值的时候就会同时调用resize操作，各自生成新的数组并rehash后赋给该map底层的数组table，结果最终只有最后一个线程生成的新数组被赋给table变量，其他线程的均会丢失。而且当某些线程已经完成赋值而其他线程刚开始的时候，就会用已经被赋值的table作为原始数组，这样也会有问题。

是否提供contains方法

HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey，因为contains方法容易让人引起误解。
Hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同。

key和value是否允许null值

其中key和value都是对象，并且不能包含重复key，但可以包含重复的value。
通过上面的ContainsKey方法和ContainsValue的源码我们可以很明显的看出：
HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，可能是 HashMap中没有该键，也可能使该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键，而应该用containsKey()方法来判断。
Hashtable中，key和value都不允许出现null值。但是如果在Hashtable中有类似put(null,null)的操作，编译同样可以通过，因为key和value都是Object类型，但运行时会抛出NullPointerException异常，这是JDK的规范规定的。

两个遍历方式的内部实现上不同

HashMap使用 Iterator。
Hashtable使用Iterator，还使用了Enumeration的方式。

hash值不同

HashTable直接使用对象的hashCode。而HashMap重新计算hash值。

hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值。

HashMap重新计算了key的hash值，HashMap在求位置索引时，则用与运算，即 hash&(length-1)

Hashtable计算hash值：直接用key的hashCode()，Hashtable在求hash值对应的位置索引时，用取模运算，且这里一般先用hash&0x7FFFFFFF后，再对length取模，&0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而&0x7FFFFFFF后，只有符号外改变，而后面的位都不变。

内部实现使用的数组初始化和扩容方式不同

HashTable初始默认容量为11，Hashtable不要求底层数组的容量一定要为2的整数次幂， Hashtable扩容时，将容量变为原来的2倍加1，
而HashMap初始默认容量为为16，而HashMap则要求一定为2的整数次幂，而HashMap扩容时，将容量变为原来的2倍。

十、面试官提问

1）介绍HashMap：
按照特性来说明一下：储存的是键值对，线程不安全，非Synchronied，储存的比较快，能够接受null。

按照工作原理来叙述一下：Map的put（key，value）来储存元素，通过get（key）来得到value值，通过hash算法来计算hascode值，用hashCode标识Entry在bucket中存储的位置，储存结构就算哈希表。

“2）你知道HashMap的工作原理吗？” “你知道HashMap的get()方法的工作原理吗？”
“HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。
当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。
”这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Entry。
这一点有助于理解获取对象的逻辑。如果你没有意识到这一点，或者错误的认为仅仅只在bucket中存储值的话，你将不会回答如何从HashMap中获取对象的逻辑。这个答案相当的正确，也显示出面试者确实知道hashing以及HashMap的工作原理。

3）提问：两个hashcode相同的时候会发生说明？
hashcode相同，bucket的位置会相同，也就是说会发生碰撞，哈希表中的结构其实有链表（LinkedList），这种冲突通过将元素储存到LinkedList中，解决碰撞。储存顺序是放在表头。

4）如果两个键的hashcode相同，如何获取值对象？
如果两个键的hashcode相同，即找到bucket位置之后，我们通过key.equals（）找到链表LinkedList中正确的节点，最终找到要找的值对象。
一些优秀的开发者会指出使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。

5）如果HashMap的大小超过了负载因子(load factor)定义的容量？怎么办？
HashMap里面默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。

6）重新调整HashMap大小的话会出现什么问题？
多线程情况下会出现竞争问题，因为你在调节的时候，LinkedList储存是按照顺序储存，调节的时候回将原来最先储存的元素（也就是最下面的）遍历，多线程就好试图重新调整，这个时候就会出现死循环。

当多线程的情况下，可能产生条件竞争(race condition)。
当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。

7）HashMap在并发执行put操作，会引起死循环，为什么？
是因为多线程会导致hashmap的node链表形成环形链表，一旦形成环形链表，node 的next节点永远不为空，就会产生死循环获取node。从而导致CPU利用率接近100%。

8）为什么String, Interger这样的wrapper类适合作为键？
因为他们一般不是不可变的，源码上面final，使用不可变类，而且重写了equals和hashcode方法，避免了键值对改写。提高HashMap性能。

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

9）使用CocurrentHashMap代替Hashtable？
可以，但是Hashtable提供的线程更加安全。
Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable，但是HashTable提供更强的线程安全性。

10）hashing的概念
散列法（Hashing）或哈希法是一种将字符组成的字符串转换为固定长度（一般是更短长度）的数值或索引值的方法，称为散列法，也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快，这种方法一般用来在数据库中建立索引并进行搜索，同时还用在各种解密算法中。

11）扩展：为什么equals()方法要重写？
判断两个对象在逻辑上是否相等，如根据类的成员变量来判断两个类的实例是否相等，而继承Object中的equals方法只能判断两个引用变量是否是同一个对象。这样我们往往需要重写equals()方法。

我们向一个没有重复对象的集合中添加元素时，集合中存放的往往是对象，我们需要先判断集合中是否存在已知对象，这样就必须重写equals方法。

怎样重写equals()方法？

重写equals方法的注意点：