`
mabusyao
  • 浏览: 252576 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

HashMap 源码解读

    博客分类:
  • java
阅读更多
HashMap是我们在日常写代码时最常用到的一个数据结构,它为我们提供key-value形式的数据存储。同时,它的查询,插入效率都非常高。

在之前的排序算法总结里面里,我大致学习了HashMap的实现原理,并制作了一个简化版本的HashMap。 今天,趁着项目的间歇期,我又仔细阅读了Java中的HashMap的实现。

HashMap的初始化:
    public HashMap(int initialCapacity, float loadFactor)

    public HashMap(int initialCapacity)
    
    public HashMap()

    public HashMap(Map<? extends K, ? extends V> m)


initialCapacity表示了HashMap中初始的大小,loadFactor则表示每次当HashMap中的空间不够时,按什么样的比例来扩展空间。

我们来看下HashMap是怎样扩展空间的:
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

可以看到这个方法并不是public的,因此用户无法手动去调用这个方法。

变量threshod维持着HashMap下一次增长将要到达的长度。而MAXIMUM_CAPACITY则包含了最大可能长度:1 << 30。

注意,这个长度是2的倍数,我们在后面会经常看到2的幂数,事实上,HashMap规定了它的table长度只能是2的幂数,因此,即使你设置了loadFactor, 它也未必按照你的想法来增长。这点,从构造器方法里面可以看出:
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity) 
            capacity <<= 1;
    
        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
    }


可以看见capacity的构建方法,先是设置为1,然后不停的左移直到大于等于initialCapacity。

trasfer方法的实现需要好好看一下:
    private transient int contentionFlag = 0;

    void transfer(Entry[] newTable) {
        onEntry();
        try {
            transfer0(newTable);
        } finally {
            onExit();
        }
    }

       private synchronized void onEntry() {
       switch(contentionFlag) {
           case(0):    contentionFlag=1;       /* Free -> Busy */
                       break;
           case(1):    contentionFlag=2;       /* Busy -> Contended */
                                               //FALLTHRU
           case(2):    throw new ConcurrentModificationException(
                           "concurrent access to HashMap attempted by " + Thread.currentThread());
           default:    throw new RuntimeException(
                           "Unexpected contentionFlag " + contentionFlag);
        }
    }

       private synchronized void onExit() {
              int oldContentionFlag=contentionFlag;
        contentionFlag=0;
        switch(oldContentionFlag) {
            case(1):    break;                                     /* Busy -> Free */
            case(2):    throw new ConcurrentModificationException( /* Contended -> Free */
                             "concurrent access to HashMap attempted by " + Thread.currentThread());
            default:    throw new RuntimeException(
                            "Unexpected contentionFlag " + oldContentionFlag);
        }
    }

    private void transfer0(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);  
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }


首先是onentry方法, 这个方法先判断是否有其它的线程在操作该HashMap进行resize,如果没有,将contentionFlag 设为1, 如果已经有了,就设为2,表示已经有冲突了。如果已经有冲突存在了,直接抛exception。

无怪网上都说HashMap是非线程安全的,而HashTable才是线程安全的。从这个角度理解,确实是这样的。

而当onexit时,如果contentionFlag为1,则直接结束,如果为2,表示在onentry时已经有冲突,那么直接抛出excpetion。

这一部分内容非常有意思,可以在别的地方借鉴这种用法。想起来之前有人问我关于线程同步的问题,我想这个应该是个很好的解决办法,等回头看看HashTable这个号称可以支持多线程的结构之后,在综合分析一下这块内容。 而在最新版本的JDK6b17中,似乎已经去掉了该部分的代码。

而对于transfer0这个方法名,实在是太难听了。

这个方法主要是创建了一个新数组,并把旧数组里面的数据放到新数组里。这里有两个很重要的内容,我们一个一个看。

a. 链表的结构
我们已经知道了hashmap中对于相同hashcode的值,是通过链表的形式挂在数组位上面的,但当我们在做resize的时候,整个链表的顺序其实是被颠倒了。 因为是private代码,所以其实并没有对此有太多的解释。我所奇怪的是,如果不把链表的顺序颠倒的话,这段代码会很容易写,性能也会高很多,可是为什么要特意去做这件事情呢?
我曾经怀疑java中是个环状的链表,可是看代码似乎又不是。。。奇怪的东西。

b. 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);
  }


indexFor的代码里面,通过h和length-1做并操作,因为length的值永远是2的幂数(参见排序算法),因此这个方法就是对h进行取模,h % 2^p, 返回的将是h的p个最低位组成的数字。这样做究竟有什么好处呢?

最大的好处就是,对于hashcode值大于table长度的,可以将之映射到table长度以内的值。其它的,我还真没看出有什么好处。

再看hash方法,事实上,java中的HashMap并不是直接去的object的hashcode值,而是先对他进行了一个简单的调整,也就是hash这个方法。

看对于该方法的介绍,该方法保证了load因子为8,即使该hashcode使用的是将每位的值乘以一个常数。

我们知道我们常常设计hashcode的方法是,比如一个string,就把每一位取出来,乘以一个常数,通常是质数,然后相加,这样得到的hashcode,会在这里得到更好的调整。

算法导论里面是这么说的:

假设机器的字长是w,那么我们就可以选择A的值为 s/2^w, s为0到2^w之间的整数,这样s=A× 2^w 用k 乘以s,取低位,再从低位中取p位,这几位就形成了k的hash值。官方建议A可以取黄金分割0.618。

这块内容是在是太复杂了,现在我也只能深入到这一步,再继续下去也看不太懂了。 JDK的作者建议去看看程序设计艺术第三卷,可惜我连第一卷都没看完。看来是要等将来解决这个问题了。

不过有一点要提的是,这种方法只在最新版本的HashMap中才有,老版本的都是直接用了key对象的hashcode。

HashMap中的其它方法都比较常规,这里就不赘述了。值得一提的是,put方法,如果key已经存在的话,会用新的value替代旧的value,并将旧value返回,否则返回空。

最后,有一个从来没用过的关键字吸引了我:
transient volatile int modCount;

查了下书,volatile是用来处理线程同步的,这里就直接转southking的一篇博文:


我们知道,在Java中设置变量值的操作,除了long和double类型的变量外都是原子操作,也就是说,对于变量值的简单读写操作没有必要进行同步。

这在JVM 1.2之前,Java的内存模型实现总是从主存读取变量,是不需要进行特别的注意的。而随着JVM的成熟和优化,现在在多线程环境下volatile关键字的使用变得非常重要。

在当前的Java内存模型下,线程可以把变量保存在本地内存(比如机器的寄存器)中,而不是直接在主存中进行读写。这就可能造成一个线程在主存中修改了一个变量的值,而另外一个线程还继续使用它在寄存器中的变量值的拷贝,造成数据的不一致。

要解决这个问题,只需要像在本程序中的这样,把该变量声明为volatile(不稳定的)即可,这就指示JVM,这个变量是不稳定的,每次使用它都到主存中进行读取。一般说来,多任务环境下各任务间共享的标志都应该加volatile修饰。

Volatile修饰的成员变量在每次被线程访问时,都强迫从共享内存中重读该成员变量的值。而且,当成员变量发生变化时,强迫线程将变化值回写到共享内存。这样在任何时刻,两个不同的线程总是看到某个成员变量的同一个值。

Java语言规范中指出:为了获得最佳速度,允许线程保存共享成员变量的私有拷贝,而且只当线程进入或者离开同步代码块时才与共享成员变量的原始值对比。

这样当多个线程同时与某个对象交互时,就必须要注意到要让线程及时的得到共享成员变量的变化。

而volatile关键字就是提示VM:对于这个成员变量不能保存它的私有拷贝,而应直接与共享成员变量交互。

使用建议:在两个或者更多的线程访问的成员变量上使用volatile。当要访问的变量已在synchronized代码块中,或者为常量时,不必使用。

由于使用volatile屏蔽掉了VM中必要的代码优化,所以在效率上比较低,因此一定在必要时才使用此关键字。







本想单独为HashTable写一篇博文的,但是等学习完之后,觉得大部分跟HashMap是一样的,我所期待的线程同步居然仅仅是通过synchronized 来实现的。 想想还是算了,就在这里列出HashTable与HashMap的几个区别:

1. 数组的长度不必是2的倍数,而是可以为任意数值。
2. 求index的办法也便简单了:(hash & 0x7FFFFFFF) % array.length
3. 对于hash值不再做特殊处理,直接使用。

即使我对HashMap的实现方法还有疑惑,但是毫无疑虑,那些算法可以提高效率。 而在Hashtable中,这些提高效率的算法都没有了,同时,过多的sychronized定义,必然会降低performance。
分享到:
评论
2 楼 mabusyao 2015-06-30  
漠北空城 写道
请问下,你这个是JDK版本是多少呢?!


忘记了,应该是1.5左右吧。很老的版本了,新版本貌似已经改了很多。
1 楼 漠北空城 2015-06-12  
请问下,你这个是JDK版本是多少呢?!

相关推荐

    HashMap之resize()方法源码解读.docx

    HashMap之resize()方法源码解读 HashMap的resize()方法是HashMap中最核心的方法之一,该方法负责扩容HashMap的容量,以便存储更多的键值对。下面我们将对HashMap的resize()方法进行源码解读,了解其扩容机制和原理...

    HashMap、ConcurrenyHashMap源码解读

    hashmap源码解读,并且会对比JDK7和8实现的不同,已更新ConcurrentHashMap部分,且结合记录了多个视频的笔记。可以在https://blog.csdn.net/hancoder/article/details/105424922 获取最新笔记地址,下载过旧文件的...

    HashMap之put方法源码解读.docx

    HashMap 之 put 方法源码解读 HashMap 是 Java 中一种常用的数据结构,用于存储键值对。其中,put 方法是 HashMap 中最重要的方法之一,负责将键值对存储到HashMap 中。在本文中,我们将对 HashMap 的 put 方法的...

    大厂HashMap面试源码解读,适合面试、初学者的人

    大厂HashMap面试源码解读,适合面试、初学者的人,HahsMap源码解读

    (003)HashMap中红黑树TreeNode的split方法源码解读.docx

    HashMap 中红黑树 TreeNode 的 split 方法源码解读 HashMap 中红黑树 TreeNode 的 split 方法是 Java 中HashMap 的核心组件之一,负责将红黑树从旧数组转移到新数组上,并进行树链表的重新组织和优化。在本文中,...

    HashMap源码粗略解读(面试必问)

    这篇文章将对HashMap的一些核心知识点进行深入解读,特别关注于面试中常见的问题。 1. **HashMap的默认容量** HashMap的默认容量是16,这是通过构造函数中的`initialCapacity`参数指定的,如果未显式设置,则...

    (006)HashMap$TreeNode确保根节点为头节点的moveRootToFront方法源码解读.docx

    在Java的集合框架中,HashMap是一个非常重要的数据结构,它提供了高效的存储和查找元素的能力。在HashMap的实现中,为了优化性能,当链表长度达到一定阈值时,会将链表转换为红黑树(Red-Black Tree)。红黑树是一种...

    java源码解读-java-src:java源码解读

    Java源码解读是Java开发人员深入理解平台工作原理和编程模型的重要途径。在这个"java-src:java源码解读"项目中,我们可以探索Java的核心库,包括JVM(Java虚拟机)、集合框架、并发机制、I/O流、网络编程等多个关键...

    java面试题_源码解读(3题)

    在Java面试中,源码解读是一项重要的能力,它考察了开发者对Java语言底层实现的理解以及问题解决的能力。这里我们将深入探讨三道常见的Java面试题,它们涵盖了基础、并发和集合框架等方面,帮助你提升对Java源码的...

    java源码解读-JavaSource:Java源码解读

    在Java编程语言的世界里,源码解读是提升技术深度、理解内部机制的关键步骤。"JavaSource:Java源码解读"项目旨在帮助开发者深入探索Java的内部工作原理,从而更好地运用和优化代码。在这个项目中,我们可以看到一...

    Struts1.2源码解读

    Struts 1.2是该框架的一个版本,它的源码解读对于深入理解Struts的工作机制和原理至关重要。北大青鸟的这份文档是为了帮助学习者入门和精通Struts所编写的,包含了对Struts源码的详细解析。 首先,了解Struts的核心...

    java源码解读-JavaAPI:jdk源码解读分析

    本篇文章将对Java API的部分关键组件进行源码解读,帮助读者深入理解其工作原理。 1. **对象创建与内存管理**: - `Object`类:所有Java类的基类,包含了如`clone()`, `equals()`, `hashCode()`等方法。理解`...

    深入解读大厂java面试必考点之HashMap全套学习资料

    HashMap是Java编程语言中最常用的集合类之一,尤其在面试中,HashMap的相关知识是考察...这套学习资料应该包含了HashMap的实例分析、源码解读、常见面试题以及实战演练等内容,确保你全面掌握这一核心Java数据结构。

    HashMap中红黑树插入节点的调整过程.doc

    总的来说,理解HashMap中红黑树插入节点的调整过程需要深入理解红黑树的性质和旋转操作,同时熟悉HashMap源码中的编码风格和变量命名规则。通过这些知识,我们可以更好地掌握HashMap在处理大数据量时如何保持高效...

    Java相关技术总结,包括redis,MySQL,RabbitMq,面试题总结,源码解读

    源码解读是提升技术水平的重要途径。例如,深入理解HashMap和ConcurrentHashMap的实现,可以让我们更好地利用这些数据结构,避免性能瓶颈;阅读ArrayList和LinkedList的源码,有助于我们选择合适的数据结构以优化...

    Java底层知识点、源码解读,技术栈相关原理知识点、工具解读最佳实践、功能点实战,问题排查,开发技巧等

    Java作为一门广泛使用的编程语言,其底层知识点和源码解读对于深入理解并优化代码性能至关重要。本主题将探讨以下几个方面: 1. **Java虚拟机(JVM)**: JVM是Java程序运行的基础,它负责字节码的解释执行,内存...

    java源码解读-ITG-JavaBook01:Java面试高频源码解读

    《Java源码解读-ITG-JavaBook01: Java面试高频源码解读》是一部针对Java程序员面试准备的深入学习资料。在这个项目中,我们将会探索Java语言的一些核心概念和常用库的源代码,帮助开发者更好地理解Java的内部机制,...

    16 解析HashMap.txt

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

    深入解读大厂java面试必考基本功-HashMap集合配套文档代码资料

    在本套课程中,将会非常深入、非常详细、非常全面的解读HashMap以及源码底层设计的思想。从底层的数据结构到底层源码分析以及怎样使用提高HashMap集合的效率问题等进行分析。如果掌握本套课程,那么再看其他javase的...

Global site tag (gtag.js) - Google Analytics