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集合类是个13分首要的知识点,HashMap、HashTable、ConcurrentHashMap等算是集合类中的重点,可谓“重中之重”,首先来看个难点,如面试官问你:HashMap和HashTable有如何界别,一个相比较简单的回答是:

解析二十四线程并发写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();
  }
}

正是启了多少个线程,不断的往七个非线程安全的HashMap中put内容,put的剧情相当粗略,key和value都以从0自增的平头(那些put
的内容做的并倒霉,以致于后来干扰了自家分析难题的思绪)。对HashMap做并发写操作,作者原感觉只不过会产生脏数据的情况,但屡屡运营这一个顺序,会冒出
线程t一、t二被hang住的意况,大多景观下是3个线程被hang住另一个打响甘休,偶尔会八个线程都被hang住。聊到此处,你只要以为不佳好学习
ConcurrentHashMap而在那瞎折腾就手下留情跳过吗。
好呢,分析下HashMap的put函数源码看看难题出在哪,那里就罗列出相关代码(jdk1.6):

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:10892捌=108928,next:10892八=拾8928,eq:true”。
这一个输出声明:
一)这么些Entry链中的多个Entry之间的涉嫌是:e=e.next.next,变成死循环。
2)e.equals(e.next),但e!=e.next。因为测试例子中多个线程put的剧情1致,并发时恐怕同二个key被保留了多少个value,那种漏洞非常多是在addEntry函数发生的,但那和线程死循环未有涉及。

接下去就分析transfer中特别while循环了。先所说这么些轮回平常的魔法:src[j]封存的是炫目成同多少个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一和t二,那里它们恐怕的爆发难点的实施类别做些个人分析:

一)倘使同3个Entry列表[e->f->…],t1先到,t2后到并都走到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 Entrynext =
e.next;”,就算e自个儿死循环了,在终极的“e =
next;”后,三个线程都会跳过e继续试行下去。

二)在while中每一种遍历Entry链表中的Entry而把next关系反向时,newTable[i]化为了被换来的引用,狐疑的言辞在于
“e.next =
newTable[i];”。假使链表e->f->g被t一拍卖成eg,产生了死循环。所以,理论上的话,死循环的Entry个数大概繁多。
就算爆发了死循环,不过t一实施到了死循环的左侧,所以是会继续试行下去的,而t②假如实践“final
Entrynext =
e.next;”的next为null,则也会继续实行下去,不然就进去了死循环。

三)就像状态会更复杂,因为正是线程跳出了死循环,它下叁遍做resize进入transfer时,有希望因为前面的死循环Entry链表而被
hang住(如同是断定会被hang住)。也有不小大概,在put检查Entry链表时(@标识1),因为Entry链表的死循环而被hang住。也仿佛有不小可能率,活着的线程和死循环的线程同时推行在while里后,五个线程都能活着出来。所以,恐怕八个线程平安退出,恐怕1个线程hang在transfer
中,或然八个线程都被hang住而又不必然在二个地点。

四)我数十三回的测试,出现3个线程被hang住的场合最多,都以e=e.next.next产生的,那重大便是例证put两份增量数据造成的。笔者若是去掉@标识叁的输出,有时也能复现七个线程都被hang住的图景,但丰硕后就很难复现出来。笔者又把put的数量改了下,比如让四个线程put范围不一的数
据,就能复现出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类应用而生!总想在小说的发端说个别什么,但又无从提起。从方今的有些面试聊到吧,感受正是:知识是永无边无际的,永久不要感觉温馨已经通晓了一些事物。若是对哪1块知识感兴趣,那么,请多多的花时间,哪怕最基础的事物也要明了它的法则,尽量往深了切磋,在学习的还要,记得多与大家调换联系,因为也许有个别事物,从您本人的角度,是很难发现的,因为你并从未那么多的尝试环境去发现她们。只有调换的多了,手艺立时寻觅团结的供不应求,本事认识到:“哦,原来我还有如此多不亮堂的事物!”。


1、HashMap的里边存款和储蓄结构 
Java中多少存款和储蓄格局最尾巴部分的二种结构,一种是数组,另壹种便是链表,数组的特点:三番五次空间,寻址飞快,但是在剔除或许添新币素的时候须要有较大开间的位移,所以查询速度快,增加和删除较慢。而链表正好相反,由于空间不总是,寻址困难,增加和删除成分只需修改指针,所以查询慢、增加和删除快。有未有1种数据结构来综合一下数组和链表,以便发挥她们分别的优势?答案是毫无疑问的!正是:哈希表。哈希表具有较快(常量级)的询问速度,及相对较快的增加和删除速度,所以很适合在海量数据的条件中采用。一般达成哈希表的章程应用“拉链法”,我们能够精通为“链表的数组”,如下图:

图片 1

从上海体育场面中,大家得以发现哈希表是由数组+链表组成的,二个长短为1陆的数组中,每种成分存款和储蓄的是贰个链表的头结点。那么这几个要素是服从什么的平整存款和储蓄到数组中呢。一般景色是由此hash(key)%len得到,也正是因素的key的哈希值对数主任度取模获得。比如上述哈希表中,1二%1陆=1二,28%1六=1二,十8%1六=1二,1五分之二1陆=1贰。所以1二、28、10八以及140都存款和储蓄在数组下标为1二的职位。它的个中其实是用三个Entity数组来落到实处的,属性有key、value、next。接下来笔者会从开始化阶段详细的疏解HashMap的内部结构。

1、初始化  第一来看三个常量: 
static final int DEFAULT_INITIAL_CAPACITY = 1陆; 初叶容积:1陆 
static final int MAXIMUM_CAPACITY = 1  
<< 30; 最大容积:二的3二回方:十73741捌贰四 
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.捌),loadFactor为0.八,capacity为7,通过上述代码后,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,体量扩充二倍。
如果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.     }  

看源码中二处,首先会进行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]。具体方法能够分解为下边包车型客车那段文字:(3-肆处的代码只是检查在索引为i的那条链上有没有key重复的,有则替换且再次来到原值,程序不再去施行5-陆处的代码,无则无处理

地方大家关系过Entry类里面有2个next属性,作用是指向下二个Entry。如,
第二个键值对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里面设置3个要素(也称之为因子),随着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.     }  

2、当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];  

接头了就相比较轻松。

那边附一个大致的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.  */  
  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的下边的操作,别的的大多数办法都很轻易精晓了。搞通晓它的里边存款和储蓄机制,1切OK!

二、HashTable的中间存款和储蓄结构

HashTable和HashMap选拔同一的仓库储存机制,二者的兑现基本一致,不一样的是:

一、HashMap是非线程安全的,HashTable是线程安全的,内部的措施基本都以synchronized。

二、HashTable不容许有null值的存在。

在HashTable中调用put方法时,倘使key为null,直接抛出NullPointerException。其余细微的歧异还有,比如初叶化Entry数组的大小等等,但中央思维和HashMap同样。

三、HashTable和ConcurrentHashMap的比较

如我开篇所说同样,ConcurrentHashMap是线程安全的HashMap的贯彻。一样是线程安全的类,它与HashTable在同步方面有哪些不相同吧?

前边大家说,synchronized关键字加锁的原理,其实是对目的加锁,不论你是在艺术前加synchronized还是语句块前加,锁住的都是指标全体,不过ConcurrentHashMap的联合签字机制和那几个分裂,它不是加synchronized关键字,而是基于lock操作的,那样的指标是确认保障同步的时候,锁住的不是任何对象。事实上,ConcurrentHashMap能够满意concurrentLevel个线程并发无阻塞的操作集合对象。关于concurrentLevel稍后介绍。

一、构造方法

为了轻易理解,我们先从构造函数提起。ConcurrentHashMap是依据2个叫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的构造函数多3个参数,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值,当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中的不均等:

[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类的3个方法,用当下囤积的个数+壹来和threshold相比较,要是过量threshold,则打开rehash,将近来的体量扩展二倍,重新实行hash。之后对hash的值和数组大小-1进行按位于操作后,获得当前的key须求放入的地点,从此时起头,和HashMap同样。

从上述的辨析看来,ConcurrentHashMap基于concurrentLevel划分出了多少个Segment来对key-value进行仓库储存,从而幸免每一次锁定任何数组,在暗中同意的场所下,允许十五个线程并发无阻塞的操作集合对象,尽可能地压缩并发时的围堵现象。

在四线程的环境中,相对于HashTable,ConcurrentHashMap会带来不小的天性提高!

欢迎读者批评指正,有别的建议请联系:

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

4、HashMap常见难点分析

一、此处笔者感到网友huxb23@126的1篇作品说的很好,分析八线程并发写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、t2被hang住的意况,大多景况下是二个线程被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:十892八=十892捌,next:十8928=十8928,eq:true”。
那些输出注解:
壹)这些Entry链中的多少个Entry之间的涉嫌是:e=e.next.next,形成死循环。
2)e.equals(e.next),但e!=e.next。因为测试例子中四个线程put的剧情一致,并发时只怕同2个key被保留了四个value,那种错误是在addEntry函数产生的,但那和线程死循环未有涉及。

接下去就分析transfer中国和亚洲常while循环了。先所说那些轮回符合规律的功能:src[j]保留的是绚烂成同3个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二,那里它们或许的爆发难点的实践系列做些个人分析:

一)要是同3个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被t一甩卖成e<-f<-g,newTable[i]本着了g,那时t二进来了,它壹执行“e.next

newTable[i];”就使得e->g,形成了死循环。所以,理论上的话,死循环的Entry个数只怕许多。即便产生了死循环,不过t1试行到了死循环的出手,所以是会继续实行下去的,而t2假诺实行“final
Entry next =
e.next;”的next为null,则也会继续施行下去,不然就进入了死循环。

三)就像是状态会更复杂,因为即便线程跳出了死循环,它下三遍做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了。

2、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.     }  
  18. }  

一致的键会被遮盖,且重临原值。

三、HashMap按值排序

给定2个数组,求出种种数据出现的次数并遵循次数的由大到小排列出来。大家选用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].表达,暗中认可就是开辟17个高低的空中。别的二个重大的构造方法:

[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.八),loadFactor为0.8,capacity为7,通过上述代码后,capacity的值为:八.(一<< 2的结果是4,二 << 二的结果为8<此处谢谢网络好友wego1234的指正>)。所以,最后capacity的值为8,末了经过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],并基于第1个成分的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,体量增添二倍。 
如果key不为null,那也是超越1/二的景况,重新看一下源码:

[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类的1个办法,为地方方法,内部贯彻相比较复杂,大家 
会在后头作单独的有关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重复的,有则替换且重回原值,程序不再去执行5-陆处的代码,无则无处理

上边大家提到过Entry类里面有二个next属性,成效是指向下二个Entry。如,
第二个键值对A进来,通过测算其key的hash得到的i=0,记做:Entry[0] =
A。壹会后又进来三个键值对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]; 

精通了就比较轻便。

那边附3个简短的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. *
    利用3个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的下面的操作,别的的超过50%主意都很轻松理解了。搞通晓它的内部存款和储蓄机制,壹切OK! 

贰、HashTable的里边存储结构

HashTable和HashMap选取一样的存款和储蓄机制,2者的兑现基本壹致,差别的是:

一、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稍后介绍。

1、构造方法

为了便于通晓,大家先从构造函数聊起。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的构造函数多一个参数,paramInt壹正是大家事先谈过的initialCapacity,正是数组的伊始化大小,paramfloat为loadFactor(装载因子),而paramInt二则是大家所要说的concurrentLevel,那多少个值分别被先河化为16,0.7伍,16,经过:

[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数组的分寸为16.末尾成立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类的1个格局,用当下储存的个数+一来和threshold比较,假使超越threshold,则打开rehash,将近年来的容积扩充2倍,重新举办hash。之后对hash的值和数组大小-一开始展览按位于操作后,获得当前的key供给放入的职位,从此时早先,和HashMap同样。

从上述的剖析看来,ConcurrentHashMap基于concurrentLevel划分出了两个Segment来对key-value举办仓库储存,从而防止每趟锁定任何数组,在暗许的情况下,允许17个线程并发无阻塞的操作集合对象,尽大概地减少并发时的隔断现象。

在三十二线程的条件中,相对于HashTable,ConcurrentHashMap会带来异常的大的个性提高!


4、HashMap常见难点浅析

一、此处小编以为网友huxb23@126的1篇文章说的很好,浅析二十四线程并发写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.    

正是启了多个线程,不断的往2个非线程安全的HashMap中put内容,put的始末很轻松,key和value都是从0自增的整数(那一个put的剧情做的并不好,以致于后来烦扰了自身分析难题的思绪)。对HashMap做并发写操作,小编原感觉只然则会爆发脏数据的图景,但频仍运维那些程序,会出现线程t一、t贰被hang住的景况,繁多状态下是3个线程被hang住另一个打响结束,偶尔会八个线程都被hang住。聊起此处,你只要以为倒霉好学习ConcurrentHashMap而在那瞎折腾就手下留情跳过呢。 
好呢,分析下HashMap的put函数源码看看难题出在哪,那里就罗列出有关代码(jdk1.6):

[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,加上了@标志2和@标识3的代码片断,以打字与印刷出死循环时的状态,结果死循环线程总是出现类似那样的出口:“Thread-一,e==next:false,e==next.next:true,e:10892八=十8928,next:十892八=拾892八,eq:true”。 
以此输出证明: 
1)这一个Entry链中的八个Entry之间的涉嫌是:e=e.next.next,产生死循环。 
2)e.equals(e.next),但e!=e.next。因为测试例子中几个线程put的内容一律,并发时可能同1个key被封存了两个value,那种张冠李戴是在addEntry函数发生的,但这和线程死循环未有涉及。

接下去就分析transfer中丰盛while循环了。先所说那一个轮回平常的职能:src[j]保存的是炫酷成同三个hash值的几个Entry的链表,那几个src[j]莫不为null,或许唯有2个Entry,也恐怕由八个Entry链接起来。假诺是四个Entry,原来的链是(src[j]=a)->b(也就是src[j]=a,a.next=b,b.next=null),经过while处理后得到了(newTable[i]=b)->a。也正是说,把链表的next关系反向了。

再看看这几个while中也许在10二线程景况下引起难题的话语。针对五个线程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 Entry next =
e.next;”,固然e本人死循环了,在最终的“e =
next;”后,多个线程都会跳过e继续履行下去。

2)在while中各个遍历Entry链表中的Entry而把next关系反向时,newTable[i]形成了被换到的引用,疑心的讲话在于“e.next

newTable[i];”。若是链表e->f->g被t一处理成e<-f<-g,newTable[i]针对了g,那时t2进来了,它1试行“e.next

newTable[i];”就使得e->g,变成了死循环。所以,理论上来讲,死循环的Entry个数大概诸多。固然产生了死循环,不过t一实施到了死循环的动手,所以是会继续施行下去的,而t二如若施行“final
Entry next =
e.next;”的next为null,则也会继续执行下去,不然就进去了死循环。

三)就像状态会更扑朔迷离,因为就算线程跳出了死循环,它下二回做resize进入transfer时,有不小概率因为在此之前的死循环Entry链表而被hang住(就好像是必定会被hang住)。也有非常大可能率,在put检查Entry链表时(@标志一),因为Entry链表的死循环而被hang住。也就像有希望,活着的线程和死循环的线程同时实践在while里后,五个线程都能活着出来。所以,恐怕三个线程平安退出,恐怕二个线程hang在transfer中,恐怕两个线程都被hang住而又不鲜明在二个地点。

四)小编屡屡的测试,出现多个线程被hang住的场地最多,都以e=e.next.next变成的,那重大就是例证put两份增量数据形成的。作者一旦去掉@标志叁的输出,有时也能复现多个线程都被hang住的意况,但增加后就很难复现出来。笔者又把put的数码改了下,比如让多少个线程put范围不一的多少,就能复现出e=e.next,多个线程都被hang住的情况。

上边罗哩罗嗦了多数,一同始笔者大约的分析后以为就好像知道了怎么回事,可近来细心雕刻后就像是又不知晓了成百上千。有贰个细节是,每一趟死循环的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

相关文章

网站地图xml地图