Java集合类是个要命重大的知识点,可以看看线程停在了transfer方法的while循环处”

“通过jconsole(只怕thread
dump),能够看出线程停在了transfer方法的while循环处”

注:
前天看看的1篇讲hashMap,hashTable,concurrentHashMap很透彻的一篇小说,
谢谢原文者的分享. 
初稿地址: http://blog.csdn.net/zhangerqing/article/details/8193118 

http://www.udpwork.com/item/2321.html

Java集合类是个可怜重大的知识点,HashMap、HashTable、ConcurrentHashMap等算是集合类中的重点,可谓“重中之重”,首先来看个问题,如面试官问你:HashMap和HashTable有何分别,1个相比较不难的作答是:

剖析拾2线程并发写HashMap线程被hang住的原委

kafka0102 发表于 2010年08月07日
05:05 | Hits: 4367

Tag: java |
HashMap

在blogjava上看看一文什么人能协理解释一下为何那么些程序会死锁?,激发了自家那能害死猫的惊讶,所以很伤脑筋的雕琢了那个题材。由于涉及的内容较多,就独自发文解说一下。

文中涉及的题材先后如下:

public class TestLock {
  private final HashMap map = new HashMap();
  public TestLock() {
    final Thread t1 = new Thread() {
      @Override
      public void run() {
        for(int i=0; i<500000; i++) {
          map.put(new Integer(i), i);
        }
        System.out.println("t1 over");
      }
    };
    final Thread t2 = new Thread() {
      @Override
      public void run() {
        for(int i=0; i<500000; i++) {
          map.put(new Integer(i), i);
        }
        System.out.println("t2 over");
      }
    };
    t1.start();
    t2.start();
  }
 
  public static void main(final String[] args) {
    new TestLock();
  }
}

正是启了八个线程,不断的往2个非线程安全的HashMap中put内容,put的剧情很简短,key和value都是从0自增的平头(那几个put
的始末做的并倒霉,以致于后来烦扰了本人分析难点的思路)。对HashMap做并发写操作,小编原以为只不过会生出脏数据的景色,但反复运维这些顺序,会油然则生
线程t1、t贰被hang住的情形,多数情状下是2个线程被hang住另二当中标甘休,偶尔会三个线程都被hang住。提及那里,你要是以为倒霉好学习
ConcurrentHashMap而在那瞎折腾就手下留情跳过吧。
好啊,分析下HashMap的put函数源码看看难点出在哪,那里就罗列出相关代码(jdk一.陆):

public V put(final K key, final V value) {
    if (key == null) {
      return putForNullKey(value);
    }
    final int hash = hash(key.hashCode());
    final int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {//@标记1
      Object k;
      if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        final V oldValue = e.value;
        e.value = value;
        e.recordAccess(this);
        return oldValue;
      }
    }
 
    modCount++;
    addEntry(hash, key, value, i);
    return null;
  }
 
void addEntry(final int hash, final K key, final V value, final int bucketIndex) {
    final Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold) {
      resize(2 * table.length);
    }
  }
 
void resize(final int newCapacity) {
    final Entry[] oldTable = table;
    final int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return;
    }
 
    final Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
  }
 
void transfer(final Entry[] newTable) {
    final Entry[] src = table;
    final int newCapacity = newTable.length;
    final long time1 = System.currentTimeMillis();
    for (int j = 0; j < src.length; j++) {
      Entry<K,V> e = src[j];
      if (e != null) {
        src[j] = null;
        int k=0;//@标记2
        do {
          final Entry<K,V> next = e.next;
          final int i = indexFor(e.hash, newCapacity);
          e.next = newTable[i];
          newTable[i] = e;
          e = next;
          if (k++ > 1000) {//@标记3
            System.out.println(Thread.currentThread().getName()+
                ",e==next:"+(e==e.next)+",e==next.next:"+(e==e.next.next)+
                ",e:"+e+",next:"+e.next+",eq:"+e.equals(e.next));
            try {
              Thread.sleep(2000);
            } catch (final Exception e2) {
            }
 
          }
        } while (e != null);
      }
    }
  }

透过jconsole(也许thread
dump),能够看到线程停在了transfer方法的while循环处。这几个transfer方法的职能是,当Map一月素数超过阈值须要resize
时,它肩负把原Map中的成分映射到新Map中。作者修改了HashMap,加上了@标记二和@标记叁的代码片断,以打字与印刷出死循环时的情况,结果死循环线程
总是出现就像是这样的出口:“Thread-
一,e==next:false,e==next.next:true,e:108928=10892捌,next:拾892八=十8928,eq:true”。
以此输出注解:
一)这几个Entry链中的多少个Entry之间的关联是:e=e.next.next,造成死循环。
2)e.equals(e.next),但e!=e.next。因为测试例子中多少个线程put的情节同样,并发时只怕同一个key被封存了三个value,那种张冠李戴是在addEntry函数发生的,但这和线程死循环未有涉嫌。

接下去就分析transfer中那一个while循环了。先所说那几个轮回符合规律的效益:src[j]保存的是炫耀成同一个hash值的五个Entry的
链表,这一个src[j]莫不为null,大概唯有贰个Entry,也说不定由多少个Entry链接起来。如果是三个Entry,原来的链是
(src[j]=a)->b(也就是src[j]=a,a.next=b,b.next=null),经过while处理后收获了
(newTable[i]=b)->a。也正是说,把链表的next关系反向了。

再看看这几个while中可能在四线程处境下引起难点的语句。针对七个线程t一和t贰,那里它们只怕的产生难题的实践连串做些个人分析:

1)假使同三个Entry列表[e->f->…],t一先到,t二后到并都走到while中。t一推行“e.next
= newTable[i];newTable[i] =
e;”这使得e.next=null(初始的newTable[i]为null),newTable[i]指向了e。这时t2执行了“e.next
= newTable[i];newTable[i] =
e;”,那使得e.next=e,e死循环了。因为循环发轫处的“final Entrynext =
e.next;”,固然e自个儿死循环了,在最终的“e =
next;”后,多少个线程都会跳过e继续执行下去。

2)在while中各个遍历Entry链表中的Entry而把next关系反向时,newTable[i]成为了被换来的引用,嫌疑的口舌在于
“e.next =
newTable[i];”。假使链表e->f->g被t一拍卖成eg,造成了死循环。所以,理论上的话,死循环的Entry个数大概很多。
就算产生了死循环,但是t一执行到了死循环的右手,所以是会继续执行下去的,而t2借使履行“final
Entrynext =
e.next;”的next为null,则也会继续执行下去,不然就进去了死循环。

叁)就像是状态会更复杂,因为即便线程跳出了死循环,它下二次做resize进入transfer时,有不小希望因为事先的死循环Entry链表而被
hang住(仿佛是早晚会被hang住)。也有相当大希望,在put检查Entry链表时(@标记1),因为Entry链表的死循环而被hang住。也就像有大概,活着的线程和死循环的线程同时执行在while里后,多少个线程都能活着出来。所以,恐怕七个线程平安退出,大概一个线程hang在transfer
中,大概五个线程都被hang住而又不必然在3个地方。

4)笔者数十次的测试,出现二个线程被hang住的景况最多,都是e=e.next.next造成的,那首要正是例证put两份增量数据造成的。小编只要
去掉@标记三的出口,有时也能复现四个线程都被hang住的动静,但丰裕后就很难复现出来。小编又把put的多寡改了下,比如让五个线程put范围不1的数
据,就能复现出e=e.next,五个线程都被hang住的意况。

地点罗哩罗嗦了广大,一开首本身不难的分析后认为就如知道了怎么回事,可近来精心钻探后仿佛又不明白了累累。有1个细节是,每一次死循环的key的大小
也是有据可循的,作者就不打哈了。感觉,假设样本多些,可能出现问题的因由点会很多,也会更复杂,作者姑且不再蛋疼下去。至于有人提到
ConcurrentHashMap也有其①标题,小编认为十分的小恐怕,因为它的put操作是加锁的,如若有其一题材就不叫线程安全的Map了。

原稿链接: http://www.udpwork.com/redirect/2321

一、HashMap是非线程安全的,HashTable是线程安全的。

2、HashMap的键和值都允许有null值存在,而HashTable则丰盛。

三、因为线程安全的题目,HashMap功效比HashTable的要高。

能答出上边的3点,简单的面试,算是过了,可是借使再问:Java中的另1个线程安全的与HashMap极其类似的类是如何?同样是线程安全,它与HashTable在线程同步上有啥两样?能把第一个难点总体的答出来,表明你的基本功算是不错的了。带着那些题材,本章起头系Java之美[从菜鸟到高手衍变]系列之深远解析HashMap和HashTable类应用而生!总想在篇章的始发说简单什么,但又无从谈起。从近来的壹对面试谈到啊,感受就是:知识是永无穷境的,永远不要认为自个儿早已控制了一点事物。即使对哪壹块知识感兴趣,那么,请多多的花时间,哪怕最基础的事物也要知道它的规律,尽量往深了商讨,在就学的同时,记得多与大家交换联络,因为或然有个别事物,从您协调的角度,是很难发现的,因为您并不曾那么多的试行环境去发现他们。唯有调换的多了,才能立刻找出本身的欠缺,才能认得到:“哦,原来自家还有这么多不知底的东西!”。


一、HashMap的内部存款和储蓄结构 
Java中数量存款和储蓄方式最尾部的两种结构,1种是数组,另1种正是链表,数组的表征:接二连三空间,寻址飞快,可是在剔除大概添美成分的时候须要有较大幅度面包车型客车移动,所以查询速度快,增加和删除较慢。而链表正好相反,由于空间不延续,寻址困难,增加和删除成分只需修改指针,所以查询慢、增加和删除快。有未有1种数据结构来归纳一下数组和链表,以便发挥她们各自的优势?答案是必然的!就是:哈希表。哈希表具有较快(常量级)的询问速度,及相对较快的增删速度,所以很符合在海量数据的环境中央银行使。1般达成哈希表的不二诀窍运用“拉链法”,大家能够领略为“链表的数组”,如下图:

图片 1

从上海教室中,大家得以窥见哈希表是由数组+链表组成的,三个长短为1六的数组中,每一种元素存款和储蓄的是2个链表的头结点。那么那个要素是遵守什么的平整存款和储蓄到数组中吗。一般景观是经过hash(key)%len获得,也正是因素的key的哈希值对数经理度取模获得。比如上述哈希表中,12%16=1二,2八%16=1二,拾捌%16=1二,1五分二1陆=1贰。所以1二、2八、拾八以及140都存款和储蓄在数组下标为1二的地点。它的里边其实是用二个Entity数组来达成的,属性有key、value、next。接下来作者会从开头化阶段详细的讲解HashMap的内部结构。

1、初始化  首先来看多少个常量: 
static final int DEFAULT_INITIAL_CAPACITY = 1陆; 开始体量:16 
static final int MAXIMUM_CAPACITY = 1  
<< 30; 最大体量:二的31遍方:十737418二肆 
static final float DEFAULT_LOAD_FACTOR = 0.75f;  
装载因子,前面再说它的功用 
来看个无参构造方法,也是我们最常用的:

[java] view
plain
 copy

  1. public HashMap() {  
  2.         this.loadFactor = DEFAULT_LOAD_FACTOR;  
  3.         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);  
  4.         table = new Entry[DEFAULT_INITIAL_CAPACITY];  
  5.         init();  
  6.     }  

loadFactor、threshold的值在那里未有起到功用,可是他们在前面包车型客车扩大体量方面会用到,此处只需清楚table=new
Entry[DEFAULT_INITIAL_CAPACITY].表达,私下认可正是开辟十五个大大小小的空中。别的一个重中之重的构造方法:

[java] view
plain
 copy

  1. public HashMap(int initialCapacity, float loadFactor) {  
  2.         if (initialCapacity < 0)  
  3.             throw new IllegalArgumentException(“Illegal initial capacity: ” +  
  4.                                                initialCapacity);  
  5.         if (initialCapacity > MAXIMUM_CAPACITY)  
  6.             initialCapacity = MAXIMUM_CAPACITY;  
  7.         if (loadFactor <= 0 || Float.isNaN(loadFactor))  
  8.             throw new IllegalArgumentException(“Illegal load factor: ” +  
  9.                                                loadFactor);  
  10.   
  11.         // Find a power of 2 >= initialCapacity  
  12.         int capacity = 1;  
  13.         while (capacity < initialCapacity)  
  14.             capacity <<= 1;  
  15.   
  16.         this.loadFactor = loadFactor;  
  17.         threshold = (int)(capacity * loadFactor);  
  18.         table = new Entry[capacity];  
  19.         init();  
  20.     }  

说是传入参数的构造方法,大家把第二放在:

[java] view
plain
 copy

  1. while (capacity < initialCapacity)  
  2.            capacity <<= 1;  

地方,该代码的情致是,实际的开拓的上空要压倒传入的率先个参数的值。举个例子:
new
HashMap(七,0.8),loadFactor为0.八,capacity为七,通过上述代码后,capacity的值为:8.(一<< 二的结果是4,2 << 二的结果为八<此处谢谢网上朋友wego123四的指正>)。所以,最后capacity的值为八,最终通过new
Entry[capacity]来创设大小为capacity的数组,所以,那种办法最红取决于capacity的尺寸。
2、put(Object
key,Object value)操作
 
当调用put操作时,首先判断key是或不是为null,如下代码1处:

[java] view
plain
 copy

  1. <p>public V put(K key, V value) {  
  2.         if (key == null)  
  3.             return putForNullKey(value);  
  4.         int hash = hash(key.hashCode());  
  5.         int i = indexFor(hash, table.length);  
  6.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
  7.             Object k;  
  8.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
  9.                 V oldValue = e.value;  
  10.                 e.value = value;  
  11.                 e.recordAccess(this);  
  12.                 return oldValue;  
  13.             }  
  14.         }</p><p>        modCount++;  
  15.         addEntry(hash, key, value, i);  
  16.         return null;  
  17.     }</p>  

如果key是null,则调用如下代码:

[java] view
plain
 copy

  1. private V putForNullKey(V value) {  
  2.         for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
  3.             if (e.key == null) {  
  4.                 V oldValue = e.value;  
  5.                 e.value = value;  
  6.                 e.recordAccess(this);  
  7.                 return oldValue;  
  8.             }  
  9.         }  
  10.         modCount++;  
  11.         addEntry(0, null, value, 0);  
  12.         return null;  
  13.     }  

实属,获取Entry的第一个元素table[0],并依据第2个成分的next属性开端遍历,直到找到key为null的Entry,将其value设置为新的value值。
只要没有找到key为null的因素,则调用如上述代码的addEntry(0, null, value,
0);扩大一个新的entry,代码如下:

[java] view
plain
 copy

  1. void addEntry(int hash, K key, V value, int bucketIndex) {  
  2.     Entry<K,V> e = table[bucketIndex];  
  3.         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
  4.         if (size++ >= threshold)  
  5.             resize(2 * table.length);  
  6.     }  

先取得第二个成分table[bucketIndex],传给e对象,新建二个entry,key为null,value为传入的value值,next为取得的e对象。假若体量当先threshold,容积扩充2倍。
如果key不为null,那也是多数的状态,重新看一下源码:

[java] view
plain
 copy

  1. public V put(K key, V value) {  
  2.         if (key == null)  
  3.             return putForNullKey(value);  
  4.         int hash = hash(key.hashCode());//—————2—————  
  5.         int i = indexFor(hash, table.length);  
  6.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {//————–3———–  
  7.             Object k;  
  8.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
  9.                 V oldValue = e.value;  
  10.                 e.value = value;  
  11.                 e.recordAccess(this);  
  12.                 return oldValue;  
  13.             }  
  14.         }//——————-4——————  
  15.         modCount++;//—————-5———-  
  16.         addEntry(hash, key, value, i);————-6———–  
  17.         return null;  
  18.     }  

看源码中2处,首先会实行key.hashCode()操作,获取key的哈希值,hashCode()是Object类的二个方法,为本地点法,内部贯彻比较复杂,大家
会在末端作单独的关于Java中Native方法的剖析中牵线。hash()的源码如下:

[java] view
plain
 copy

  1. static int hash(int h) {  
  2.         // This function ensures that hashCodes that differ only by  
  3.         // constant multiples at each bit position have a bounded  
  4.         // number of collisions (approximately 8 at default load factor).  
  5.         h ^= (h >>> 20) ^ (h >>> 12);  
  6.         return h ^ (h >>> 7) ^ (h >>> 4);  
  7.     }  

int i =
indexFor(hash, table.length);的意思,相当于int i = hash
% Entry[].length;获得i后,正是在Entry数组中的地方,(上述代码5和6处是如果Entry数组中不存在新要增加的元素,则执行5,6处的代码,如果存在,即Hash冲突,则执行 3-4处的代码,此处HashMap中采用链地址法解决Hash冲突。此处经网上朋友bbycszh指正,发现上述陈述有些标题)。重新解释:其实不管Entry数组中i地点有无成分,都会去执行5-陆处的代码,如若未有,则直接增加产量,假设有,则将新元素设置为Entry[0],其next指针指向原有对象,即原有对象为Entry[1]。具体方法能够分解为上面包车型客车那段文字:(三-四处的代码只是检查在索引为i的那条链上有未有key重复的,有则替换且重返原值,程序不再去实施伍-6处的代码,无则无处理

上边我们关系过Entry类里面有2个next属性,成效是指向下八个Entry。如,
第1个键值对A进来,通过总结其key的hash获得的i=0,记做:Entry[0] =
A。1会后又进入多个键值对B,通过计算其i也就是0,以后怎么做?HashMap会那样做:B.next
= A,Entry[0] = B,即便又进来C,i约等于0,那么C.next = B,Entry[0] =
C;那样大家发现i=0的地点实际存取了A,B,C八个键值对,他们通过next那本性子链接在联合署名,也正是说数组中蕴藏的是终极插入的元素。

到此处甘休,HashMap的光景落成,咱们应有已经知道了。当然HashMap里面也富含部分优化方面包车型客车贯彻,那里也说一下。比如:Entry[]的长度一定后,随着map里面数据的更是长,那样同四个i的链就会十分短,会不会影响属性?HashMap里面设置贰个因素(也称为因子),随着map的size更加大,Entry[]会以自然的平整加长长度。

2、get(Object key)操作
get(Object
key)操作时依据键来获取值,如若精通了put操作,get操作简单领会,先来探视源码的贯彻:

[java] view
plain
 copy

  1. public V get(Object key) {  
  2.         if (key == null)  
  3.             return getForNullKey();  
  4.         int hash = hash(key.hashCode());  
  5.         for (Entry<K,V> e = table[indexFor(hash, table.length)];  
  6.              e != null;  
  7.              e = e.next) {  
  8.             Object k;  
  9.             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))//——————-1—————-  
  10.                 return e.value;  
  11.         }  
  12.         return null;  
  13.     }  

意思正是:1、当key为null时,调用getForNullKey(),源码如下:

[java] view
plain
 copy

  1. private V getForNullKey() {  
  2.         for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
  3.             if (e.key == null)  
  4.                 return e.value;  
  5.         }  
  6.         return null;  
  7.     }  

二、当key不为null时,先依据hash函数获得hash值,在更具indexFor()获得i的值,循环遍历链表,如若有:key值等于已存在的key值,则赶回其value。如上述get()代码1处判断。

总结下HashMap新增put和获取get操作:

[java] view
plain
 copy

  1. //存储时:  
  2. int hash = key.hashCode();  
  3. int i = hash % Entry[].length;  
  4. Entry[i] = value;  
  5.   
  6. //取值时:  
  7. int hash = key.hashCode();  
  8. int i = hash % Entry[].length;  
  9. return Entry[i];  

明亮了就相比较简单。

那边附2个回顾的HashMap小算法应用:

[java] view
plain
 copy

  1. package com.xtfggef.hashmap;  
  2.   
  3. import java.util.HashMap;  
  4. import java.util.Map;  
  5. import java.util.Set;  
  6.   
  7. /** 
  8.  * 打字与印刷在数组中冒出n/二以上的因素 
  9.  * 利用多少个HashMap来存放数组成分及出现的次数 
  10.  * @author erqing 
  11.  * 
  12.  */  
  13. public class HashMapTest {  
  14.       
  15.     public static void main(String[] args) {  
  16.           
  17.         int [] a = {2,3,2,2,1,4,2,2,2,7,9,6,2,2,3,1,0};  
  18.           
  19.         Map<Integer, Integer> map = new HashMap<Integer,Integer>();  
  20.         for(int i=0; i<a.length; i++){  
  21.             if(map.containsKey(a[i])){  
  22.                 int tmp = map.get(a[i]);  
  23.                 tmp+=1;  
  24.                 map.put(a[i], tmp);  
  25.             }else{  
  26.                 map.put(a[i], 1);  
  27.             }  
  28.         }  
  29.         Set<Integer> set = map.keySet();//————1————  
  30.         for (Integer s : set) {  
  31.             if(map.get(s)>=a.length/2){  
  32.                 System.out.println(s);  
  33.             }  
  34.         }//————–2—————  
  35.     }  
  36. }  

那里注意四个地点,map.containsKey(),还有正是上述一-二处的代码。

领悟了HashMap的方面包车型客车操作,别的的多数艺术都很简单驾驭了。搞明白它的内部存款和储蓄机制,一切OK!

2、HashTable的里边存款和储蓄结构

HashTable和HashMap选择同样的储存机制,二者的兑现基本一致,区别的是:

壹、HashMap是非线程安全的,HashTable是线程安全的,内部的法子基本都是synchronized。

2、HashTable不允许有null值的存在。

在HashTable中调用put方法时,借使key为null,直接抛出NullPointerException。别的细微的距离还有,比如起先化Entry数组的尺寸等等,但基本思维和HashMap一样。

三、HashTable和ConcurrentHashMap的比较

如作者开篇所说一样,ConcurrentHashMap是线程安全的HashMap的贯彻。同样是线程安全的类,它与HashTable在一块儿方面有怎样分歧呢?

前边咱们说,synchronized关键字加锁的法则,其实是对目的加锁,不论你是在章程前加synchronized仍旧语句块前加,锁住的都是目的全部,但是ConcurrentHashMap的壹道机制和这些区别,它不是加synchronized关键字,而是基于lock操作的,那样的指标是确认保证同步的时候,锁住的不是全方位对象。事实上,ConcurrentHashMap能够满意concurrentLevel个线程并发无阻塞的操作集合对象。关于concurrentLevel稍后介绍。

一、构造方法

为了不难掌握,大家先从构造函数谈到。ConcurrentHashMap是基于贰个叫Segment数组的,其实和Entry类似,如下:

[java] view
plain
 copy

  1. public ConcurrentHashMap()  
  2.   {  
  3.     this(16, 0.75F, 16);  
  4.   }  

默许传入值1陆,调用上面包车型的士格局:

[java] view
plain
 copy

  1. public ConcurrentHashMap(int paramInt1, float paramFloat, int paramInt2)  
  2.   {  
  3.     if ((paramFloat <= 0F) || (paramInt1 < 0) || (paramInt2 <= 0))  
  4.       throw new IllegalArgumentException();  
  5.   
  6.     if (paramInt2 > 65536) {  
  7.       paramInt2 = 65536;  
  8.     }  
  9.   
  10.     int i = 0;  
  11.     int j = 1;  
  12.     while (j < paramInt2) {  
  13.       ++i;  
  14.       j <<= 1;  
  15.     }  
  16.     this.segmentShift = (32 – i);  
  17.     this.segmentMask = (j – 1);  
  18.     this.segments = Segment.newArray(j);  
  19.   
  20.     if (paramInt1 > 1073741824)  
  21.       paramInt1 = 1073741824;  
  22.     int k = paramInt1 / j;  
  23.     if (k * j < paramInt1)  
  24.       ++k;  
  25.     int l = 1;  
  26.     while (l < k)  
  27.       l <<= 1;  
  28.   
  29.     for (int i1 = 0; i1 < this.segments.length; ++i1)  
  30.       this.segments[i1] = new Segment(l, paramFloat);  
  31.   }  

您会发现比HashMap的构造函数多三个参数,paramInt1正是大家事先谈过的initialCapacity,正是数组的发轫化大小,paramfloat为loadFactor(装载因子),而paramInt二则是大家所要说的concurrentLevel,那多少个值分别被开头化为1陆,0.75,1陆,经过:

[java] view
plain
 copy

  1. while (j < paramInt2) {  
  2.       ++i;  
  3.       j <<= 1;  
  4.     }  

后,j正是我们最后要开辟的数组的size值,当paramInt一为1陆时,计算出来的size值就是16.经过:

this.segments =
Segment.newArray(j)后,大家看出了,最后稿成立的Segment数组的大小为1陆.终极创建Segment对象时:

[java] view
plain
 copy

  1. this.segments[i1] = new Segment(cap, paramFloat);  

内需cap值,而cap值来源于:

[java] view
plain
 copy

  1. int k = paramInt1 / j;  
  2.   if (k * j < paramInt1)  
  3.     ++k;  
  4.   int cap = 1;  
  5.   while (cap < k)  
  6.     cap <<= 1;  

组后创办大小为cap的数组。最终依照数组的高低及paramFloat的值算出了threshold的值:

this.threshold =
(int)(paramArrayOfHashEntry.length * this.loadFactor)。

2、put操作

[java] view
plain
 copy

  1. public V put(K paramK, V paramV)  
  2.   {  
  3.     if (paramV == null)  
  4.       throw new NullPointerException();  
  5.     int i = hash(paramK.hashCode());  
  6.     return segmentFor(i).put(paramK, i, paramV, false);  
  7.   }  

与HashMap不一致的是,固然key为null,直接抛出NullPointer卓殊,之后,同样先计算hashCode的值,再总计hash值,可是那里hash函数和HashMap中的不1样:

[java] view
plain
 copy

  1. private static int hash(int paramInt)  
  2.   {  
  3.     paramInt += (paramInt << 15 ^ 0xFFFFCD7D);  
  4.     paramInt ^= paramInt >>> 10;  
  5.     paramInt += (paramInt << 3);  
  6.     paramInt ^= paramInt >>> 6;  
  7.     paramInt += (paramInt << 2) + (paramInt << 14);  
  8.     return (paramInt ^ paramInt >>> 16);  
  9.   }  

 

[java] view
plain
 copy

  1. final Segment<K, V> segmentFor(int paramInt)  
  2.   {  
  3.     return this.segments[(paramInt >>> this.segmentShift & this.segmentMask)];  
  4.   }  

依照上述代码找到Segment对象后,调用put来操作:

[java] view
plain
 copy

  1. V put(K paramK, int paramInt, V paramV, boolean paramBoolean)  
  2. {  
  3.   lock();  
  4.   try {  
  5.     Object localObject1;  
  6.     Object localObject2;  
  7.     int i = this.count;  
  8.     if (i++ > this.threshold)  
  9.       rehash();  
  10.     ConcurrentHashMap.HashEntry[] arrayOfHashEntry = this.table;  
  11.     int j = paramInt & arrayOfHashEntry.length – 1;  
  12.     ConcurrentHashMap.HashEntry localHashEntry1 = arrayOfHashEntry[j];  
  13.     ConcurrentHashMap.HashEntry localHashEntry2 = localHashEntry1;  
  14.     while ((localHashEntry2 != null) && (((localHashEntry2.hash != paramInt) || (!(paramK.equals(localHashEntry2.key)))))) {  
  15.       localHashEntry2 = localHashEntry2.next;  
  16.     }  
  17.   
  18.     if (localHashEntry2 != null) {  
  19.       localObject1 = localHashEntry2.value;  
  20.       if (!(paramBoolean))  
  21.         localHashEntry2.value = paramV;  
  22.     }  
  23.     else {  
  24.       localObject1 = null;  
  25.       this.modCount += 1;  
  26.       arrayOfHashEntry[j] = new ConcurrentHashMap.HashEntry(paramK, paramInt, localHashEntry1, paramV);  
  27.       this.count = i;  
  28.     }  
  29.     return localObject1;  
  30.   } finally {  
  31.     unlock();  
  32.   }  
  33. }  

先调用lock(),lock是ReentrantLock类的二个办法,用当下囤积的个数+1来和threshold比较,假诺过量threshold,则展开rehash,将日前的体积扩张二倍,重新进行hash。之后对hash的值和数组大小-一进展按位于操作后,得到当前的key供给放入的职责,从这时初叶,和HashMap1样。

从上述的解析看来,ConcurrentHashMap基于concurrentLevel划分出了多少个Segment来对key-value进行仓库储存,从而制止每一遍锁定任何数组,在暗中同意的场馆下,允许14个线程并发无阻塞的操作集合对象,尽可能地回落并发时的封堵现象。

在四线程的环境中,相对于HashTable,ConcurrentHashMap会带来十分的大的属性提高!

欢迎读者批评指正,有此外提议请联系:

EGG:xtfggef@gmail.com     
http://weibo.com/xtfggef

四、HashMap常见难题分析

壹、此处小编觉得网友huxb23@126的一篇小说说的很好,浅析八线程并发写HashMap线程被hang住的缘由 ,因为是了不起的能源,此处笔者整理下搬到此刻。

以下内容转自博文:http://blog.163.com/huxb23@126/blog/static/625898182011211318854/ 

先看原难点代码:

[java] view
plain
 copy

  1. import java.util.HashMap;  
  2.   
  3. public class TestLock {  
  4.   
  5.     private HashMap map = new HashMap();  
  6.   
  7.     public TestLock() {  
  8.         Thread t1 = new Thread() {  
  9.             public void run() {  
  10.                 for (int i = 0; i < 50000; i++) {  
  11.                     map.put(new Integer(i), i);  
  12.                 }  
  13.                 System.out.println(“t1 over”);  
  14.             }  
  15.         };  
  16.   
  17.         Thread t2 = new Thread() {  
  18.             public void run() {  
  19.                 for (int i = 0; i < 50000; i++) {  
  20.                     map.put(new Integer(i), i);  
  21.                 }  
  22.   
  23.                 System.out.println(“t2 over”);  
  24.             }  
  25.         };  
  26.   
  27.         t1.start();  
  28.         t2.start();  
  29.   
  30.     }  
  31.   
  32.     public static void main(String[] args) {  
  33.         new TestLock();  
  34.     }  
  35. }  

正是启了多个线程,不断的往四个非线程安全的HashMap中put内容,put的内容很简单,key和value都以从0自增的平头(那个put的情节做的并不佳,以致于后来困扰了本身分析难点的思路)。对HashMap做并发写操作,作者原以为只但是会时有产生脏数据的事态,但屡次运营这几个顺序,汇合世线程t1、t二被hang住的状态,多数意况下是2个线程被hang住另二个打响结束,偶尔会三个线程都被hang住。提及此地,你1旦认为倒霉好学习ConcurrentHashMap而在那瞎折腾就手下留情跳过吗。
可以吗,分析下HashMap的put函数源码看看难题出在哪,那里就位列出相关代码(jdk壹.6):

[java] view
plain
 copy

  1. public V put(K paramK, V paramV)  
  2. {  
  3.   if (paramK == null)  
  4.     return putForNullKey(paramV);  
  5.   int i = hash(paramK.hashCode());  
  6.   int j = indexFor(i, this.table.length);  
  7.   for (Entry localEntry = this.table[j]; localEntry != null; localEntry = localEntry.next)  
  8.   {  
  9.     if (localEntry.hash == i) { java.lang.Object localObject1;  
  10.       if (((localObject1 = localEntry.key) == paramK) || (paramK.equals(localObject1))) {  
  11.         java.lang.Object localObject2 = localEntry.value;  
  12.         localEntry.value = paramV;  
  13.         localEntry.recordAccess(this);  
  14.         return localObject2;  
  15.       }  
  16.     }  
  17.   }  
  18.   this.modCount += 1;  
  19.   addEntry(i, paramK, paramV, j);  
  20.   return null;  
  21. }  
  22.   
  23. private V putForNullKey(V paramV)  
  24. {  
  25.   for (Entry localEntry = this.table[0]; localEntry != null; localEntry = localEntry.next)  
  26.     if (localEntry.key == null) {  
  27.       java.lang.Object localObject = localEntry.value;  
  28.       localEntry.value = paramV;  
  29.       localEntry.recordAccess(this);  
  30.       return localObject;  
  31.     }  
  32.   
  33.   this.modCount += 1;  
  34.   addEntry(0, null, paramV, 0);  
  35.   return null;  
  36. }  

 

通过jconsole(恐怕thread
dump),能够看出线程停在了transfer方法的while循环处。那些transfer方法的效果是,当Map凉月素数超越阈值需求resize时,它担负把原Map中的元素映射到新Map中。作者修改了HashMap,加上了@标记二和@标记三的代码片断,以打字与印刷出死循环时的图景,结果死循环线程总是出现就如那样的输出:“Thread-壹,e==next:false,e==next.next:true,e:10892八=十8928,next:十8928=十892八,eq:true”。
本条输出注脚:
一)那一个Entry链中的多个Entry之间的关系是:e=e.next.next,造成死循环。
2)e.equals(e.next),但e!=e.next。因为测试例子中三个线程put的始末同样,并发时大概同二个key被保存了多个value,那种错误是在addEntry函数产生的,但那和线程死循环未有涉嫌。

接下去就分析transfer中拾叁分while循环了。先所说这一个轮回不荒谬的作用:src[j]封存的是炫耀成同1个hash值的五个Entry的链表,那一个src[j]也许为null,大概唯有1个Entry,也恐怕由多个Entry链接起来。即便是多少个Entry,原来的链是(src[j]=a)->b(也就是src[j]=a,a.next=b,b.next=null),经过while处理后收获了(newTable[i]=b)->a。约等于说,把链表的next关系反向了。

再看看这么些while中恐怕在四线程情形下引起难点的说话。针对七个线程t一和t2,那里它们或许的产生难题的施行类别做些个人分析:

1)如若同三个Entry列表[e->f->…],t一先到,t贰后到并都走到while中。t1推行“e.next
= newTable[i];newTable[i] =
e;”这使得e.next=null(初始的newTable[i]为null),newTable[i]指向了e。这时t2执行了“e.next
= newTable[i];newTable[i] =
e;”,那使得e.next=e,e死循环了。因为循环开端处的“final Entry next =
e.next;”,固然e自身死循环了,在最终的“e =
next;”后,五个线程都会跳过e继续执行下去。

2)在while中每种遍历Entry链表中的Entry而把next关系反向时,newTable[i]成为了被换到的引用,疑惑的说话在于“e.next

newTable[i];”。要是链表e->f->g被t1拍卖成e<-f<-g,newTable[i]针对了g,那时t2进来了,它一执行“e.next

newTable[i];”就使得e->g,造成了死循环。所以,理论上来说,死循环的Entry个数恐怕很多。就算爆发了死循环,可是t壹执行到了死循环的出手,所以是会继续执行下去的,而t二要是推行“final
Entry next =
e.next;”的next为null,则也会继续执行下去,不然就进来了死循环。

三)就像状态会更扑朔迷离,因为即便线程跳出了死循环,它下3遍做resize进入transfer时,有不小可能率因为事先的死循环Entry链表而被hang住(如同是自但是然会被hang住)。也有希望,在put检查Entry链表时(@标记一),因为Entry链表的死循环而被hang住。也似乎有一点都不小可能率,活着的线程和死循环的线程同时履行在while里后,七个线程都能活着出去。所以,可能四个线程平安退出,或者三个线程hang在transfer中,或者七个线程都被hang住而又不自然在二个地点。

四)笔者数十次的测试,出现1个线程被hang住的场合最多,都以e=e.next.next造成的,那重大正是例证put两份增量数据造成的。我只要去掉@标记三的输出,有时也能复现八个线程都被hang住的图景,但丰盛后就很难复现出来。小编又把put的数量改了下,比如让三个线程put范围不一的数目,就能复现出e=e.next,八个线程都被hang住的景况。

上边罗哩罗嗦了不可计数,一起初自个儿回顾的辨析后以为仿佛知道了怎么回事,可后天细心雕刻后就如又不知底了过多。有多少个细节是,每一遍死循环的key的高低也是有据可循的,我就不打哈了。感觉,假设样本多些,只怕出现难题的原因点会很多,也会更复杂,作者姑且不再蛋疼下去。至于有人提到ConcurrentHashMap也有这些难题,作者认为非常小恐怕,因为它的put操作是加锁的,假若有其壹题材就不叫线程安全的Map了。

贰、HashMap中Value能够1如既往,但是键不得以等效

当插入HashMap的key相同时,会覆盖原有的Value,且重返原Value值,看下边包车型大巴次第:

[java] view
plain
 copy

  1. public class Test {  
  2.   
  3.     public static void main(String[] args) {  
  4.           
  5.         HashMap<String,Integer> map = new HashMap<String,Integer>();  
  6.   
  7.         //出入多个Value相同的值,没有毛病  
  8.         map.put(“egg”, 1);  
  9.         map.put(“niu”, 1);  
  10.           
  11.         //插入key相同的值,看重临结果  
  12.         int egg = (Integer) map.put(“egg”, 3);  
  13.           
  14.         System.out.println(egg);   //输出1  
  15.         System.out.println(map.get(“egg”));   //输出3,将原值1覆盖  
  16.         System.out.println(map.get(“niu”));   //输出1  
  17.     }  
  18. }  

没有差别于的键会被遮住,且再次来到原值。

三、HashMap按值排序

给定贰个数组,求出各样数据出现的次数并依据次数的由大到小排列出来。我们选取HashMap来做,key存款和储蓄数组元素,值存款和储蓄出现的次数,最后用Collections的sort方法对HashMap的值实行排序。代码如下:

[java] view
plain
 copy

  1. public class Test {  
  2.   
  3.     public static void main(String[] args) {  
  4.   
  5.         int data[] = { 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2,  
  6.                 7, 8, 8, 7, 8, 7, 9, 0 };  
  7.         Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
  8.         for (int i : data) {  
  9.             if (map.containsKey(i)) {//判断HashMap里是或不是留存  
  10.                 map.put(i, map.get(i) + 1);//已存在,值+1  
  11.             } else {  
  12.                 map.put(i, 1);//不存在,新增  
  13.             }  
  14.         }  
  15.         //map按值排序  
  16.         List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(  
  17.                 map.entrySet());  
  18.         Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {  
  19.             public int compare(Map.Entry<Integer, Integer> o1,  
  20.                     Map.Entry<Integer, Integer> o2) {  
  21.                 return (o2.getValue() – o1.getValue());  
  22.             }  
  23.         });  
  24.         for (Map.Entry<Integer, Integer> m : list) {  
  25.             System.out.println(m.getKey() + “-” + m.getValue());  
  26.         }  
  27.     }  
  28.   
  29. }  

输出:

2-6
5-5
3-4
8-3
7-3
9-1
0-1

  1. public HashMap()
  2.         this.loadFactor =
    DEFAULT_LOAD_FACTOR; 
  3.        
    threshold = (int)(DEFAULT_INITIAL_CAPACITY *
    DEFAULT_LOAD_FACTOR); 
  4.        
    table = new Entry[DEFAULT_INITIAL_CAPACITY]; 
  5.        
    init(); 
  6.    

loadFactor、threshold的值在那边未有起到效益,可是他俩在后头的扩大体积方面会用到,此处只需通晓table=new
Entry[DEFAULT_INITIAL_CAPACITY].表达,暗许正是开拓拾陆个大小的空间。别的3个重点的构造方法:

[java] view
plain
 copy

  1. public HashMap(int initialCapacity, float loadFactor)
  2.         if (initialCapacity
    < 0) 
  3.             throw new IllegalArgumentException(“Illegal
    initial capacity: ” + 
  4.                                               
    initialCapacity); 
  5.         if (initialCapacity >
    MAXIMUM_CAPACITY) 
  6.            
    initialCapacity = MAXIMUM_CAPACITY; 
  7.         if (loadFactor
    <= 0 ||
    Float.isNaN(loadFactor)) 
  8.             throw new IllegalArgumentException(“Illegal
    load factor: ” + 
  9.                                               
    loadFactor); 
  10.  
  11.         //
    Find a power of 2 >= initialCapacity 
  12.         int capacity
    = 1; 
  13.         while (capacity
    < initialCapacity) 
  14.            
    capacity <<= 1; 
  15.  
  16.         this.loadFactor
    = loadFactor; 
  17.        
    threshold = (int)(capacity *
    loadFactor); 
  18.        
    table = new Entry[capacity]; 
  19.        
    init(); 
  20.    

实属传入参数的构造方法,我们把首要放在:

[java] view
plain
 copy

  1. while (capacity
    < initialCapacity) 
  2.           
    capacity <<= 1; 

上面,该代码的意味是,实际的开发的半空中要高于传入的第二个参数的值。举个例子: 
new
HashMap(七,0.8),loadFactor为0.八,capacity为七,通过上述代码后,capacity的值为:八.(一<< 二的结果是四,二 << 二的结果为八<此处谢谢网络朋友wego123四的指正>)。所以,最后capacity的值为八,最终经过new
Entry[capacity]来创设大小为capacity的数组,所以,那种艺术最红取决于capacity的深浅。 
2、put(Object
key,Object value)操作 
  
当调用put操作时,首先判断key是不是为null,如下代码①处:

[java] view
plain
 copy

  1. <p>public V
    put(K key, V value) { 
  2.         if (key
    == null) 
  3.             return putForNullKey(value); 
  4.         int hash
    = hash(key.hashCode()); 
  5.         int i
    = indexFor(hash, table.length); 
  6.         for (Entry<K,V>
    e = table[i]; e != null;
    e = e.next) { 
  7.            
    Object k; 
  8.             if (e.hash
    == hash && ((k = e.key) == key || key.equals(k))) { 
  9.                
    V oldValue = e.value; 
  10.                
    e.value = value; 
  11.                
    e.recordAccess(this); 
  12.                 return oldValue; 
  13.            
  14.        
    }</p><p>        modCount++; 
  15.        
    addEntry(hash, key, value, i); 
  16.         return null; 
  17.    
    }</p> 

如果key是null,则调用如下代码:

[java] view
plain
 copy

  1. private V
    putForNullKey(V value) { 
  2.         for (Entry<K,V>
    e = table[0];
    e != null;
    e = e.next) { 
  3.             if (e.key
    == null)
  4.                
    V oldValue = e.value; 
  5.                
    e.value = value; 
  6.                
    e.recordAccess(this); 
  7.                 return oldValue; 
  8.            
  9.        
  10.        
    modCount++; 
  11.        
    addEntry(0, null,
    value, 0); 
  12.         return null; 
  13.    

便是说,获取Entry的首先个因素table[0],并依据第二个因素的next属性初步遍历,直到找到key为null的Entry,将其value设置为新的value值。 
假设未有找到key为null的成分,则调用如上述代码的addEntry(0, null, value,
0);扩展八个新的entry,代码如下:

[java] view
plain
 copy

  1. void addEntry(int hash,
    K key, V value, int bucketIndex)
  2.    
    Entry<K,V> e = table[bucketIndex]; 
  3.        
    table[bucketIndex] = new Entry<K,V>(hash,
    key, value, e); 
  4.         if (size++ >=
    threshold) 
  5.            
    resize(2 *
    table.length); 
  6.    

先得到第玖个因素table[bucketIndex],传给e对象,新建一个entry,key为null,value为传入的value值,next为获得的e对象。若是体量超越threshold,容积扩大2倍。 
如果key不为null,那也是超越4/8的图景,重新看一下源码:

[java] view
plain
 copy

  1. public V
    put(K key, V value) { 
  2.         if (key
    == null) 
  3.             return putForNullKey(value); 
  4.         int hash
    = hash(key.hashCode());//—————2————— 
  5.         int i
    = indexFor(hash, table.length); 
  6.         for (Entry<K,V>
    e = table[i]; e != null;
    e = e.next) {//————–3———– 
  7.            
    Object k; 
  8.             if (e.hash
    == hash && ((k = e.key) == key || key.equals(k))) { 
  9.                
    V oldValue = e.value; 
  10.                
    e.value = value; 
  11.                
    e.recordAccess(this); 
  12.                 return oldValue; 
  13.            
  14.        
    }//——————-4—————— 
  15.        
    modCount++;//—————-5———- 
  16.        
    addEntry(hash, key, value, i);————-6———– 
  17.         return null; 
  18.    

看源码中二处,首先会进展key.hashCode()操作,获取key的哈希值,hashCode()是Object类的三个艺术,为本地点法,内部贯彻相比较复杂,我们 
会在后边作单独的有关Java中Native方法的解析中牵线。hash()的源码如下:

[java] view
plain
 copy

  1. static int hash(int h)
  2.         //
    This function ensures that hashCodes that differ only by 
  3.         //
    constant multiples at each bit position have a bounded 
  4.         //
    number of collisions (approximately 8 at default load
    factor). 
  5.        
    h ^= (h >>> 20)
    ^ (h >>> 12); 
  6.         return h
    ^ (h >>> 7)
    ^ (h >>> 4); 
  7.    

int i =
indexFor(hash, table.length);的意思,相当于int i = hash
% Entry[].length;获得i后,正是在Entry数组中的位置,(上述代码5和6处是如果Entry数组中不存在新要增加的元素,则执行5,6处的代码,如果存在,即Hash冲突,则执行 3-4处的代码,此处HashMap中采用链地址法解决Hash冲突。此处经网民bbycszh指正,发现上述陈述有个别标题)。重新诠释:其实不管Entry数组中i地方有无成分,都会去实施伍-六处的代码,借使未有,则平素增加产量,借使有,则将新成分设置为Entry[0],其next指针指向原有对象,即原有对象为Entry[1]。具体方法能够解释为下边包车型大巴那段文字:(叁-四处的代码只是反省在索引为i的那条链上有未有key重复的,有则替换且重回原值,程序不再去实践5-陆处的代码,无则无处理

地点大家提到过Entry类里面有四个next属性,成效是指向下三个Entry。如,
第二个键值对A进来,通过测算其key的hash获得的i=0,记做:Entry[0] =
A。1会后又进来1个键值对B,通过总括其i也就是0,今后如何是好?HashMap会那样做:B.next
= A,Entry[0] = B,如果又进来C,i约等于0,那么C.next = B,Entry[0] =
C;那样大家发现i=0的地点实际上存取了A,B,C七个键值对,他们经过next那特性情链接在联合,也正是说数组中储存的是最后插入的要素。

到那里甘休,HashMap的差不多完毕,大家应当早就通晓了。当然HashMap里面也包蕴部分优化方面的落到实处,那里也说一下。比如:Entry[]的长短一定后,随着map里面数据的更长,那样同一个i的链就会非常长,会不会潜移默化属性?HashMap里面设置多个成分(也号称因子),随着map的size更加大,Entry[]会以自然的规则加长长度。 

2、get(Object key)操作 
get(Object
key)操作时依照键来获取值,固然领悟了put操作,get操作不难驾驭,先来看看源码的落实:

[java] view
plain
 copy

  1. public V
    get(Object key) { 
  2.         if (key
    == null) 
  3.             return getForNullKey(); 
  4.         int hash
    = hash(key.hashCode()); 
  5.         for (Entry<K,V>
    e = table[indexFor(hash, table.length)]; 
  6.             
    e != null; 
  7.             
    e = e.next) { 
  8.            
    Object k; 
  9.             if (e.hash
    == hash && ((k = e.key) == key || key.equals(k)))//——————-1—————- 
  10.                 return e.value; 
  11.        
  12.         return null; 
  13.    

趣味正是:壹、当key为null时,调用getForNullKey(),源码如下:

[java] view
plain
 copy

  1. private V
    getForNullKey() { 
  2.         for (Entry<K,V>
    e = table[0];
    e != null;
    e = e.next) { 
  3.             if (e.key
    == null) 
  4.                 return e.value; 
  5.        
  6.         return null; 
  7.    

二、当key不为null时,先依据hash函数得到hash值,在更具indexFor()获得i的值,循环遍历链表,假若有:key值等于已存在的key值,则赶回其value。如上述get()代码壹处判断。

总结下HashMap新增put和获取get操作:

[java] view
plain
 copy

  1. //存储时: 
  2. int hash
    = key.hashCode(); 
  3. int i
    = hash % Entry[].length; 
  4. Entry[i]
    = value; 
  5.  
  6. //取值时: 
  7. int hash
    = key.hashCode(); 
  8. int i
    = hash % Entry[].length; 
  9. return Entry[i]; 

略知12了就相比简单。

此间附三个简便的HashMap小算法应用:

[java] view
plain
 copy

  1. package com.xtfggef.hashmap; 
  2.  
  3. import java.util.HashMap; 
  4. import java.util.Map; 
  5. import java.util.Set; 
  6.  
  7. /** 
  8. *
    打字与印刷在数组中冒出n/二以上的成分 
  9. *
    利用2个HashMap来存放数组成分及出现的次数 
  10. *
    @author erqing 
  11. */ 
  12. public class HashMapTest
  13.      
  14.     public static void main(String[]
    args) { 
  15.          
  16.         int []
    a = {2,3,2,2,1,4,2,2,2,7,9,6,2,2,3,1,0}; 
  17.          
  18.        
    Map<Integer, Integer> map = new HashMap<Integer,Integer>(); 
  19.         for(int i=0;
    i<a.length; i++){ 
  20.             if(map.containsKey(a[i])){ 
  21.                 int tmp
    = map.get(a[i]); 
  22.                
    tmp+=1; 
  23.                
    map.put(a[i], tmp); 
  24.            
    }else{ 
  25.                
    map.put(a[i], 1); 
  26.            
  27.        
  28.        
    Set<Integer> set = map.keySet();//————1———— 
  29.         for (Integer
    s : set) { 
  30.             if(map.get(s)>=a.length/2){ 
  31.                
    System.out.println(s); 
  32.            
  33.        
    }//————–2————— 
  34.    

此地注意四个地点,map.containsKey(),还有正是上述壹-二处的代码。

精晓了HashMap的方面包车型大巴操作,此外的超越5九%措施都很简单精晓了。搞了然它的个中存款和储蓄机制,壹切OK! 

贰、HashTable的内部存款和储蓄结构

HashTable和HashMap选择同样的储存机制,二者的落实基本1致,不相同的是:

一、HashMap是非线程安全的,HashTable是线程安全的,内部的主意基本皆以synchronized。

2、HashTable不允许有null值的存在。

在HashTable中调用put方法时,假若key为null,直接抛出NullPointerException。别的细微的不相同还有,比如开头化Entry数组的轻重等等,但基本思念和HashMap一样。

三、HashTable和ConcurrentHashMap的比较

如作者开篇所说1样,ConcurrentHashMap是线程安全的HashMap的完结。同样是线程安全的类,它与HashTable在一起方面有啥样区别呢?

之前大家说,synchronized关键字加锁的法则,其实是对指标加锁,不论你是在形式前加synchronized照旧语句块前加,锁住的都以目的全体,不过ConcurrentHashMap的一头机制和这一个区别,它不是加synchronized关键字,而是基于lock操作的,这样的指标是保证同步的时候,锁住的不是整套对象。事实上,ConcurrentHashMap能够满意concurrentLevel个线程并发无阻塞的操作集合对象。关于concurrentLevel稍后介绍。

一、构造方法

为了简单精通,大家先从构造函数聊到。ConcurrentHashMap是基于多个叫Segment数组的,其实和Entry类似,如下:

[java] view
plain
 copy

  1. public ConcurrentHashMap() 
  2.  
  3.     this(16, 0.75F, 16); 
  4.  

暗中同意传入值16,调用下边包车型大巴办法:

[java] view
plain
 copy

  1. public ConcurrentHashMap(int paramInt1, float paramFloat, int paramInt2) 
  2.  
  3.     if ((paramFloat
    <= 0F) || (paramInt1 < 0)
    || (paramInt2 <= 0)) 
  4.       throw new IllegalArgumentException(); 
  5.  
  6.     if (paramInt2 > 65536)
  7.      
    paramInt2 = 65536; 
  8.    
  9.  
  10.     int i
    = 0; 
  11.     int j
    = 1; 
  12.     while (j
    < paramInt2) { 
  13.      
    ++i; 
  14.      
    j <<= 1; 
  15.    
  16.     this.segmentShift
    = (32 –
    i); 
  17.     this.segmentMask
    = (j – 1); 
  18.     this.segments
    = Segment.newArray(j); 
  19.  
  20.     if (paramInt1 > 1073741824) 
  21.      
    paramInt1 = 1073741824; 
  22.     int k
    = paramInt1 / j; 
  23.     if (k *
    j < paramInt1) 
  24.      
    ++k; 
  25.     int l
    = 1; 
  26.     while (l
    < k) 
  27.      
    l <<= 1; 
  28.  
  29.     for (int i1
    = 0;
    i1 < this.segments.length;
    ++i1) 
  30.       this.segments[i1]
    = new Segment(l,
    paramFloat); 
  31.  

您会发现比HashMap的构造函数多多个参数,paramInt一正是大家事先谈过的initialCapacity,正是数组的早先化大小,paramfloat为loadFactor(装载因子),而paramInt二则是我们所要说的concurrentLevel,这八个值分别被初阶化为1陆,0.75,1陆,经过:

[java] view
plain
 copy

  1. while (j
    < paramInt2) { 
  2.      
    ++i; 
  3.      
    j <<= 1; 
  4.    

后,j就是大家最后要开拓的数组的size值,当paramInt1为1陆时,总结出来的size值正是1陆.因而:

this.segments =
Segment.newArray(j)后,大家看出了,最后稿创立的Segment数组的大大小小为1陆.末段成立Segment对象时:

[java] view
plain
 copy

  1. this.segments[i1]
    = new Segment(cap,
    paramFloat); 

急需cap值,而cap值来源于:

[java] view
plain
 copy

  1. int k
    = paramInt1 / j; 
  2.   if (k *
    j < paramInt1) 
  3.    
    ++k; 
  4.   int cap
    = 1; 
  5.   while (cap
    < k) 
  6.    
    cap <<= 1; 

组后创设大小为cap的数组。最终遵照数组的大小及paramFloat的值算出了threshold的值:

this.threshold =
(int)(paramArrayOfHashEntry.length * this.loadFactor)。

2、put操作

[java] view
plain
 copy

  1. public V
    put(K paramK, V paramV) 
  2.  
  3.     if (paramV
    == null) 
  4.       throw new NullPointerException(); 
  5.     int i
    = hash(paramK.hashCode()); 
  6.     return segmentFor(i).put(paramK,
    i, paramV, false); 
  7.  

与HashMap不一致的是,假如key为null,直接抛出NullPointer分外,之后,同样先总括hashCode的值,再计算hash值,但是那里hash函数和HashMap中的不等同:

[java] view
plain
 copy

  1. private static int hash(int paramInt) 
  2.  
  3.    
    paramInt += (paramInt << 15 ^ 0xFFFFCD7D); 
  4.    
    paramInt ^= paramInt >>> 10; 
  5.    
    paramInt += (paramInt << 3); 
  6.    
    paramInt ^= paramInt >>> 6; 
  7.    
    paramInt += (paramInt << 2) +
    (paramInt << 14); 
  8.     return (paramInt
    ^ paramInt >>> 16); 
  9.  

 

[java] view
plain
 copy

  1. final Segment<K,
    V> segmentFor(int paramInt) 
  2.  
  3.     return this.segments[(paramInt >>> this.segmentShift
    & this.segmentMask)]; 
  4.  

依据上述代码找到Segment对象后,调用put来操作:

[java] view
plain
 copy

  1. V
    put(K paramK, int paramInt,
    V paramV, boolean paramBoolean) 
  2.  
    lock(); 
  3.   try { 
  4.    
    Object localObject1; 
  5.    
    Object localObject2; 
  6.     int i
    = this.count; 
  7.     if (i++ > this.threshold) 
  8.      
    rehash(); 
  9.    
    ConcurrentHashMap.HashEntry[] arrayOfHashEntry = this.table; 
  10.     int j
    = paramInt & arrayOfHashEntry.length – 1; 
  11.    
    ConcurrentHashMap.HashEntry localHashEntry1 =
    arrayOfHashEntry[j]; 
  12.    
    ConcurrentHashMap.HashEntry localHashEntry2 =
    localHashEntry1; 
  13.     while ((localHashEntry2
    != null)
    && (((localHashEntry2.hash != paramInt) ||
    (!(paramK.equals(localHashEntry2.key)))))) { 
  14.      
    localHashEntry2 = localHashEntry2.next; 
  15.    
  16.  
  17.     if (localHashEntry2
    != null)
  18.      
    localObject1 = localHashEntry2.value; 
  19.       if (!(paramBoolean)) 
  20.        
    localHashEntry2.value = paramV; 
  21.    
  22.     else { 
  23.      
    localObject1 = null; 
  24.       this.modCount
    += 1; 
  25.      
    arrayOfHashEntry[j] = new ConcurrentHashMap.HashEntry(paramK,
    paramInt, localHashEntry1, paramV); 
  26.       this.count
    = i; 
  27.    
  28.     return localObject1; 
  29.  
    } finally { 
  30.    
    unlock(); 
  31.  

先调用lock(),lock是ReentrantLock类的贰个办法,用当下囤积的个数+壹来和threshold相比,假使过量threshold,则展开rehash,将日前的体量扩张贰倍,重新开始展览hash。之后对hash的值和数组大小-一拓展按位于操作后,获得当前的key必要放入的岗位,从此刻开首,和HashMap1样。

从上述的辨析看来,ConcurrentHashMap基于concurrentLevel划分出了五个Segment来对key-value实行仓库储存,从而幸免每一次锁定任何数组,在私下认可的情事下,允许十五个线程并发无阻塞的操作集合对象,尽大概地缩减并发时的不通现象。

在多线程的环境中,相对于HashTable,ConcurrentHashMap会带来非常的大的习性进步!


四、HashMap常见难点分析

一、此处笔者觉得网友huxb23@126的一篇小说说的很好,剖析二十二十四线程并发写HashMap线程被hang住的缘由 ,因为是可观的能源,此处小编收10下搬到此刻。

以下内容转自博文:http://blog.163.com/huxb23@126/blog/static/625898182011211318854/ 

先看原难点代码:

[java] view
plain
 copy

  1. import java.util.HashMap; 
  2.  
  3. public class TestLock
  4.  
  5.     private HashMap
    map = new HashMap(); 
  6.  
  7.     public TestLock()
  8.        
    Thread t1 = new Thread()
  9.             public void run()
  10.                 for (int i
    = 0;
    i < 50000;
    i++) { 
  11.                    
    map.put(new Integer(i),
    i); 
  12.                
  13.                
    System.out.println(“t1
    over”); 
  14.            
  15.        
    }; 
  16.  
  17.        
    Thread t2 = new Thread()
  18.             public void run()
  19.                 for (int i
    = 0;
    i < 50000;
    i++) { 
  20.                    
    map.put(new Integer(i),
    i); 
  21.                
  22.  
  23.                
    System.out.println(“t2
    over”); 
  24.            
  25.        
    }; 
  26.  
  27.        
    t1.start(); 
  28.        
    t2.start(); 
  29.  
  30.    
  31.  
  32.     public static void main(String[]
    args) { 
  33.         new TestLock(); 
  34.    

便是启了多少个线程,不断的往3个非线程安全的HashMap中put内容,put的内容很不难,key和value都以从0自增的整数(那一个put的始末做的并倒霉,以致于后来苦恼了本人分析问题的思路)。对HashMap做并发写操作,我原以为只不过会时有产生脏数据的动静,但屡次运转这几个程序,会产出线程t1、t二被hang住的气象,多数景况下是一个线程被hang住另3个成功结束,偶尔会多少个线程都被hang住。说起此地,你壹旦认为不佳好学习ConcurrentHashMap而在那瞎折腾就手下留情跳过啊。 
行吗,分析下HashMap的put函数源码看看难题出在哪,那里就位列出有关代码(jdk一.陆):

[java] view
plain
 copy

  1. public V
    put(K paramK, V paramV) 
  2.   if (paramK
    == null) 
  3.     return putForNullKey(paramV); 
  4.   int i
    = hash(paramK.hashCode()); 
  5.   int j
    = indexFor(i, this.table.length); 
  6.   for (Entry
    localEntry = this.table[j];
    localEntry != null;
    localEntry = localEntry.next) 
  7.  
  8.     if (localEntry.hash
    == i) { java.lang.Object localObject1; 
  9.       if (((localObject1
    = localEntry.key) == paramK) || (paramK.equals(localObject1)))
  10.        
    java.lang.Object localObject2 = localEntry.value; 
  11.        
    localEntry.value = paramV; 
  12.        
    localEntry.recordAccess(this); 
  13.         return localObject2; 
  14.      
  15.    
  16.  
  17.   this.modCount
    += 1; 
  18.  
    addEntry(i, paramK, paramV, j); 
  19.   return null; 
  20.  
  21. private V
    putForNullKey(V paramV) 
  22.   for (Entry
    localEntry = this.table[0];
    localEntry != null;
    localEntry = localEntry.next) 
  23.     if (localEntry.key
    == null)
  24.      
    java.lang.Object localObject = localEntry.value; 
  25.      
    localEntry.value = paramV; 
  26.      
    localEntry.recordAccess(this); 
  27.       return localObject; 
  28.    
  29.  
  30.   this.modCount
    += 1; 
  31.  
    addEntry(0, null,
    paramV, 0); 
  32.   return null; 

 

因此jconsole(或许thread
dump),能够观看线程停在了transfer方法的while循环处。这些transfer方法的效果是,当Map凉月素数超越阈值供给resize时,它担负把原Map中的成分映射到新Map中。小编修改了HashMap,加上了@标记二和@标记三的代码片断,以打字与印刷出死循环时的事态,结果死循环线程总是出现类似那样的出口:“Thread-一,e==next:false,e==next.next:true,e:十8928=拾892八,next:十892八=拾892八,eq:true”。 
本条输出声明: 
一)这些Entry链中的七个Entry之间的关联是:e=e.next.next,造成死循环。 
2)e.equals(e.next),但e!=e.next。因为测试例子中七个线程put的始末同样,并发时恐怕同二个key被保存了四个value,那种不当是在addEntry函数爆发的,但那和线程死循环未有涉嫌。

接下去就分析transfer中非凡while循环了。先所说那些轮回寻常的效能:src[j]保留的是炫耀成同2个hash值的多少个Entry的链表,那一个src[j]莫不为null,恐怕唯有贰个Entry,也也许由多个Entry链接起来。借使是三个Entry,原来的链是(src[j]=a)->b(也就是src[j]=a,a.next=b,b.next=null),经过while处理后获得了(newTable[i]=b)->a。也正是说,把链表的next关系反向了。

再看看那一个while中或许在八线程景况下引起难题的言辞。针对七个线程t一和t二,那里它们或然的发生难点的履行种类做些个人分析:

一)假使同二个Entry列表[e->f->…],t一先到,t二后到并都走到while中。t一实施“e.next
= newTable[i];newTable[i] =
e;”这使得e.next=null(初始的newTable[i]为null),newTable[i]指向了e。这时t2执行了“e.next
= newTable[i];newTable[i] =
e;”,那使得e.next=e,e死循环了。因为循环起来处的“final Entry next =
e.next;”,固然e自个儿死循环了,在结尾的“e =
next;”后,三个线程都会跳过e继续执行下去。

二)在while中每一个遍历Entry链表中的Entry而把next关系反向时,newTable[i]改为了被换来的引用,狐疑的言语在于“e.next

newTable[i];”。假若链表e->f->g被t1拍卖成e<-f<-g,newTable[i]本着了g,那时t2进来了,它壹举行“e.next

newTable[i];”就使得e->g,造成了死循环。所以,理论上来说,死循环的Entry个数大概很多。就算产生了死循环,不过t一执行到了死循环的右手,所以是会继续执行下去的,而t二要是推行“final
Entry next =
e.next;”的next为null,则也会继续执行下去,不然就进来了死循环。

3)就如状态会更扑朔迷离,因为尽管线程跳出了死循环,它下三回做resize进入transfer时,有相当大可能因为从前的死循环Entry链表而被hang住(就如是任其自然会被hang住)。也有希望,在put检查Entry链表时(@标记1),因为Entry链表的死循环而被hang住。也就像有极大恐怕,活着的线程和死循环的线程同时实行在while里后,四个线程都能活着出去。所以,或然八个线程平安退出,恐怕一个线程hang在transfer中,恐怕三个线程都被hang住而又不自然在3个地点。

四)我一再的测试,出现3个线程被hang住的情景最多,都以e=e.next.next造成的,那第2正是例证put两份增量数据造成的。小编借使去掉@标记三的出口,有时也能复现多少个线程都被hang住的景色,但增进后就很难复现出来。笔者又把put的数据改了下,比如让四个线程put范围分歧的数量,就能复现出e=e.next,七个线程都被hang住的意况。

上边罗哩罗嗦了广大,1开端本身不难的剖析后以为就像是知道了怎么回事,可目前细心商讨后如同又不晓得了众多。有一个细节是,每便死循环的key的高低也是有据可循的,小编就不打哈了。感觉,若是样本多些,大概出现难题的原由点会很多,也会更扑朔迷离,笔者姑且不再蛋疼下去。至于有人涉嫌ConcurrentHashMap也有那个难题,小编以为相当小恐怕,因为它的put操作是加锁的,即便有那一个题材就不叫线程安全的Map了。

二、HashMap中Value能够等效,可是键不得以等效

当插入HashMap的key相同时,会覆盖原有的Value,且重返原Value值,看下边包车型大巴次序:

[java] view
plain
 copy

  1. public class Test
  2.  
  3.     public static void main(String[]
    args) { 
  4.          
  5.        
    HashMap<String,Integer> map = new HashMap<String,Integer>(); 
  6.  
  7.         //出入四个Value相同的值,未有失常态 
  8.        
    map.put(“egg”, 1); 
  9.        
    map.put(“niu”, 1); 
  10.          
  11.         //插入key相同的值,看重回结果 
  12.         int egg
    = (Integer) map.put(“egg”, 3); 
  13.          
  14.        
    System.out.println(egg);   //输出1 
  15.        
    System.out.println(map.get(“egg”));   //输出3,将原值1覆盖 
  16.        
    System.out.println(map.get(“niu”));   //输出1 
  17.    

1致的键会被覆盖,且重临原值。

三、HashMap按值排序

给定一个数组,求出种种数据出现的次数并遵照次数的由大到小排列出来。大家接纳HashMap来做,key存款和储蓄数组成分,值存款和储蓄出现的次数,最终用Collections的sort方法对HashMap的值进行排序。代码如下:

[java] view
plain
 copy

  1. public class Test
  2.  
  3.     public static void main(String[]
    args) { 
  4.  
  5.         int data[]
    = { 2, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 
  6.                 7, 8, 8, 7, 8, 7, 9, 0 }; 
  7.        
    Map<Integer, Integer> map = new HashMap<Integer,
    Integer>(); 
  8.         for (int i
    : data) { 
  9.             if (map.containsKey(i))
    {//判断HashMap里是还是不是存在 
  10.                
    map.put(i, map.get(i) + 1);//已存在,值+1 
  11.            
    } else { 
  12.                
    map.put(i, 1);//不存在,新增 
  13.            
  14.        
  15.         //map按值排序 
  16.        
    List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer,
    Integer>>( 
  17.                
    map.entrySet()); 
  18.        
    Collections.sort(list, new Comparator<Map.Entry<Integer,
    Integer>>() { 
  19.             public int compare(Map.Entry<Integer,
    Integer> o1, 
  20.                    
    Map.Entry<Integer, Integer> o2) { 
  21.                 return (o2.getValue() –
    o1.getValue()); 
  22.            
  23.        
    }); 
  24.         for (Map.Entry<Integer,
    Integer> m : list) { 
  25.            
    System.out.println(m.getKey() + “-” +
    m.getValue()); 
  26.        
  27.    
  28.  

输出:

2-6 
5-5 
3-4 
8-3 
7-3 
9-1 
0-1