`

JDK源代码学习系列一---java.util(2)

    博客分类:
  • Java
阅读更多
前一篇 JDK源代码学习系列一---java.util(1):http://www.iteye.com/topic/905329

       就目前看来,上一篇有点标题党的味道,源代码学习却没有一句JDK源代码,把大家都骗进来了,为了改过自新,哥现在开始要贴源代码了。我相信我要讲的,我所看到的,很多jer都知道的比我深刻,有同学已经在回复中贴出了部分源码,但是我的学习我得自己过一遍。所以我们接下去是讨论,我说我的,各位大大们觉得我理解有误的地方可以用砖头拍我。
       继续来学习HashMap。
       首先,我们来看下什么叫hash。百度有如下解释,参考性拿来使用:
       “Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。”
       接着,我们来看一下HashMap的一些结构。HashMap是存储key-value键值对的,即Entry。宏观上来说它底层是一个Entry的数组。
    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table;

       但是,Entry并不是简单纯粹的键值对,它的结构如下:
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
...

       重点请关注Entry<K,V> next;,这个让人想到的是链表。
       为了能形象的看到整个HashMap的结构,哥从百度上找了张HashMap的结构图(如有侵权行为,请通知本人,请勿直接投隐藏...):



       可见table这个数组存储的并非是单纯的键值对,实际存储的是链表,而每一个Entry的next将指向该链表的下一个元素。那为什么在这个地方需要链表的结构呢?
       我们来看一下HashMap的put方法:
     /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        //如果key为null,则调用putForNullKey(value),由此可见HashMap支持null为key
        if (key == null)
            return putForNullKey(value);
        //获取key的hash值
        int hash = hash(key.hashCode());
        //由此可见新元素插入HashMap的位置将由其hash值决定,所以通过hash值和table长
        //度算出该key的hash值所对应的table数组索引i。
        int i = indexFor(hash, table.length);
        //遍历table[i]这个位置的链表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //如果hash值与key都相同,表明该链表中已存在该key的entry,则更新该entry的value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //若程序走到这里,table[i]处尚没有该key对应的entry,插入entry
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

    ......

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

    /**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        //插入链表头部
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }
     


     获取hash值需要使用哈希算法,但是通过上文Hash解释的红色字体部分“不同的输入可能会散列成相同的输出”可以得知,哈希算法可能会出现不同的key得到重复的hash值,这就是hash冲突。这样的entry都会被插入到table的i处,为了不覆盖不同的key的entry,多个hash值相同的key的entry就会被按照链表的结构串接起来。
     到这里,我希望我讲清楚了HashMap的结构与其成因。

     现在,我们来看看上一篇中留下的问题。
    
     首次插入p1,p2的时候,p1与p2的hash值不同,所以插入后的结构应该如下:

     可见key为p1,p2的hash值得到分别为x,y,根据indexFor方法得到该插入table的索引值分别为m,n。因此entry分别被插入到table的索引m,n处。但是后来p2的id被修改了,因为entry中的key虽然是final的,但它只是一个引用,实例对象还是可以被修改的。一旦p2的id被修改,根据Person类重写的hashcode方法,其重新计算得到的hash值也将改变。因为将p2的id改为了与p1相同,所以重新计算得到p2的hash值与p1相同,都为x。我们来看一下HashMap的get方法:
    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        //重新计算key的hash值,此时p2与p1的hash值相同
        int hash = hash(key.hashCode());
        //此处的循环并不是一key对应多个value的循环,而是通过重新计算得到key的hash值
        //找出该key所对应的entry在table数组中的链表所在的索引,然后遍历相同hash的
        //entry链表找到目标key,并返回该key对应的value
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

     因为此时在n位置的p2对应的entry中的hash是final字段,在插入时就已经固定,所以重新计算得到hash并不会更新,且该链表结构也不会改变。p2对应的entry还在老位置,但是通过get(p2)等效于get(p1),因为他们的hash值相同。所以虽然出现了一键对应多个value的情况,但实际上不论通过get(p1)还是get(p2)只能找到m处的entry了。
     那么现在你会想到,既然p2对应的entry还在老位置,我有什么方法可以重新找到这个entry呢。如果我给你两种方案:
     1.将p2的id改回去,然后通过m.get(p2):
 ......
 
 p2.setId("2");

 ......

     2.新建一个p3,把p3的id设为"2",即跟原来的p2相同,然后直接通过m.get(p3):
      ......
      Person p3 = new Person();
      p3.setName("name3");
      ......
      System.out.println("Map m 通过get方法用key p3:"+p3+"时,获取的value:"+m.get(p3));

    大家觉得两种结果分别会怎样呢?原因又是什么?


   

    
  • 大小: 12.5 KB
  • 大小: 13 KB
分享到:
评论
6 楼 liuxuejin 2011-03-08  
没有说hashmap里面对hashcode进行hash的函数的作用,注释我看不明白
5 楼 chenyong0214 2011-02-19  
不可否认写的非常好!
4 楼 sepac 2011-02-17  
顶一个!没看过源码的路过!希望楼主继续!Java新手天天有!需要你的帮助!
3 楼 kingkan 2011-02-16  
kakaluyi 写道
链表为了解决哈希冲突,还有一种方式是再hash,但是jdk里面用到的是链表法来解决hash冲突的问题


再hash的话,不如链表快了。
2 楼 kakaluyi 2011-02-16  
链表为了解决哈希冲突,还有一种方式是再hash,但是jdk里面用到的是链表法来解决hash冲突的问题
1 楼 superobin 2011-02-16  
第一种做法肯定没问题,就当没改过呗
第二种做法除非p2 equals p3 ,否则肯定拿不出来。

相关推荐

    jetty-util-8.1.8.v20121106-API文档-中文版.zip

    赠送源代码:jetty-util-8.1.8.v20121106-sources.jar; 赠送Maven依赖信息文件:jetty-util-8.1.8.v20121106.pom; 包含翻译后的API文档:jetty-util-8.1.8.v20121106-javadoc-API文档-中文(简体)版.zip; Maven...

    backport-util-concurrent-3.1.jar

    backport-util-concurrent-3.1.jar是一个Java库,它提供了一些并发工具类,用于简化多线程编程。这个库包含了许多实用的工具类,如`FutureTask`、`CountDownLatch`、`Semaphore`等,这些工具类可以帮助开发者更好地...

    javajdk源码-java.util_source_learning:学习JDK源代码

    java jdk源码jdk_source_learning 学习JDK源代码

    java-swing管理系统毕业设计源码-学生信息管理(文档+视频+源码)-计算机毕业设计源代码.rar

    这款Java swing实现的学生信息管理系统和jsp版本的功能很相似,简单的实现了班级信息的增删改查,学生信息的增删改查,数据库采用的是mysql,jdk版本不限,是Java学习者学习参考非常好的一个小项目,下面我们来看看...

    javajdk1.8源码-Java-source-reading:jdk1.8源代码分析

    近期计划:以jdk为主,java.lang和java.util下一些重要的类以及juc,将来可能会写web框架相关 jdk1.8 java.lang Integer String java.util Arrays ArrayList LinkedList HashMap HashSet LinkedHashMap

    [Java参考文档].JDK_API 1.6

    java.sql 提供使用 JavaTM 编程语言访问并处理存储在数据源(通常是一个关系数据库)中的数据的 API。 java.text 提供以与自然语言无关的方式来处理文本、日期、数字和消息的类和接口。 java.text.spi java.text ...

    java jdk实列宝典 光盘源代码

    java为数据结构中的列表定义了一个接口类java.util.list同时提供了3个实现类,分别是ArrayList、Vector、LinkedList使用; 生成不重复的随机数序列;列表、集合与数组的互相转换;java为数据结构中的映射定义一个接口...

    数据库增删改查的源代码

    非常实用的数据库增删改查的源代码; DB.java package com.util; import java.sql.Connection; import java.sql.DriverManager; import java.sql.PreparedStatement; import java.sql.ResultSet; import ...

    SM4加解密代码参考.java

    源代码 需要的jar :SM4Util.jar 和bcprov-jdk15on-1.60.jar SM4Util.jar 可以本人上传的资源下载

    java api最新7.0

    java.sql 提供使用 JavaTM 编程语言访问并处理存储在数据源(通常是一个关系数据库)中的数据的 API。 java.text 提供以与自然语言无关的方式来处理文本、日期、数字和消息的类和接口。 java.text.spi java.text ...

    spring-hibernate-dwr实例

    spring-hibernate-dwr做的AJAX操作CRUD实例 环境:myeclipse6.0+jdk1.6 所需lib列表,请自行加入 mysql-connector-java-3.1.7-bin.jar antlr-2.7.6rc1.jar asm-attrs.jar cglib-2.1.3.jar ...

    Java学习笔记7.0

    《Java JDK6学习笔记》是作者良葛格本人近几年来学习Java的心得笔记,结构按照作者的学习脉络依次展开,从什么是Java、如何配置Java开发环境、基本的Java语法到程序流程控制、管理类文件、异常处理、枚举类型、泛型...

    Java 1.6 API 中文 New

    java.sql 提供使用 JavaTM 编程语言访问并处理存储在数据源(通常是一个关系数据库)中的数据的 API。 java.text 提供以与自然语言无关的方式来处理文本、日期、数字和消息的类和接口。 java.text.spi java.text ...

    java JDK5.0 实例开发宝典

    Jdk5.0 源代码使用说明 &lt;br&gt;1. 类型基本操作 2. 面向对象的操作 适配器模式 单列模式 工程模式 组合模式。。。 3. 精确计算数字和随机数字 4. java.util.package高级使用 List Set collection.. 5. ...

    javaapi和源码-javase_review:回顾JavaSE深入了解源代码,并实现JDKAPI。源代码分析文章可以找到@我的博客

    java api和源码 javase_review review java SE deeping with source code,and implements the JDK API. the source code analyse articles can find @my blog 参考资料: 视频: 【1】. 刘意JavaSE视频--【主导】 ...

    [Java参考文档]

    java.sql 提供使用 JavaTM 编程语言访问并处理存储在数据源(通常是一个关系数据库)中的数据的 API。 java.text 提供以与自然语言无关的方式来处理文本、日期、数字和消息的类和接口。 java.text.spi java.text ...

    贪吃蛇java课程设计--贪吃蛇程序设计.doc

    " 沈 阳 大 学 课程设计说明书 NO.4 "2.4设计的源代码 " "import java.awt.*; " "import java.awt.event.*; " "import javax.swing.*; " "import java.util.*; " "public class GreedSnake implements KeyListener ...

    JDK1.8:阅读和注释JDK源代码-jdk1.8 source code

    JDK1.8 介绍 JDK原始阅读,注释 文件开头的备注,是关于此类的重点或关键问题 ///开头或/\*/开头的注释,是阅读过程中添加的 内容 java.util.concurrent 质量管理体系 收藏 java.util.stream java.util.function ...

    JDK_1_6 API

    java.sql 提供使用 JavaTM 编程语言访问并处理存储在数据源(通常是一个关系数据库)中的数据的 API。 java.text 提供以与自然语言无关的方式来处理文本、日期、数字和消息的类和接口。 java.text.spi java.text ...

    java打包源码-ga-ref-impl:www.geometricalgebra.net打包了Java源代码以使用常见的Maven/Java

    在Linux上使用Java7和Maven2进行了测试 只要您已经通过Java7(JDK,而不仅仅是JRE!您需要编译器!),Maven就会简化编译和构建软件的过程。 Maven首先将这个几何代数代码“ colt”线性代数库作为依赖项,下载...

Global site tag (gtag.js) - Google Analytics