`
qicen
  • 浏览: 47383 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

HashMap和ConcurrentHashMap分享

阅读更多
大家一看到这两个类就能想到HashMap不是线程安全的,ConcurrentHashMap是线程安全的。除了这些,还知道什么呢?

先看一下简单的类图:

从类图中可以看出来在存储结构中ConcurrentHashMap比HashMap多出了一个类Segment,而Segment是一个可重入锁。
ConcurrentHashMap是使用了锁分段技术技术来保证线程安全的。
锁分段技术:首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。

属性说明:
我们会发现HashMap和Segment里的属性值基本是一样的,因为Segment的本质上就是一个加锁的HashMap,下面是每个属性的意义:
table:数据存储区
size,count: 已存数据的大小
threshold:table需要扩容的临界值,等于table的大小*loadFactor
loadFactor: 装载因子
modCount: table结构别修改的次数

hash算法和table数组长度:
仔细阅读HashMap的构造方法的话,会发现他做了一个操作保证table数组的大小是2的n次方。
如果使用new HashMap(10)新建一个HashMap,你会发现这个HashMap中table数组实际的大小是16,并不是10.
为什么要这么做呢?这就要从HashMap里的hash和indexFor方法开始说了。
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);

HashMap里的put和get方法都使用了这两个方法将key散列到table数组上去。
indexFor方法是通过hash值和table数组的长度-1进行于操作,来确定具体的位置。
为什么要减1呢?因为数组的长度是2的n次方,减1以后就变成低位的二进制码都是1,和hash值做与运算的话,就能得到一个小于数组长度的数了。
那为什么对hashCode还要做一次hash操作呢?因为如果不做hash操作的话,只有低位的值参与了hash的运算,而高位的值没有参加运算。hash方法是让高位的数字也参加hash运算。
假如:数组的长度是16 我们会发现hashcode为5和53的散列到同一个位置.
hashcode:53  00000000 00000000 00000000 00110101
hashcode:5    00000000 00000000 00000000 00000101
length-1:15     00000000 00000000 00000000 00001111
只要hashcode值的最后4位是一样的,那么他们就会散列到同一个位置。
hash方法是通过一些位运算符,让高位的数值也尽可能的参加到运算中,让它尽可能的散列到table数组上,减少hash冲突。

ConcurrentHashMap的初始化:
仔细阅读ConcurrentHashMap的构造方法的话,会发现是由initialCapacity,loadFactor, concurrencyLevel几个参数来初始化segments数组的。
segmentShift和segmentMask是在定位segment时的哈希算法里需要使用的,让其能够尽可能的散列开。
initialCapacity:ConcurrentHashMap的初始大小
loadFactor:装载因子
concurrencyLevel:预想的并发级别,为了能够更好的hash,也保证了concurrencyLevel的值是2的n次方
segements数组的大小为concurrencyLevel,每个Segement内table的大小为initialCapacity/ concurrencyLevel

ConcurrentHashMap的put和get
        int hash = hash(key.hashCode());
        return segmentFor(hash).get(key, hash);

可以发现ConcurrentHashMap通过一次hash,两次定位来找到具体的值的。
先通过segmentFor方法定位到具体的Segment,再在Segment内部定位到具体的HashEntry,而第二次在Segment内部定位的时候是加锁的。
ConcurrentHashMap的hash算法比HashMap的hash算法更复杂,应该是想让他能够更好的散列到数组上,减少hash冲突。

HashMap和Segment里modCount的区别:
modCount都是记录table结构被修改的次数,但是对这个次数的处理上,HashMap和Segment是不一样的。
HashMap在遍历数据的时候,会判断modCount是否被修改了,如果被修改的话会抛出ConcurrentModificationException异常。
Segment的modCount在ConcurrentHashMap的containsValue、isEmpty、size方法中用到,ConcurrentHashMap先在不加锁的情况下去做这些计算,如果发现有Segment的modCount被修改了,会再重新获取锁计算。

HashMap和ConcurrentHashMap的区别:
如果仔细阅读他们的源码,就会发现HashMap是允许插入key和value是null的数据的,而ConcurrentHashMap是不允许key和value是null的。这个是为什么呢?ConcurrentHashMap的作者是这么说的:
The main reason that nulls aren't allowed in ConcurrentMaps (ConcurrentHashMaps, ConcurrentSkipListMaps) is that ambiguities that may be just barely tolerable in non-concurrent maps can't be accommodated. The main one is that if map.get(key) returns null, you can't detect whether the key explicitly maps to null vs the key isn't mapped. In a non-concurrent map, you can check this via map.contains(key), but in a concurrent one, the map might have changed between calls.

为什么重写了equals方法就必须重写hashCode方法呢?
绝大多数人都知道如果要把一个对象当作key使用的话,就需要重写equals方法。重写了equals方法的话,就必须重写hashCode方法,否则会出现不正确的结果。那么为什么不重写hashCode方法就会出现不正确结果了呢?这个问题只要仔细阅读一下HashMap的put方法,看看它是如何确定一个key是否已存在的就明白了。关键代码:
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        V oldValue = e.value;
        e.value = value;
        e.recordAccess(this);
        return oldValue;
    }
}

首先通过key的hashCode来确定具体散列到table的位置,如果这个位置已经有值的话,再通过equals方法判断key是否相等。
如果只重写equals方法而不重写hashCode方法的话,即使这两个对象通过equals方法判断是相等的,但是因为没有重写hashCode方法,他们的hashCode是不一样的,这样就会被散列到不同的位置去,变成错误的结果了。所以hashCode和equals方法必须一起重写。

  • 大小: 80.7 KB
分享到:
评论

相关推荐

    java7-8中的 HashMap和ConcurrentHashMap全解析.pdf

    在Java 7和8中,HashMap和ConcurrentHashMap是两种重要的数据结构,分别用于非线程安全和线程安全的键值对存储。本篇文章将深入解析这两种数据结构的内部实现,帮助读者理解它们的工作原理。 HashMap是Java中最常用...

    HashMap&ConcurrentHashMap.key

    HashMap& ConcurrentHashMap 深度解析

    java7-8中的 HashMap和ConcurrentHashMap全解析

    在Java编程语言中,`HashMap`和`ConcurrentHashMap`是两种非常重要的数据结构,它们都属于`java.util`包,用于存储键值对。本文将深入解析这两个类在Java 7和8版本中的实现原理、特点以及使用场景。 首先,`HashMap...

    HashMap与ConcurrentHashMap面试要点.pdf

    ### HashMap和ConcurrentHashMap面试要点详解 #### HashMap面试要点 ##### HashMap底层数据结构 **JDK7与JDK8的差异:** - **JDK7的HashMap**底层是由数组+链表构成的。在JDK7中,链表采用头插法(head-...

    详谈HashMap和ConcurrentHashMap的区别(HashMap的底层源码)

    HashMap和ConcurrentHashMap的区别 HashMap和ConcurrentHashMap是Java语言中两个常用的哈希表实现,它们都继承自AbstractMap类,实现了Map接口,但是它们之间存在着一些关键的区别。 首先,从数据结构上讲,...

    ConcurrentHashmap源码

    源码分析见我博文:http://blog.csdn.net/wabiaozia/article/details/50684556

    2.Java7_8+中的+HashMap+和+ConcurrentHashMap+全解析1

    在Java编程语言中,HashMap和ConcurrentHashMap是两种常用的散列表数据结构,主要用于存储键值对。本文将对这两个类在Java 7和8中的实现进行深入解析,尤其是它们在并发环境下的行为和优化。 首先,我们来看Java 7...

    HashMap,HashTable,ConcurrentHashMap之关联.docx

    HashMap,HashTable,ConcurrentHashMap 之关联 HashMap、HashTable、ConcurrentHashMap 是 Java 集合类中的重点,以下是对它们的详细解释: HashMap HashMap 是非线程安全的,它的键和值都允许有 null 值存在。...

    史上最详细详解hashmap、concurrenthashmap

    HashMap 和 ConcurrentHashMap 是 Java 中两种广泛使用的 Map 实现,它们都在 Java 的 Collections 框架中扮演着重要角色。HashMap 是非线程安全的,而 ConcurrentHashMap 是线程安全的,这使得后者在多线程环境下...

    Java集合相关面试题

    Java集合相关面试题是Java开发中非常重要的一部分,本文将对Java集合相关面试题进行总结和分析,涵盖List和Map相关的面试题,包括ArrayList、LinkedList、HashMap、ConcurrentHashMap等,并对数据结构和算法复杂度...

    java多线程并发及集合框架面试题

    本题旨在考察候选人在实际并发场景下对 HashMap 和 ConcurrentHashMap 的理解和应用。 HashMap 和 ConcurrentHashMap 的主要区别在于它们对并发操作的支持。HashMap 是非线程安全的,意味着在多线程环境中,如果不...

    hashMap和hashTable的区别

    ### hashMap和hashTable的区别 #### 一、简介与基本概念 `HashMap` 和 `HashTable` 都是 Java 集合框架中非常重要的数据结构,它们都实现了 `Map` 接口,用于存储键值对。尽管它们在功能上有很多相似之处,但在...

    一文让你彻底理解JavaHashMap和ConcurrentHashMap

    Java中的HashMap和ConcurrentHashMap是两种非常重要的数据结构,它们都是Map接口的实现,用于存储键值对数据。HashMap是非线程安全的,而ConcurrentHashMap则是为多线程环境设计的线程安全版本。 HashMap在Java 1.7...

    16 解析HashMap.txt

    HashMap、ConcurrentHashMap源码级解读,并且对比了JDK7和8实现的不同,进行了大量的解释,结合了多个学习视频

    经典讲解List和ArrayList和Vector和HashTable和HashMap区别

    在Java编程语言中,集合框架是处理对象数组的重要工具,其中`List`、`ArrayList`、`Vector`、`HashTable`和`HashMap`是五个关键的接口和类,它们各有不同的特性和用途。以下是这些概念的详细解释: 1. **List接口**...

    hashmap面试题_hashmap_

    答:在多线程环境下,可以使用ConcurrentHashMap,它是线程安全的HashMap实现。 五、HashMap与HashSet的关系 HashSet基于HashMap实现,每个元素作为HashMap的一个键,值为null。因此,HashSet的操作性能也依赖于...

    Java里多个Map的性能比较(TreeMap、HashMap、ConcurrentSkipListMap)

    在Java编程中,Map接口是用于存储键值对的数据结构,而Java提供了多种Map的实现,包括TreeMap、HashMap和ConcurrentSkipListMap。本文主要比较了这三种Map的性能,尤其是在插入和查找操作上的效率。 1. **TreeMap**...

    蚂蚁金服 P6 面试分享.txt

    朋友准备3个月以上的的真实面试分享,绝对值; ... 3&gt; HashMap和ConcurrentHashMap的区别,以及两者的优缺点。。。。。。。。 。。。。。。。。。。。。。。。。。。。。。。。。。(详见完整版)

    Java利用ConcurrentHashMap实现本地缓存demo

    Java利用ConcurrentHashMap实现本地缓存demo; 基本功能有缓存有效期、缓存最大数、缓存存入记录、清理线程、过期算法删除缓存、LRU算法删除、获取缓存值等功能。 复制到本地项目的时候,记得改包路径哦~

Global site tag (gtag.js) - Google Analytics