Java HashMap实现原理分析

参考链接:https://www.cnblogs.com/xiarongjin/p/8310011.html

1. HashMap的数据结构

数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。

 数组

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

链表

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

哈希表

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

  哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法—— 拉链法,我们可以理解为“链表的数组” ,如图:

Java HashMap实现原理分析

Java HashMap实现原理分析

  从上图我们可以发现哈希表是由数组+链表组成的,一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

  HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。

  首先HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */

transient Entry[] table;

2. HashMap的存取实现

既然是线性数组,为什么能随机存取?这里HashMap用了一个小算法,大致是这样实现:

Java HashMap实现原理分析
// 存储时:
int hash = key.hashCode(); // 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值
int index = hash % Entry[].length;
Entry[index] = value; // 取值时:

int hash = key.hashCode();

int index = hash % Entry[].length;

return Entry[index];
Java HashMap实现原理分析

1)put

 
疑问:如果两个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的大致实现,我们应该已经清楚了。

Java HashMap实现原理分析
public V put(K key, V value) {
if (key == null)
return putForNullKey(value); //null总是放在数组的第一个链表中
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;
//如果key在链表中已存在,则替换为新value
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;
} 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); //参数e, 是Entry.next

//如果size超过threshold,则扩充table大小。再散列

if (size++ >= threshold)

resize(2 * table.length);

}
Java HashMap实现原理分析

当然HashMap里面也包含一些优化方面的实现,这里也说一下。比如:Entry[]的长度一定后,随着map里面数据的越来越长,这样同一个index的链就会很长,会不会影响性能?HashMap里面设置一个因子,随着map的size越来越大,Entry[]会以一定的规则加长长度。

2)get

Java HashMap实现原理分析
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
//先定位到数组元素,再遍历该元素处的链表
for (Entry<K,V> 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;
}
Java HashMap实现原理分析

3)null key的存取

null key总是存放在Entry[]数组的第一个元素。

Java HashMap实现原理分析
 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;
}
</span><span style="color: #0000ff;">private</span><span style="color: #000000;"> V getForNullKey() {
</span><span style="color: #0000ff;">for</span> (Entry&lt;K,V&gt; e = table[0]; e != <span style="color: #0000ff;">null</span>; e =<span style="color: #000000;"> e.next) {
</span><span style="color: #0000ff;">if</span> (e.key == <span style="color: #0000ff;">null</span><span style="color: #000000;">)
</span><span style="color: #0000ff;">return</span><span style="color: #000000;"> e.value;
}
</span><span style="color: #0000ff;">return</span> <span style="color: #0000ff;">null</span><span style="color: #000000;">;
}</span></span></pre>
Java HashMap实现原理分析

4)确定数组index:hashcode % table.length取模

HashMap存取时,都需要计算当前key应该对应Entry[]数组哪个元素,即计算数组下标;算法如下:

Java HashMap实现原理分析
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
Java HashMap实现原理分析
按位取并,作用上相当于取模mod或者取余%。
这意味着数组下标相同,并不表示hashCode相同。
 

5)table初始大小

Java HashMap实现原理分析
public HashMap(int initialCapacity, float loadFactor) {
.....
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
Java HashMap实现原理分析

注意table初始大小并不是构造函数中的initialCapacity!!

而是 >= initialCapacity的2的n次幂!!!!

————为什么这么设计呢?——

3. 解决hash冲突的办法

  1. 开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)
  2. 再哈希法
  3. 链地址法
  4. 建立一个公共溢出区

Java中hashmap的解决办法就是采用的链地址法。

4. 再散列rehash过程

当哈希表的容量超过默认容量时,必须调整table的大小。当容量已经达到最大可能值时,那么该方法就将容量调整到Integer.MAX_VALUE返回,这时,需要创建一张新表,将原表的映射到新表中。

Java HashMap实现原理分析
/**
* 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 be a power of two;
* must be greater than current capacity unless current
* capacity is MAXIMUM_CAPACITY (in which case value
* is irrelevant).
*/
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
</span><span style="color: #008000;">/**</span><span style="color: #008000;">
* Transfers all entries from current table to newTable.
</span><span style="color: #008000;">*/</span>
<span style="color: #0000ff;">void</span><span style="color: #000000;"> transfer(Entry[] newTable) {
Entry[] src </span>=<span style="color: #000000;"> table;
</span><span style="color: #0000ff;">int</span> newCapacity =<span style="color: #000000;"> newTable.length;
</span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> j = 0; j &lt; src.length; j++<span style="color: #000000;">) {
Entry</span>&lt;K,V&gt; e =<span style="color: #000000;"> src[j];
</span><span style="color: #0000ff;">if</span> (e != <span style="color: #0000ff;">null</span><span style="color: #000000;">) {
src[j] </span>= <span style="color: #0000ff;">null</span><span style="color: #000000;">;
</span><span style="color: #0000ff;">do</span><span style="color: #000000;"> {
Entry</span>&lt;K,V&gt; next =<span style="color: #000000;"> e.next;
</span><span style="color: #008000;">//</span><span style="color: #008000;">重新计算index</span>
<span style="color: #0000ff;">int</span> i =<span style="color: #000000;"> indexFor(e.hash, newCapacity);
e.next </span>=<span style="color: #000000;"> newTable[i];
newTable[i] </span>=<span style="color: #000000;"> e;
e </span>=<span style="color: #000000;"> next;
} </span><span style="color: #0000ff;">while</span> (e != <span style="color: #0000ff;">null</span><span style="color: #000000;">);
}
}
}</span></span></pre>
Java HashMap实现原理分析
  • 第二篇文章

1 数据结构:hash_map原理 
这是一节让你深入理解hash_map的介绍,如果你只是想囫囵吞枣,不想理解其原理,你倒是可以略过这一节,但我还是建议你看看,多了解一些没有坏处。 

hash_map基于hash table(哈希表)。哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。 

其基本原理是:使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数,也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标,hash值)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素“分类”,然后将这个元素存储在相应“类”所对应的地方,称为桶。 

但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中。 总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。 

hash_map,首先分配一大片内存,形成许多桶。是利用hash函数,对key进行映射到不同区域(桶)进行保存。其插入过程是: 

   1. 得到key 
   2. 通过hash函数得到hash值 
   3. 得到桶号(一般都为hash值对桶数求模) 
   4. 存放key和value在桶内。 

其取值过程是: 

   1. 得到key 
   2. 通过hash函数得到hash值 
   3. 得到桶号(一般都为hash值对桶数求模) 
   4. 比较桶的内部元素是否与key相等,若都不相等,则没有找到。 
   5. 取出相等的记录的value。

hash_map中直接地址用hash函数生成,解决冲突,用比较函数解决。这里可以看出,如果每个桶内部只有一个元素,那么查找的时候只有一次比较。当许多桶内没有值时,许多查询就会更快了(指查不到的时候). 

由此可见,要实现哈希表, 和用户相关的是:hash函数(hashcode)和比较函数(equals)。

假定哈希函数将元素正确分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。迭代集合视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)的和成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。 HashMap 的实例有两个参数影响其性能:初始容量 和加载因子容量 是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,通过调用 rehash 方法将容量翻倍。 通常,默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点)。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地降低 rehash 操作次数。如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。 如果很多映射关系要存储在 HashMap 实例中,则相对于按需执行自动的 rehash 操作以增大表的容量来说,使用足够大的初始容量创建它将使得映射关系能更有效地存储。 注意,此实现不是同步的。如果多个线程同时访问此映射,而其中至少一个线程从结构上修改了该映射,则它必须 保持外部同步。(结构上的修改是指添加或删除一个或多个映射关系的操作;仅改变与实例已经包含的键关联的值不是结构上的修改。)这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象,则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作,以防止对映射进行意外的不同步访问,如下所示: Map m = Collections.synchronizedMap(new HashMap(...)); 

Java HashMap实现原理分析

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道HashTable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考察的深度很深。这题经常出现在高级或中高级面试中。投资银行更喜欢问这个问题,甚至会要求你实现HashMap来考察你的编程能力。ConcurrentHashMap和其它同步集合的引入让这道题变得更加复杂。让我们开始探索的旅程吧!

先来些简单的问题

“你用过HashMap吗?” “什么是HashMap?你为什么用到它?”

几乎每个人都会回答“是的”,然后回答HashMap的一些特性,譬如HashMap可以接受null键值和值,而HashTable则不能;HashMap是非synchronized;HashMap很快;以及HashMap储存的是键值对等等。这显示出你已经用过HashMap,而且对它相当的熟悉。但是面试官来个急转直下,从此刻开始问出一些刁钻的问题,关于HashMap的更多基础的细节。面试官可能会问出下面的问题:

“你知道HashMap的工作原理吗?” “你知道HashMap的get()方法的工作原理吗?”

你也许会回答“我没有详查标准的JavaAPI,你可以看看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使用LinkedList存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在LinkedList中。”这个答案非常的合理,虽然有很多种处理碰撞的方法,这种方法是最简单的,也正是HashMap的处理方法。但故事还没有完结,面试官会继续问:

“如果两个键的hashcode相同,你如何获取值对象?” 面试者会回答:当我们调用get()方法,HashMap会使用键对象的hashcode找到bucket位置,然后获取值对象。面试官提醒他如果有两个值对象储存在同一个bucket,他给出答案:将会遍历LinkedList直到找到值对象。面试官会问因为你并没有值对象去比较,你是如何确定确定找到值对象的?除非面试者直到HashMap在LinkedList中存储的是键值对,否则他们不可能回答出这一题。

其中一些记得这个重要知识点的面试者会说,找到bucket位置之后,会调用keys.equals()方法去找到LinkedList中正确的节点,最终找到要找的值对象。完美的答案!

许多情况下,面试者会在这个环节中出错,因为他们混淆了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需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在LinkedList中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在LinkedList的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。这个时候,你可以质问面试官,为什么这么奇怪,要在多线程的环境下使用HashMap呢?:)

热心的读者贡献了更多的关于HashMap的问题:

  1. 为什么String, Interger这样的wrapper类适合作为键? String, Interger这样的wrapper类作为HashMap的键是再适合不过了,而且String最为常用。因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。
  2. 我们可以使用自定义的对象作为键吗? 这是前一个问题的延伸。当然你可能使用任何对象作为键,只要它遵守了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了。
  3. 我们可以使用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使用LinkedList来解决碰撞问题,当发生碰撞了,对象将会储存在LinkedList的下一个节点中。 HashMap在每个LinkedList节点中储存键值对对象。

当两个不同的键对象的hashcode相同时会发生什么? 它们会储存在同一个bucket位置的LinkedList中。键对象的equals()方法用来找到键值对。

因为HashMap的好处非常多,我曾经在电子商务的应用中使用HashMap作为缓存。因为金融领域非常多的运用Java,也出于性能的考虑,我们会经常用到HashMap和ConcurrentHashMap。你可以查看更多的关于HashMap和HashTable的文章。

  • 第三篇文章

hashmap本质数据加链表。根据key取得hash值,然后计算出数组下标,如果多个key对应到同一个下标,就用链表串起来,新插入的在前面。

看3段重要代码摘要:

a:

Java HashMap实现原理分析
public HashMap(int initialCapacity, float loadFactor) {
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
</span><span style="color: #0000ff;">this</span>.loadFactor =<span style="color: #000000;"> loadFactor;
threshold </span>= (<span style="color: #0000ff;">int</span>)(capacity *<span style="color: #000000;"> loadFactor);
table </span>= <span style="color: #0000ff;">new</span><span style="color: #000000;"> Entry[capacity];
init();

}

Java HashMap实现原理分析
有3个关键参数:
capacity:容量,就是数组大小
loadFactor:比例,用于扩容
threshold:=capacity*loadFactor 最多容纳的Entry数,如果当前元素个数多于这个就要扩容(capacity扩大为原来的2倍)
b:
Java HashMap实现原理分析
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> 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;
}
Java HashMap实现原理分析

根据key算hash值,再根据hash值取得数组下标,通过数组下标取出链表,遍历链表用equals取出对应key的value。

c:

Java HashMap实现原理分析
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</span>++<span style="color: #000000;">;
addEntry(hash, key, value, i);
</span><span style="color: #0000ff;">return</span> <span style="color: #0000ff;">null</span><span style="color: #000000;">;
} </span></span></pre>
Java HashMap实现原理分析

从数组(通过hash值)取得链表头,然后通过equals比较key,如果相同,就覆盖老的值,并返回老的值。(该key在hashmap中已存在)

否则新增一个entry,返回null。新增的元素为链表头,以前相同数组位置的挂在后面。

另外:modCount是为了避免读取一批数据时,在循环读取的过程中发生了修改,就抛异常

if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

下面看添加一个map元素

Java HashMap实现原理分析
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);
}
Java HashMap实现原理分析

新增后,如果发现size大于threshold了,就resize到原来的2倍

Java HashMap实现原理分析
void resize(int newCapacity) {  
Entry[] newTable </span>= <span style="color: #0000ff;">new</span><span style="color: #000000;"> Entry[newCapacity];
transfer(newTable);
table </span>=<span style="color: #000000;"> newTable;
threshold </span>= (<span style="color: #0000ff;">int</span>)(newCapacity *<span style="color: #000000;"> loadFactor);

}

Java HashMap实现原理分析

新建一个数组,并将原来数据转移过去

Java HashMap实现原理分析
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
Java HashMap实现原理分析

将原来数组中的链表一个个取出,然后遍历链表中每个元素,重新计算index并放入新数组。每个处理的也放链表头。

在取出原来数组链表后,将原来数组置空(为了大数据量复制时更快的被垃圾回收?)

还有两点注意:

static class Entry<K,V> implements Map.Entry<K,V>是hashmap的静态内部类,iterator之类的是内部类,因为不是每个元素都需要持有map的this指针。

HashMap把  transient Entry[] table;等变量置为transient,然后override了readObject和writeObject,自己实现序列化。

  • ConcurrentHashMap:

在hashMap的基础上,ConcurrentHashMap将数据分为多个segment,默认16个(concurrency level),然后每次操作对一个segment加锁,避免多线程锁得几率,提高并发效率。

Java HashMap实现原理分析
public V get(Object key) {
int hash = hash(key.hashCode());
return segmentFor(hash).get(key, hash);
} final Segment<K,V> segmentFor(int hash) {

return segments[(hash >>> segmentShift) & segmentMask];

}
Java HashMap实现原理分析

in class Segment:

Java HashMap实现原理分析
V get(Object key, int hash) {
if (count != 0) { // read-volatile
HashEntry<K,V> e = getFirst(hash);
while (e != null) {
if (e.hash == hash && key.equals(e.key)) {
V v = e.value;
if (v != null)
return v;
return readValueUnderLock(e); // recheck
}
e = e.next;
}
}
return null;
}
Java HashMap实现原理分析
Java HashMap实现原理分析
 /**
* Reads value field of an entry under lock. Called if value
* field ever appears to be null. This is possible only if a
* compiler happens to reorder a HashEntry initialization with
* its table assignment, which is legal under memory model
* but is not known to ever occur.
*/
V readValueUnderLock(HashEntry<K,V> e) {
lock();
try {
return e.value;
} finally {
unlock();
}
}
Java HashMap实现原理分析

注意,这里在并发读取时,除了key对应的value为null之外,并没有使用锁,如何做到没有问题的呢,有以下3点:
1.       HashEntry<K,V> getFirst(int hash) {
            HashEntry<K,V>[] tab = table;
            return tab[hash & (tab.length - 1)];
        }
这里如果在读取时数组大小(tab.length)发生变化,是会导致数据不对的,但transient volatile HashEntry<K,V>[] table;是volatile得,数组大小变化能立刻知道

2.    static final class HashEntry<K,V> {
        final K key;
        final int hash;
        volatile V value;
        final HashEntry<K,V> next;
这里next是final的,就保证了一旦HashEntry取出来,整个链表就是正确的。

3.value是volatile的,保证了如果有put覆盖,是可以立刻看到的。

Java HashMap实现原理分析
public V put(K key, V value) {
if (value == null)
throw new NullPointerException();
int hash = hash(key.hashCode());
return segmentFor(hash).put(key, hash, value, false);
} V put(K key, int hash, V value, boolean onlyIfAbsent) {

lock();

try {

int c = count;

if (c++ > threshold) // ensure capacity

rehash();

HashEntry<K,V>[] tab = table;

int index = hash & (tab.length - 1);

HashEntry<K,V> first = tab[index];

HashEntry<K,V> e = first;

while (e != null && (e.hash != hash || !key.equals(e.key)))

e = e.next;
            V oldValue;
</span><span style="color: #0000ff;">if</span> (e != <span style="color: #0000ff;">null</span><span style="color: #000000;">) {
oldValue </span>=<span style="color: #000000;"> e.value;
</span><span style="color: #0000ff;">if</span> (!<span style="color: #000000;">onlyIfAbsent)
e.value </span>=<span style="color: #000000;"> value;
}
</span><span style="color: #0000ff;">else</span><span style="color: #000000;"> {
oldValue </span>= <span style="color: #0000ff;">null</span><span style="color: #000000;">;
</span>++<span style="color: #000000;">modCount;
tab[index] </span>= <span style="color: #0000ff;">new</span> HashEntry&lt;K,V&gt;<span style="color: #000000;">(key, hash, first, value);
count </span>= c; <span style="color: #008000;">//</span><span style="color: #008000;"> write-volatile </span>

}

return oldValue;

} finally {

unlock();

}

}

Java HashMap实现原理分析

这里除了加锁操作,其他和普通HashMap原理上无太大区别。

还有一点不理解的地方:

对于get和put/remove并发发生的时候,如果get的HashEntry<K,V> e = getFirst(hash);链表已经取出来了,这个时候put放入一个entry到链表头,如果正好是需要取的key,是否还是会取不出来?

remove时,会先去除需要remove的key,然后把remove的key前面的元素一个个接到链表头,同样也存在remove后,以前的head到了中间,也会漏掉读取的元素。

Java HashMap实现原理分析
                     ++modCount;
HashEntry<K,V> newFirst = e.next;
for (HashEntry<K,V> p = first; p != e; p = p.next)
newFirst = new HashEntry<K,V>(p.key, p.hash,
newFirst, p.value);
tab[index] = newFirst;
count = c; // write-volatile
Java HashMap实现原理分析
上一篇:spring mvc 在上传图片时,浏览器报The request sent by the client was syntactically incorrect


下一篇:总结HashMap实现原理分析