Java刷题知识点之HashMap的实现原理、HashMap的存储结构、HashMap在JDK1.6、JDK1.7、JDK1.8之间的差异以及带来的性能影响
Java刷题知识点之HashMap的实现原理、HashMap的存储结构、HashMap在JDK1.6、JDK1.7、JDK1.8之间的差异以及带来的性能影响
HashMap的实现原理
　　HashMap是基于java.util.map接口的实现，该实现提供了所有的对Map的可选操作，同时也允许null类型的key以及value （HashTable与此大致相同，只是HashTable是同步的，不过HashTable一般被认为是已经过时的，很少有人再去用了）。
HashMap的实现原理
　　HashMap是基于java.util.map接口的实现，该实现提供了所有的对Map的可选操作，同时也允许null类型的key以及value （HashTable与此大致相同，只是HashTable是同步的，不过HashTable一般被认为是已经过时的，很少有人再去用了）。
　　HashMap不保证Map中的顺序，特别是不能保证数据在一段时间内的顺序性。
　　如果散列函数（Hash函数）在正确的在桶中分散元素，HashMap的实现提供了对基本的操作（put与get）时间性能为常数。
　　集合视图的迭代需要的时间与HashMap实例的容量capacity值（桶数）和大小（键值对个数）成正比，所以如果对迭代器的性能比较关注， 那么不要把初始化的容量capacity值设的太高或不要将装填因子load factor设的太小就非常重要。
　　HashMap的实例总有两个非常重要的影响性能的参数：初始容量大小（initial capacity）与装填因子（load factor）。
在HashMap中，capacity就是buckets的数量，初始容量大小就是在HashMap创建的时候指定的capacity。
　　装填因子指的是HashMap在多满的时候就需要提前自动扩容了（如初始化容量16，装填因子0.75，一旦元素个数 超过16*0.75=12个的时候，就需要对容量进行扩充，翻倍） 扩容需要rehash，也就是说HashMap内部结构会被重新构建。
　　通常来讲，默认的装填因子0.75提供了一个基于时间与空间代价比较好的平衡。桶中装的更满意味着空间开销更低， 但是查找开销变大（反映到HashMap中就是包含get与put在内各种操作开销变大，时间变长）。
　　当设置初始容量大小时，应该考虑HashMap中预期的数量以及装填因子，这样才能让rehash执行的次数最少， 如果初始化大小的值比实际数据的条数乘以装填因子的积还要大，那么就不会发生rehash。
　　如果有非常多的记录存在HashMap中，那么在初始化这个HashMap的时候将容量capacity设置的足够大，比自动rehash 扩容效率更高。
　　注意如果很多key有了相同的hashCode值，那么会对性能造成很大的影响（产生聚集问题，rehash次数变多，性能下降），为了改善这种情况 当key可以进行比较（继承了Comparable接口之类的），HashMap会采用对key进行比较排序。
　　注意：HashMap不是线程同步的。
　　如果多线程并发访问一个HashMap，同时至少有一个线程修改了HashMap的结构，那么该HashMap必须要在外部进行同步 （结构的改变指的是添加或删除一个映射关系-键值对，只是根据key修改了value的值不会对HashMap造成结构上的影响） 这种同步操作通常在封装有HashMap的Object中实现；如果没有这样的对象实现，那么HashMap需要采用Collections.synchronizedMap 来保证多线程并发环境下的数据同步问题，这个操作最好在创建HashMap的时候就去做。 Map m = Collections.synchronizedMap(new HashMap(…));
　　如果HashMap产生的迭代器创建后，HashMap数据结构又发生了变化，则除了remove方法外，迭代器iterator会抛出一个 ConcurrentModificationException异常，这就是迭代器的快速失败（fail-fast）。 因此面对并发修改，迭代器采用快速而干净的失败来取代在未来的某一个不确定的时间产生不确定的后果。
　　注意：迭代器的快速失败行为是无法保证的，通常来讲，在非同步并发修改的情况下这种硬性保证都没法给出，快速失败也只能尽量抛出 ConcurrentModificationException异常，所以不能写一段代码去基于该异常做出义务逻辑处理，最好快速失败进行BUG探测。
HashMap的存储结构
　　HashMap的存储，本质上是构造了一个table，根据计算的hashCode将对应的KV存储到该table中，一旦发生hashCode冲突，那么就会将该KV放到对应的已有元素的后面， 此时，形成了一个链表式的存储结构，即：HashMap 就是一个table数组
链表实现的存储结构（在JDK1.8之前的存储结构），如下图所示：
　　 从上图中，我们可以发现哈希表是由数组
链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。它的内部其实是用一个Entity数组来实现的，属性有key、value、next。
　　当构造出一个HashMap后，每次put一个元素时，会执行addEntry操作，addEntry中会执行创建一个Entry实体存储当前的KV，如果有Hash冲突， 那么就会将当前的entry指向最后一个冲突的entry，同时将当前的entry放到链表中，执行完当前操作后，判断是否需要resize，如果需要，则构造出一个新的entry数组（比之前大一倍）， 并将原有的数组中的entry链表（或entry）拷贝到新的数组中。
　　在JDK1.8中有了一些变化，当链表的存储的数据个数大于等于8的时候，不再采用链表存储，而采用了红黑树存储结构。如下图所示：
　　 这么做主要是查询的时间复杂度上，链表为O(n)，而红黑树一直是O(logn)，一般来讲，冲突（即为相同的hash值存储的元素个数） 超过8个，红黑树的性能高于链表的查找性能。
HashMap在JDK1.6中的实现方式
　　put方法：
　　put方法完成数据的基本写入操作，同时会验证数据的有效性，如key是否为空的处理，计算hash值，hash值 的查找，并根据hash值找出所有的数据，判断是否重复，如果重复，则替换，并返回旧值，如果不重复，则写入数据（addEntry）。
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with &tt&key&/tt&, or
&tt&null&/tt& if there was no mapping for &tt&key&/tt&.
(A &tt&null&/tt& return can also indicate that the map
previously associated &tt&null&/tt& with &tt&key&/tt&.)
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) {
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.
e.recordAccess(this);
return oldV
modCount++;
addEntry(hash, key, value, i);
return null;
　　对应的addEntry方法： addEntry方法实现了数据的写入以及判断是否需要对HashMap进行扩容。
* Adds a new entry with the specified key, value and hash code to
* the specified bucket.
It is the responsibility of this
* method to resize the table if appropriate.
* Subclass overrides this to alter the behavior of put method.
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry&K,V& e = table[bucketIndex];
table[bucketIndex] = new Entry&K,V&(hash, key, value, e);
if (size++ &= threshold)
resize(2 * table.length);
　　resize方法： resize方法主要是对Map进行扩容的实际操作：构造存储结构，并调用数据转移方法transfer进行数据转移
* Rehashes the contents of this map into a new array with a
* larger capacity.
This method is called automatically when the
* number of keys in this map reaches its threshold.
* If current capacity is MAXIMUM_CAPACITY, this method does not
* resize the map, but sets threshold to Integer.MAX_VALUE.
* This has the effect of preventing future calls.
* @param newCapacity the new capacity, MUST
must be greater than current capacity unless current
capacity is MAXIMUM_CAPACITY (in which case value
is irrelevant).
void resize(int newCapacity) {
Entry[] oldTable =
int oldCapacity = oldTable.
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newT
threshold = (int)(newCapacity * loadFactor);
　　transfer 方法： 完成数据转移，注意，转移的过程就是两个数组进行数据拷贝的过程，数据产生了倒置，新元素其实是插入到了第一个位置。
* Transfers all entries from current table to newTable.
void transfer(Entry[] newTable) {
Entry[] src =
int newCapacity = newTable.
for (int j = 0; j & src. j++) {
Entry&K,V& e = src[j];
if (e != null) {
src[j] = null;
do {//每次循环都是将第一个元素指向了最新的数据，其他数据后移（链式存储，更改指向）
Entry&K,V& next = e.
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] =
} while (e != null);
　　 Entry的构造： 链式存储结构。
static class Entry&K,V& implements Map.Entry&K,V& {
Entry&K,V&
* Creates new entry.
Entry(int h, K k, V v, Entry&K,V& n) {
HashMap在JDK1.7中的实现
　　JDK1.7中的实现与JDK1.6中的实现总体来说，基本没有改进，区别不大。
　　put 方法：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry&K,V& e = table[i]; e != null; e = e.next) {
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.
e.recordAccess(this);
return oldV
modCount++;
addEntry(hash, key, value, i);
return null;
　　addEntry方法：
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);
　　resize方法：
void resize(int newCapacity) {
Entry[] oldTable =
int oldCapacity = oldTable.
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newT
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
　　transfer方法：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.
for (Entry&K,V& e : table) {
while(null != e) {
Entry&K,V& next = e.
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] =
　　createEntry方法：
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization).
This version needn't worry about resizing the table.
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry&K,V& e = table[bucketIndex];
table[bucketIndex] = new Entry&&(hash, key, value, e);
HashMap在JDK1.8中的实现
　　put方法： put方法中与JDK1.6/1.7相比，新增了判断是否是TreeNode的逻辑，TreeNode即为红黑树， 同时添加了冲突的元素个数是否大于等于7的判断（因为第一个是-1，所以还是8个元素），如果冲突的元素个数超过8个，则构造红黑树（treeifyBin方法），否则还是按照链表方式存储。
* Implements Map.put and related methods
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node&K,V&[] Node&K,V& int n,
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).
if ((p = tab[i = (n - 1) & hash]) == null)//取模运算，寻址无冲突，写入数据
tab[i] = newNode(hash, key, value, null);
else {//存在冲突
Node&K,V& K
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
else if (p instanceof TreeNode)//集合中已经是红黑树了
e = ((TreeNode&K,V&)p).putTreeVal(this, tab, hash, key, value);
for (int binCount = 0; ; ++binCount) {//冲突时的数据写入逻辑，判断是否需要构造红黑树
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount &= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
if (e != null) { // existing mapping for key
V oldValue = e.
if (!onlyIfAbsent || oldValue == null)
afterNodeAccess(e);
return oldV
if (++size & threshold)
afterNodeInsertion(evict);
return null;
　　treeifyBin方法： treeifyBin方法主要是将链式存储的冲突的数据转换成树状存储结构
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
final void treeifyBin(Node&K,V&[] tab, int hash) {
int n, Node&K,V&
if (tab == null || (n = tab.length) & MIN_TREEIFY_CAPACITY)
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode&K,V& hd = null, tl = null;
TreeNode&K,V& p = replacementTreeNode(e, null);
if (tl == null)
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
　　resize方法： 注意：JDK1.8中resize方法扩容时对链表保持了原有的顺序。
* 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 =
int oldCap = (oldTab == null) ? 0 : oldTab.
int oldThr =
int newCap, newThr = 0;
if (oldCap & 0) {
if (oldCap &= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldT
else if ((newCap = oldCap && 1) & MAXIMUM_CAPACITY &&
oldCap &= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr && 1; // double threshold
else if (oldThr & 0) // initial capacity was placed in threshold
newCap = oldT
// 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 * loadF
newThr = (newCap & MAXIMUM_CAPACITY && ft & (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
threshold = newT
@SuppressWarnings({"rawtypes","unchecked"})
Node&K,V&[] newTab = (Node&K,V&[])new Node[newCap];
table = newT
if (oldTab != null) {
for (int j = 0; j & oldC ++j) {
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] =
else if (e instanceof TreeNode)
((TreeNode&K,V&)e).split(this, newTab, j, oldCap);
else { // preserve order
Node&K,V& loHead = null, loTail = null;
Node&K,V& hiHead = null, hiTail = null;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loTail.next =
if (hiTail == null)
hiTail.next =
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loH
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiH
return newT
HashMap的不足以及产生原因
　　多线程并发问题
　　在多线程并发环境下会有如下一种情况：
　　两个线程同时操作时同时遇到HashMap需要扩容，且映射到相同的地址（key计算得到的HashCode相同），此时在扩容时可能发生一种情况， 两个线程同时对HashMap进行扩容，扩容时做第一次循环时一个线程阻塞，另一个完成扩容，前一个继续，那么就可能发生链表数据的相互指向问题， 造成get数据时遍历的死循环
　　测试代码如下：
final Map&Integer, String& map = new HashMap&&(2);
map.put(3, "3");
Thread t = new Thread(new Runnable() {
public void run() {
map.put(5, "5");
}, "thread");
Thread t2 = new Thread(new Runnable() {
public void run() {
map.put(7, "7");
}, "thread2");
t.start();
t2.start();
t2.join();
　　注意：我参考了大量的网上的一些博客，他们基本都是基于JDK1.6进行的分析，即：先写入数据，再扩容：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry&K,V& e = table[bucketIndex];
table[bucketIndex] = new Entry&K,V&(hash, key, value, e);//先写数据
if (size++ &= threshold)
resize(2 * table.length);//再扩容
　　由此，很容易产生上述问题，而在JDK1.7中发生了变化，先扩容，再进行数据写入：
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);//再写入数据
　　此时，先扩容，再写入数据，就不会产生这种问题，但是会产生另一中问题，即： HashMap中有A元素，thread1 写入B元素（碰撞），thread2写入C元素（碰撞） 线程thread1先扩容，在写入数据，同时线程thread2也进行该操作那么，最终互不影响， thread1得到：B-&A链表，thread2得到：C-&A链表，那么，在thread1中取数据，能否取到C元素？ 多线程并发问题依旧存在。
　　在JDK1.8中，HashMap的这块儿做了大量改进，死循环问题已经解决了：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);//直接追加到最后节点中
if (binCount &= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);//构造红黑树
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
　　但是JDK1.8 中通过测试发现依然存在JDK1.7中的数据丢失情况。
　　同时在并发情况下会出现如下新的问题： Hash碰撞情况下：前一个线程判断是链表存储，准备写入数据，但是写入时阻塞，其他线程也准备写入，发现数据链表为8，此时构造红黑树，然后完成数据转移 前一个线程此后写入数据时，就会出现类型错误：
Exception in thread "24590 _subThread" java.lang.ClassCastException: java.util.HashMap$Node cannot be cast to java.util.HashMap$TreeNode
at java.util.HashMap$TreeNode.moveRootToFront(HashMap.java:1827)
at java.util.HashMap$TreeNode.treeify(HashMap.java:1944)
at java.util.HashMap$TreeNode.split(HashMap.java:2170)
at java.util.HashMap.resize(HashMap.java:713)
at java.util.HashMap.putVal(HashMap.java:662)
at java.util.HashMap.put(HashMap.java:611)
at com.lin.map.HashMapDeadLoopTest$1$1.run(HashMapDeadLoopTest.java:37)
at java.lang.Thread.run(Thread.java:745)
相关测试代码（可能需要多执行几次）：
public class HashMapDeadLoopTest {
public void test() throws InterruptedException {
final Map&String, String& map = Collections.synchronizedMap(new HashMap&&(2048));
final Map&String, String& map = new HashMap&&(2048);
Thread t = new Thread(new Runnable() {
public void run() {
for (int i = 0; i & 100000; i++) {
final int x =
new Thread(new Runnable() {
public void run() {
put(map, x);
},i+" _subThread").start();
if(i!=0 && i%10000==0){
System.out.println("1:"+map.size());
},"thread");
Thread t2 = new Thread(new Runnable() {
public void run() {
for (int i = 0; i & 100000; i++) {
final int x =
new Thread(new Runnable() {
public void run() {
put(map, x);
},i+" _subThread2").start();
if(i!=0 && i%10000==0){
System.out.println("2:"+map.size());
},"thread2");
Thread t3 = new Thread(new Runnable() {
public void run() {
for (int i = 0; i & 100000; i++) {
final int x =
new Thread(new Runnable() {
public void run() {
put(map, x);
},i+" _subThread3").start();
if(i!=0 && i%10000==0){
System.out.println("3:"+map.size());
},"thread3");
t.start();
t2.start();
t3.start();
t2.join();
t3.join();
String getKey(){
return RandomStringUtils.randomAlphanumeric(32);
void put(Map&String,String& map,int index){
String key = getKey();
map.put(key, key);
if(map.get(key)==null){
System.out.println(key+",元素缺失，index:"+index);
HashMap的JDK1.6、JDK1.7、JDK1.8中的实现各不相同，尤其以JDK1.8变化最大，注意区分
本文转自大数据躺过的坑博客园博客，原文链接：http://www.cnblogs.com/zlslch/p/7622756.html，如需转载请自行联系原作者
用云栖社区APP，舒服~
【云栖快讯】新手小白必看！编程语言系列讲座火爆进行中，与行业资深专家一起学习Python、C++、JavaScript、Java！从入门到进阶&&
文章2091篇
构建在阿里云飞天分布式系统之上的NoSQL数据存储服务，提供海量结构化数据的存储和实时访问。
支持以数据库为核心的结构化存储产品之间的数据传输。 它是一种集数据迁移、数据订阅及数据实时同...
基于大数据的移动云服务。帮助App快速集成移动推送的功能，在实现高效、精确、实时的移动推送的...
为您提供简单高效、处理能力可弹性伸缩的计算服务，帮助您快速构建更稳定、安全的应用，提升运维效...
云通信517活动HashMap的工作原理 - ImportNew
HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap，都知道哪里要用HashMap，知道，那么为何这道面试题如此特殊呢？是因为这道题考察的深度很深。这题经常出现在高级或中高级面试中。投资银行更喜欢问这个问题，甚至会要求你实现HashMap来考察你的编程能力。ConcurrentHashMap和其它同步集合的引入让这道题变得更加复杂。让我们开始探索的旅程吧！
先来些简单的问题
“你用过HashMap吗？” “什么是HashMap？你为什么用到它？”
几乎每个人都会回答“是的”，然后回答HashMap的一些特性，譬如HashMap可以接受null键值和值，而Hashtable则不能；HashMap是非HashMap很快；以及HashMap储存的是键值对等等。这显示出你已经用过HashMap，而且对它相当的熟悉。但是面试官来个急转直下，从此刻开始问出一些刁钻的问题，关于HashMap的更多基础的细节。面试官可能会问出下面的问题：
“你知道HashMap的工作原理吗？” “你知道HashMap的get()方法的工作原理吗？”
你也许会回答“我没有详查标准的Java API，你可以看看Java源代码或者Open JDK。”“我可以用Google找到答案。”
但一些面试者可能可以给出答案，“HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。”这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Entry。这一点有助于理解获取对象的逻辑。如果你没有意识到这一点，或者错误的认为仅仅只在bucket中存储值的话，你将不会回答如何从HashMap中获取对象的逻辑。这个答案相当的正确，也显示出面试者确实知道hashing以及HashMap的工作原理。但是这仅仅是故事的开始，当面试官加入一些Java程序员每天要碰到的实际场景的时候，错误的答案频现。下个问题可能是关于HashMap中的碰撞探测(collision detection)以及碰撞的解决方法：
“当两个对象的hashcode相同会发生什么？” 从这里开始，真正的困惑开始了，一些面试者会回答因为hashcode相同，所以两个对象是相等的，HashMap将会抛出异常，或者不会存储它们。然后面试官可能会提醒他们有equals()和hashCode()两个方法，并告诉他们两个对象就算hashcode相同，但是它们可能并不相等。一些面试者可能就此放弃，而另外一些还能继续挺进，他们回答“因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。”这个答案非常的合理，虽然有很多种处理碰撞的方法，这种方法是最简单的，也正是HashMap的处理方法。但故事还没有完结，面试官会继续问：
“如果两个键的hashcode相同，你如何获取值对象？” 面试者会回答：当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，然后获取值对象。面试官提醒他如果有两个值对象储存在同一个bucket，他给出答案:将会遍历链表直到找到值对象。面试官会问因为你并没有值对象去比较，你是如何确定确定找到值对象的？除非面试者直到HashMap在链表中存储的是键值对，否则他们不可能回答出这一题。
其中一些记得这个重要知识点的面试者会说，找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。完美的答案！
许多情况下，面试者会在这个环节中出错，因为他们混淆了hashCode()和equals()方法。因为在此之前hashCode()屡屡出现，而equals()方法仅仅在获取值对象的时候才出现。一些优秀的开发者会指出使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。
如果你认为到这里已经完结了，那么听到下面这个问题的时候，你会大吃一惊。“如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？”除非你真正知道HashMap的工作原理，否则你将回答不出这道题。默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。
如果你能够回答这道问题，下面的问题来了：“你了解重新调整HashMap大小存在什么问题吗？”你可能回答不上来，这时面试官会提醒你当多线程的情况下，可能产生条件竞争(race condition)。
当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。这个时候，你可以质问面试官，为什么这么奇怪，要在多线程的环境下使用HashMap呢？：）
热心的读者贡献了更多的关于HashMap的问题：
为什么String, Interger这样的wrapper类适合作为键？ String, Interger这样的wrapper类作为HashMap的键是再适合不过了，而且String最为常用。因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的，那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。
我们可以使用自定义的对象作为键吗？ 这是前一个问题的延伸。当然你可能使用任何对象作为键，只要它遵守了equals()和hashCode()方法的定义规则，并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的，那么它已经满足了作为键的条件，因为当它创建之后就已经不能改变了。
我们可以使用CocurrentHashMap来代替Hashtable吗？这是另外一个很热门的面试题，因为ConcurrentHashMap越来越多人用了。我们知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable，但是HashTable提供更强的线程安全性。看看查看Hashtable和ConcurrentHashMap的区别。
我个人很喜欢这个问题，因为这个问题的深度和广度，也不直接的涉及到不同的概念。让我们再来看看这些问题设计哪些知识点：
hashing的概念
HashMap中解决碰撞的方法
equals()和hashCode()的应用，以及它们在HashMap中的重要性
不可变对象的好处
HashMap多线程的条件竞争
重新调整HashMap的大小
HashMap的工作原理
HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。
当两个不同的键对象的hashcode相同时会发生什么？ 它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。
因为HashMap的好处非常多，我曾经在电子商务的应用中使用HashMap作为缓存。因为金融领域非常多的运用Java，也出于性能的考虑，我们会经常用到HashMap和ConcurrentHashMap。你可以查看更多的关于HashMap的文章:
原文链接：
- 译文链接： [ 转载请保留原文出处、译者和译文链接。]
关于作者：
一名在路上的程旭媛
update user_account set amount = amount+30 where u...
关于ImportNew
ImportNew 专注于 Java 技术分享。于日 11:11正式上线。是的，这是一个很特别的时刻 :)
ImportNew 由两个 Java 关键字 import 和 new 组成，意指：Java 开发者学习新知识的网站。 import 可认为是学习和吸收， new 则可认为是新知识、新技术圈子和新朋友……
新浪微博：
推荐微信号
反馈建议：ImportNew.
广告与商务合作QQ：
– 好的话题、有启发的回复、值得信赖的圈子
– 写了文章？看干货？去头条！
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 活跃 & 专业的翻译小组
– 国内外的精选博客文章
– UI,网页，交互和用户体验
– JavaScript, HTML5, CSS
– 专注Android技术分享
– 专注iOS技术分享
– 专注Java技术分享
– 专注Python技术分享
& 2018 ImportNew}