开发者社区> hengyunabc> 正文

Java中的几个HashMap/ConcurrentHashMap实现分析

简介:
+关注继续查看

一、HashMap,即java.util.HashMap

标准链地址法实现。这个不用多解析,下图十分明了。(图片来自网络)

二、Collections.synchronizedMap() 函数返回的线程安全的HashMap

这个的实现比较简单。

代码中有:

    private final Map<K,V> m;     // Backing Map
    final Object      mutex;// Object on which to synchronize


基本所有的方法都加上了synchronized(mutex)。

但是这个HashMap不能随便地进行迭代,因为它只是简单包装了HashMap,而回看HashMap的实现,我们可以发现,对于冲突的key,形成一个链表,明显如果有一个线程在历遍HashMap,另一个线程在做删除操作,则很有可能出错。

因此,JDK中给出以下代码:

  Map m = Collections.synchronizedMap(new HashMap());
      ...
  Set s = m.keySet();  // Needn't be in synchronized block
      ...
  synchronized(m) {  // Synchronizing on m, not s!
      Iterator i = s.iterator(); // Must be in synchronized block
      while (i.hasNext())
          foo(i.next());
  }



三、ConcurrentHashMap

对于HashMap,最主要的是以下四种的操作:

	public V get(Object key)
	public V put(K key, V value)
	public V remove(Object key)
	迭代

在多线程环境下,get,put,remove都是比较容易实现的(如果不考虑效率,简单加锁即可),迭代的操作才是真正的难点。

从Collections.synchronizedMap()的迭代来看,它并不能做到对客户代码透明,有点蛋疼。

下面简单分析ConcurrentHashMap的实现,相当精巧。

默认一个ConcurrentHashMap中有16个HashMap,所以相当于一个二级哈希。对于所有的操作都是先定位到子HashMap,再作相应的操作。

对于:

public V get(Object key)

先得到 key所在的table,再像HashMap一样get
中间并不加锁

public V put(K key, V value)

先得到所属的table,加锁
判断table是否要扩容
如果table要扩容,则产生newTable
hash值相同的slot整体移到newTable
hash值不同的slot,把oldTable中的所有Entry都复制到newTable中
因为有可能其它线程在历遍这个table,所以不能把原来的链表拆断


public V remove(Object key)

remove操作,如下图,要删除Entry3,则先复制Entry1为Entry1*,Entry1*指向Entry4,再复制Entry2为Entry2*,Entry2*指向Entry1*,最终形成一个两叉的链表。原本的Entry1,Entry2,Entry3会被GC自动回收。


迭代操作:

ConcurrentHashMap的历遍是从后向前历遍的,因为如果有另一个线程B在执行clear操作时,会把table中的所有slot都置为null,这个操作是从前向后执行
如果线程A在历遍Map时也是从前向后,则有可能会出现追赶现象。

以下代码:

HashMap<Integer, String> m1 = new HashMap();
	m1.put(1, "001");
	m1.put(2, "002");
	for(Entry<Integer, String> entry : m1.entrySet()){
		System.out.println("key:" + entry.getKey());
	}

HashMap输出的是 key:1 key:2
ConcurrentHashMap输出的是key:2 key:1


结:Java中的类库实在太多了,HashMap还有很多,有空再补充。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Java集合源码学习(四)HashMap分析
ArrayList、LinkedList和HashMap的源码是一起看的,横向对比吧,感觉对这三种数据结构的理解加深了很多。 数据结构中有数组和链表来实现对数据的存储,这两者有不同的应用场景, 数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,插入和删除容易; 哈希表的实现结合了这两点,哈希表的实现方式有多种,在HashMap中使用的是链地址法,也就是拉链法。
1566 0
一次HASH JOIN 临时表空间不足的分析和优化思路
(原创转载请注明出处)   最近遇到一个语句,  只要一执行这个语句就会出现报错临时表空间不足,回想一下在语句中用到临时表空间无非是大量的SORT和HASH,然后通过执行计划查看如下:  PLAN_TABLE_OUTPUT------------------...
767 0
+关注
hengyunabc
负责5K+应用,60K+机器的Spring Boot微服务技术落地,关注开发体验,微服务,APM,应用诊断,dubbo开源。Github: https://github.com/hengyunabc
106
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载