`
flyfoxs
  • 浏览: 297725 次
  • 性别: Icon_minigender_1
  • 来自: 合肥
社区版块
存档分类
最新评论

2种办法让HashMap线程安全

阅读更多

多线程之--2种办法让HashMap线程安全

多线程之--synchronized 和reentrantlock的优缺点

多线程之--2种JAVA乐观锁的比较( NonfairSync VS. FairSync)

 

 

HashMap不是线程安全的,往往在写程序时需要通过一些方法来回避.其实JDK原生的提供了2种方法让HashMap支持线程安全.

 

方法一:通过Collections.synchronizedMap()返回一个新的Map,这个新的map就是线程安全的. 这个要求大家习惯基于接口编程,因为返回的并不是HashMap,而是一个Map的实现.

方法二:重新改写了HashMap,具体的可以查看java.util.concurrent.ConcurrentHashMap. 这个方法比方法一有了很大的改进.

 

下面对这2中实现方法从各个角度进行分析和比较.

  • 实现原理
  • 锁机制的不同
  • 如何得到/释放锁
  • 优缺点

 

 

1)实现原理

方法一原理: 

通过Collections.synchronizedMap()来封装所有不安全的HashMap的方法,就连toString, hashCode都进行了封装. 封装的关键点有2处,1)使用了经典的synchronized来进行互斥, 2)使用了代理模式new了一个新的类,这个类同样实现了Map接口.

 

private static class SynchronizedMap<K,V>

implements Map<K,V>, Serializable {

// use serialVersionUID from JDK 1.2.2 for interoperability

private static final long serialVersionUID = 1978198479659022715L;

 

private final Map<K,V> m;     // Backing Map

final Object      mutex;// Object on which to synchronize

 

SynchronizedMap(Map<K,V> m) {

if (m==null)

throw new NullPointerException();

this.m = m;

mutex = this;

}

 

SynchronizedMap(Map<K,V> m, Object mutex) {

this.m = m;

this.mutex = mutex;

}

 

public int size() {

synchronized(mutex) {return m.size();}

}

 

//***********************************

//节省空间,删除了大量类似代码

//***********************************

public String toString() {

synchronized(mutex) {return m.toString();}

}

private void writeObject(ObjectOutputStream s) throws IOException {

synchronized(mutex) {s.defaultWriteObject();}

}

}

 

 

方法二原理:

重新写了HashMap,比较大的改变有如下几点.

使用了新的锁机制(可以理解为乐观锁)稍后详细介绍

把HashMap进行了拆分,拆分成了多个独立的块,这样在高并发的情况下减少了锁冲突的可能

 

public V put(K key, V value) {

if (value == null)

throw new NullPointerException();

int hash = hash(key.hashCode());

return segmentFor(hash).put(key, hash, value, false);

}

 

2)锁机制的不同

方法一使用的是的synchronized方法,是一种悲观锁.在进入之前需要获得锁,确保独享当前对象,然后做相应的修改/读取.

 

方法二使用的是乐观锁,只有在需要修改对象时,比较和之前的值是否被人修改了,如果被其他线程修改了,那么就会返回失败.锁的实现,使用的是NonfairSync. 这个特性要确保修改的原子性,互斥性,无法在JDK这个级别得到解决,JDK在此次需要调用JNI方法,而JNI则调用CAS指令来确保原子性与互斥性.读者可以自行Google JAVA CAS来了解更多. JAVA的乐观锁是如何实现的.

当如果多个线程恰好操作到ConcurrentHashMap同一个segment上面,那么只会有一个线程得到运行,其他的线程会被LockSupport.park(),稍后执行完成后,会自动挑选一个线程来执行LockSupport.unpark().

 

        V put(K key, int hash, V value, boolean onlyIfAbsent) {

            lock();

            try {

                int c = count;

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

                    rehash();

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

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

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

                HashEntry<K,V> e = first;

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

                    e = e.next;

 

                V oldValue;

                if (e != null) {

                    oldValue = e.value;

                    if (!onlyIfAbsent)

                        e.value = value;

                }

                else {

                    oldValue = null;

                    ++modCount;

                    tab[index] = new HashEntry<K,V>(key, hash, first, value);

                    count = c; // write-volatile

                }

                return oldValue;

            } finally {

                unlock();

            }

        }

 

 

 

 

3)如何得到/释放锁

得到锁:

方法一:在Hashmap上面,synchronized锁住的是对象(不是Class),所以第一个申请的得到锁,其他线程将进入阻塞,等待唤醒.

方法二:检查AbstractQueuedSynchronizer.state,如果为0,则得到锁,或者申请者已经得到锁,则也能再辞得到锁,并且state也加1.

释放锁:

都是得到锁的逆操作,并且使用正确,二种方法都是自动选取一个队列中的线程得到锁可以获得CPU资源.

 

4)优缺点

方法一:

优点:代码实现十分简单,一看就懂.

缺点:从锁的角度来看,方法一直接使用了锁住方法,基本上是锁住了尽可能大的代码块.性能会比较差.

 

方法二:

优点:需要互斥的代码段比较少,性能会比较好. ConcurrentHashMap把整个Map切分成了多个块,发生锁碰撞的几率大大降低,性能会比较好.

缺点:代码实现稍稍复杂些.

2
1
分享到:
评论
2 楼 flyfoxs 2014-08-05  
cywhoyi 写道
JDK 8中的实现相较而言高明的多,bucket

以及额外推送一个,温少写的


仔细的看了一下温少写的这个HashMap的实现,满精简的. 短短100行就实现了一个单向链表来解决冲突的Hashmap.学习到了很多.

但是这个应该不是一个通用的HashMap应该是特定场合下适用的吧.

1)下面这处,应该是在并发下会出错,但是注释是缓存丢失,猜测这个HashMap的实现是用来做缓存的.
2) Size的实现是依靠遍历来实现的.
3) 没有实现map的接口.

buckets[bucket] = entry;  // 并发是处理时会可能导致缓存丢失,但不影响正确性
1 楼 cywhoyi 2014-08-05  
JDK 8中的实现相较而言高明的多,bucket

以及额外推送一个,温少写的
public class IdentityHashMap<K, V> {

    public static final int     DEFAULT_TABLE_SIZE = 1024;

    private final Entry<K, V>[] buckets;
    private final int           indexMask;

    public IdentityHashMap(){
        this(DEFAULT_TABLE_SIZE);
    }

    public IdentityHashMap(int tableSize){
        this.indexMask = tableSize - 1;
        this.buckets = new Entry[tableSize];
    }

    public final V get(K key) {
        final int hash = System.identityHashCode(key);
        final int bucket = hash & indexMask;

        for (Entry<K, V> entry = buckets[bucket]; entry != null; entry = entry.next) {
            if (key == entry.key) {
                return (V) entry.value;
            }
        }

        return null;
    }

    public boolean put(K key, V value) {
        final int hash = System.identityHashCode(key);
        final int bucket = hash & indexMask;

        for (Entry<K, V> entry = buckets[bucket]; entry != null; entry = entry.next) {
            if (key == entry.key) {
                entry.value = value;
                return true;
            }
        }

        Entry<K, V> entry = new Entry<K, V>(key, value, hash, buckets[bucket]);
        buckets[bucket] = entry;  // 并发是处理时会可能导致缓存丢失,但不影响正确性

        return false;
    }

    public int size() {
        int size = 0;
        for (int i = 0; i < buckets.length; ++i) {
            for (Entry<K, V> entry = buckets[i]; entry != null; entry = entry.next) {
                size++;
            }
        }
        return size;
    }

    protected static final class Entry<K, V> {

        public final int   hashCode;
        public final K     key;
        public V     value;

        public final Entry<K, V> next;

        public Entry(K key, V value, int hash, Entry<K, V> next){
            this.key = key;
            this.value = value;
            this.next = next;
            this.hashCode = hash;
        }
    }

}

相关推荐

    Spring并发访问的线程安全性问题.docx

    解决办法是使用`Collections.synchronizedMap()`来同步HashMap,或者使用`ConcurrentHashMap`,这是一种专门为多线程环境设计的线程安全的Map实现。 ```java @Service("userService") Class UserService{ public ...

    Java集合框架面试题

    - 2)都不是线程安全的类,解决办法是:Collections.synchronizedSet(Set 对象) - 3)HashSet 不保证元素的添加顺序,底层采用哈希表算法,查询效率高 - 4)LinkedHashSet:HashSet 的子类,底层采用了哈希表算法...

    JAVA面试-集合知识点汇总(高频、经典).doc

    - `ConcurrentHashMap`:一种高效且线程安全的`Map`实现。 - `Vector`:线程安全的`List`实现。 - `Stack`:基于`Vector`的栈实现,线程安全。 - **线程不安全的集合**: - `HashMap` - `ArrayList` - `...

    Java经典面试笔试题及答案 (2).pdf

    12. **HashMap与Hashtable**:HashMap是非线程安全的,允许null键值对,效率较高;Hashtable是线程安全的,不允许null键值对,效率较低,两者的父类分别为AbstractMap和Dictionary。 13. **Iterator**:Iterator...

    java面试笔试资料包括JAVA基础核心知识点深度学习Spring面试题等资料合集.zip

    第五题 如何保证集合是线程安全的.pdf 第八题 Java并发类库提供的线程池有哪几种 分别有什么特点.pdf 第六题 synchronized和ReentLock有什么区别.pdf 第四题 ArrayList LinkedList Vector的区别.pdf docker讲得最...

    超级有影响力霸气的Java面试题大全文档

    HashMap是Hashtable的轻量级实现(非线程安全的实现),他们都完成了Map接口,主要区别在于HashMap允许空(null)键值(key),由于非线程安全,效率上可能高于Hashtable。 HashMap允许将null作为一个entry的key或者...

    笔试Java2考试.doc

    + Vector:基于动态数组的实现,线程安全,查找效率高,但插入和删除效率低 + LinkedList:基于链表的实现,插入和删除效率高,但查找效率低 * 对集合内的对象进行排序,可以使用Collections.sort()方法或自定义...

    C#及.Net经典面试题目及答案

    - **线程安全性**: HashMap是非线程安全的,而Hashtable是线程安全的。 - **空键值**: HashMap允许键值为空,而Hashtable不允许。 - **性能**: HashMap通常比Hashtable性能更高。 #### 11\. Collection与...

    大厂的Android面试题.pdf

    - HashMap不支持多线程安全操作,而ConcurrentHashMap通过锁分离技术实现了线程安全。 18. **BroadcastReceiver与LocalBroadcastReceiver区别** - BroadcastReceiver用于接收来自系统或其他应用的广播。 - ...

    出现java.util.ConcurrentModificationException 问题及解决办法

    这个异常的产生是由于集合类(如HashMap)的非线程安全特性,当你在一个线程中使用迭代器遍历集合,而另一个线程在同时修改这个集合时,就会触发此异常。下面我们将深入探讨这个问题的原因、示例代码以及解决策略。 ...

    50例经典C#、.Net经典面试题 pdf版本

    - **线程安全性**: `HashMap`是非线程安全的,而`Hashtable`是线程安全的。 - **空值支持**: `HashMap`允许键和值为null,而`Hashtable`不允许。 #### 11. Collection与Collections的区别 - **Collection**: 是...

    藏经阁-Java开发手册(泰山版)灵魂13问-117.pdf

    SimpleDateFormat不是线程安全的,将其声明为static可能导致多线程环境下的数据不一致和同步问题。应为每个线程实例化一个SimpleDateFormat对象,或使用线程安全的日期格式化工具。 9. **禁止使用isSuccess作为...

    IT职场:程序员Java面试中的陷阱

    他们可能会给出一个实际问题,让你现场设计解决方案,或者讨论你在过去项目中遇到的难题及其解决办法。这时,清晰的逻辑思维、良好的沟通技巧以及实战经验显得尤为重要。 总之,Java面试涵盖了广泛的领域,从基础...

    java面试要点

    线程的生命周期和线程安全问题,特别是volatile和synchronized的实现原理,synchronized与lock的区别,以及CAS乐观锁、ABA问题和乐观锁的业务场景都是面试中经常会被问到的。 在数据存储方面,需要了解MySQL索引...

    银海软件java面试题

    而 `HashMap` 不是线程安全的,它没有同步操作。 - **null 值和 null 键**:`Hashtable` 不允许插入 `null` 键或 `null` 值;而 `HashMap` 允许插入 `null` 键和 `null` 值,但只能插入一个 `null` 键。 - **性能**...

    java面试宝典

    125、如何执行一个线程安全的JSP? 31 126、JSP如何处理HTML FORM中的数据? 31 127、在JSP如何包含一个静态文件? 32 128、在JSP中如何使用注释? 32 129、在JSP中如何执行浏览重定向? 32 130、如何防止在JSP或SERVLET...

    Google_开源项目_Gson教程.pdf

    3. **注意线程安全**:Gson实例本身不是线程安全的,如果在多线程环境中使用,应该创建一个单例。 通过上述知识点的学习,我们可以快速掌握Gson的基本使用,并能应对大部分实际开发中的JSON处理需求。

    开源bbs源码java-interview-note:面试题总结

    HashMap数据结构、扩展策略,Hash冲突攻击如何防范,如何实现线程安全的HashMap? JVM内存结构,GC算法,CMS、G1的原理 NIO模型,select/epoll的区别,多路复用的原理 Java中一个字符占多少个字节,扩展再问int, ...

Global site tag (gtag.js) - Google Analytics