JDK源代码学习系列一---java.util（1）

    好吧，我承认我比较懒~ 但是发现不把一些学习成果与工作经验记录下来，我会慢慢将它们遗忘掉，最后一无所有。新年回来，2011从今天开始重新积累吧。
    市面上的技术书籍琳琅满目，但哥坚信“有代码有真相”，所以，源代码才是最好的学习材料，先不说Java庞大的开源社区提供的充斥着各种设计模式与创新思路的框架代码，就JDK源代码本身就是一部博大精深的技术圣经。去看看jdk源代码中那些署名的@author...无一不是技术大牛，可以学习他们的代码也许是一件让人激动的事情，这也是开源所带给我们的乐趣。好吧，既然又free，又open，干嘛不去看看呢。
    首先看java.util中的HashMap与HashTable吧，这对兄弟在各种java面试题中老是被提及，以前只看过面试题答案中的异同点罗列，但是其内部实现及一些特点却未曾深究。个人觉得看源代码不能像看小说那样毫无目的的从头看下来，可以先给自己准备几个问题，做些猜测，然后再去看实现，这样更有针对性。好吧，哥给本次学习准备了几个给自己的问题。
    就先从HashMap开始吧。

    新建一个Person类：

package com.emsn.crazyjdk.java.util;

/**
 * “人”类，重写了equals和hashcode方法...,以id来区分不同的人，你懂的...
 * 
 * @author emsn1026
 *
 */

public class Person {
	
	/**
	 * 身份id
	 */
	private String id;
	
	/**
	 * 姓名
	 */
	private String name;

	public String getId() {
		return id;
	}

	public void setId(String id) {
		this.id = id;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((id == null) ? 0 : id.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Person other = (Person) obj;
		if (id == null) {
			if (other.id != null)
				return false;
		} else if (!id.equals(other.id))
			return false;
		return true;
	}

	@Override
	public String toString() {
		return "Person [id=" + id + ", name=" + name + "]";
	}
	
}

    现在，同样id的人会被认为是同样的实例...当然，不同id的即使姓名相同也是不同的人，那当把这个Person类的实例作为HashMap的key时，key的唯一性将通过people实例的id
来控制。

package com.emsn.crazyjdk.java.util;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

import com.emsn.crazyjdk.java.util.Person;

/**
 * @author emsn1026
 *
 */
public class MapTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
			Map m = new HashMap();
			Person p1 = new Person();
			Person p2 = new Person();
			
			p1.setId("1");
			p1.setName("name1");
			p2.setId("1");
			p2.setName("name2");
					
			m.put(p1, "person1");
			m.put(p2, "person2");
			
			System.out.println("Map m's size :" + m.size());
			
			for(Object o :m.entrySet()){
				Entry e = (Entry)o;
				System.out.println("key:"+ e.getKey());
				System.out.println("value:"+ e.getValue());
			}
			
		}

}

打印的结果是
Map m's size :1
key:Person [id=1, name=name1]
value:person2

可见key已存在，value被覆盖，这个结果可以预测。那么接下来我们把代码修改下：

package com.emsn.crazyjdk.java.util;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

import com.emsn.crazyjdk.java.util.Person;

/**
 * @author emsn1026
 *
 */
public class MapTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
			Map m = new HashMap();
			Person p1 = new Person();
			Person p2 = new Person();
			
			p1.setId("1");
			p1.setName("name1");
			p2.setId("2");
			p2.setName("name2");
					
			m.put(p1, "person1");
			m.put(p2, "person2");

                        System.out.println("Map m's size :" + m.size());
			
			p2.setId("1");
			
			System.out.println("Map m's size :" + m.size());
			
			for(Object o :m.entrySet()){
				Entry e = (Entry)o;
				System.out.println("key:"+ e.getKey());
				System.out.println("value:"+ e.getValue());
			}
			
		}

}

    此处的变化是将p1,p2的id设成不同，然后都作为key插入map,因为两个key不相同，所以我们的预测是都可以插入，此时map的size应该为2，待插入后我们修改p2的id为1，即与p1相同，这样就造成了两个entry的key相同的情况，测试再查看map的结构，看看是不是还是刚才插入的两项。
    此时我们不知道HashMap的内部实现，所以我们不知道它的实例会不会在数据插入后还继续维持key的唯一性。
    我们可以猜测的是三种答案：
    1.抛出异常，不允许修改p2的id与p1相同，维护key的唯一性；
    2.可以修改，但根据某种算法删除p1或p2中的一项，也能起到维护key的唯一性；
    3.可以修改，没有任何事情发生....两项id相同的person实例并存于map中，即存在同一个key对应了两个value。

    那么各位在没尝试并且没有查看过HashMap的源代码时会做出怎样的选择呢？

    好，我们跑一下程序。

    结果打印如下：

Map m's size :2
key:Person [id=1, name=name2]
value:person2
key:Person [id=1, name=name1]
value:person1

    那么是预测的第三种情况...这原本不是我最看好的答案..这样我就有一个疑问了，既然可以有两个相同的key对应不同的value存在，那么我通过这个key应该拿到的value是哪个呢？在上述代码的main方法末尾加入以下两行代码:

...

System.out.println("Map m 通过get方法用key p1:"+p1+"时,获取的value:"+m.get(p1));
System.out.println("Map m 通过get方法用key p2:"+p2+"时,获取的value:"+m.get(p2));
...

得到的结果如下：

Map m 通过get方法用key p1:Person [id=1, name=name1]时,获取的value:person1
Map m 通过get方法用key p2:Person [id=1, name=name2]时,获取的value:person1

可见不论你使用p1还是p2,得到的value都是person1。

好吧，现象就先写到这里，在下一篇，我们去边看源代码，边研究这个问题。

下一篇 JDK源代码学习系列一---java.util（2）：http://www.iteye.com/topic/907293

评论

17 楼 skzr.org 2011-02-14  

<p>呵呵再补充下，摘录自我的wiki：</p>
<p> </p>
<p> </p>
<h1 id="A.2BW.2FlOjmJAZwlb.2BYxhkP2QGnUodoRluWzV-" style="font-family: sans-serif; font-size: 16px;">对于所有对象都通用的方法</h1>
<p> </p>
<ul style="font-family: sans-serif; font-size: 16px;">
<li>Object中的方法：equals,hashCode,toString,clone 和 finalize都有明确的通用约定，所以我们需要遵守，因为不少的类都是按照通用约定来工作的</li>
</ul>
<p class="line867" style="font-family: sans-serif; font-size: 16px;"> </p>
<h2 id="A.2BiYZ21g-equals.2BZfaL95B1W4iQGnUofqZbmg-" style="font-family: sans-serif; font-size: 16px;">覆盖equals时请遵守通用约定</h2>
<p> </p>
<ul style="font-family: sans-serif; font-size: 16px;">
<li>覆盖equals方法有讲究的</li>
<li>一下任意条件满足，都不应该覆盖equals<ol type="1">
<li>类的每个实例本质上都是唯一的，如：Thread</li>
<li>不关心类是否提供了“逻辑相等”的测试功能：如java.util.Random.equals</li>
<li>
<p class="line862" style="margin-top: 0.25em; margin-right: 0px; margin-bottom: 0.25em; margin-left: 0px;">超类已经覆盖了equals，并且子类认为是合适的，如：Map的equals实现继承了<a class="nonexistent" style="color: #666666; text-decoration: none;" href="http://localhost:8082/AbstractMap">?</a>AbstractMap.equals,List的equals实现继承了<a class="nonexistent" style="color: #666666; text-decoration: none;" href="http://localhost:8082/AbstractList">?</a>AbstractList的equals</p>
</li>
</ol>
</li>
<li>
<p class="line862" style="margin-top: 0.25em; margin-right: 0px; margin-bottom: 0.25em; margin-left: 0px;">类是私有的或是包级私有的，可以确定永远不会被调用equals方法： 需要覆盖equals:throw new <a class="nonexistent" style="color: #666666; text-decoration: none;" href="http://localhost:8082/AssertionError">?</a>AssertionError("不要调用我");</p>
</li>
<li>如果类有自有的“逻辑相等”就需要覆盖equals方法了</li>
<li>equals通用约定：<ol type="1">
<li>自反性：对于任何非空x,x.equals(x)==true</li>
<li>对称性：对于任何非空x、y,x.equals(y)==y.equals(x);</li>
<li>传递性：对于任何非空x、y、z,如果x.equals(y)==true、y.equals(z)==true那么x.equals(z)==true;<ol type="a">
<li>java.sql.Timestamp和java.util.Date的问题:"鉴于 Timestamp 类和上述 java.util.Date 类之间的不同，建议代码一般不要将 Timestamp 值视为 java.util.Date 的实例。Timestamp 和 java.util.Date 之间的继承关系实际上指的是实现继承，而不是类型继承。"</li>
</ol>
</li>
<li>一致性：只要x、y没有修改过，那么每次执行x.equals(y)都获得相同的结果<ol type="a">
<li>java.net.URL.equals的调用依赖于网络，每次调用它们的内在可能变化</li>
</ol>
</li>
<li>对于非空x: x.equals(null)==false</li>
</ol>
</li>
<li>高质量的equals方法<ol type="1">
<li>使用==检查参数是否为这个对象的引用：if (o == this) return true;</li>
<li>instance of进行类型检查</li>
<li>把参数转化为正确的类型</li>
<li>每个关键域检查它们是否匹配<ol type="a">
<li>非float和double的基本类型直接==比较</li>
<li>float使用Float.compare比较</li>
<li>double使用Double.compare比较</li>
<li>对于对象引用直接调用equals比较</li>
<li>如果是数组域，如果每个元素都是关键域，那么每一个都要比较，jdk1.5后可以通过Arrays.equals解决</li>
</ol>
</li>
<li>注意比较顺序带来的性能影响：最易变的先比较</li>
<li>写完equals问问：是否对称、传递、一致<ol type="a">
<li>覆盖equals时总要覆盖hashCode</li>
<li>不要企图让equals过于智能</li>
<li>不要讲equals中的参数替换为其他类型，这不是覆盖而是重载,所以需要@Override注解</li>
</ol>
</li>
</ol>
</li>
</ul>
<p class="line867" style="font-family: sans-serif; font-size: 16px;"> </p>
<h2 id="A.2BiYZ21g-equals.2BZfZgO4mBiYZ21g-hashCode" style="font-family: sans-serif; font-size: 16px;">覆盖equals时总要覆盖hashCode</h2>
<p> </p>
<ul style="font-family: sans-serif; font-size: 16px;">
<li>hashCode 的常规协定是：<ol type="1">
<li>在 Java 应用程序执行期间，在对同一对象多次调用 hashCode 方法时，必须一致地返回相同的整数，前提是将对象进行 equals 比较时所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行，该整数无需保持一致。</li>
<li>如果根据 equals(Object) 方法，两个对象是相等的，那么对这两个对象中的每个对象调用 hashCode 方法都必须生成相同的整数结果。</li>
<li>如果根据 equals(java.lang.Object) 方法，两个对象不相等，那么对这两个对象中的任一对象上调用 hashCode 方法不 要求一定生成不同的整数结果。但是，程序员应该意识到，为不相等的对象生成不同整数结果可以提高哈希表的性能。</li>
</ol>
</li>
<li>hashCode生成简单办法：计算所有的关键域，排除可由其他关键域计算得到的域<ol type="1">
<li>把非0的常数值保存到result中，如17</li>
<li>对于每一个关键域f（equals中涉及的每个域），完成以下步骤：<ol type="a">
<li>为该域计算int型散列码c:<ol type="i">
<li>boolean return f?1:0</li>
<li>byte、char、sort或int return f;</li>
<li>
<p class="line862" style="margin-top: 0.25em; margin-right: 0px; margin-bottom: 0.25em; margin-left: 0px;">long return (int)(f^(f&gt;&gt;&gt;32))</p>
</li>
<li>float return Float.floatToIntBits(f)</li>
<li>double return Double.doubleToLongBits(f)再作为long型来计算散列值</li>
<li>引用对象return null?0:f.hasCode();</li>
<li>如果是数组，递归处理每一个元素</li>
</ol>
</li>
<li>合并result = 31 * result + c</li>
</ol>
</li>
</ol>
</li>
</ul>

16 楼 skzr.org 2011-02-14  

<div class="quote_title">emsn 写道</div>
<div class="quote_div">
<div class="quote_title">youjianbo_han_87 写道</div>
<div class="quote_div">1. 先鄙视下论坛规则，我好久没上了，竟然要回答什么尿尿问题。<br>2. 贴出 JDK1.5_update_22中 HashMap的 get方法的源码：<br>/**<br>     * Returns the value to which the specified key is mapped in this identity<br>     * hash map, or &lt;tt&gt;null&lt;/tt&gt; if the map contains no mapping for this key.<br>     * A return value of &lt;tt&gt;null&lt;/tt&gt; does not &lt;i&gt;necessarily&lt;/i&gt; indicate<br>     * that the map contains no mapping for the key; it is also possible that<br>     * the map explicitly maps the key to &lt;tt&gt;null&lt;/tt&gt;. The<br>     * &lt;tt&gt;containsKey&lt;/tt&gt; method may be used to distinguish these two cases.<br>     *<br>     * @param   key the key whose associated value is to be returned.<br>     * @return  the value to which this map maps the specified key, or<br>     *          &lt;tt&gt;null&lt;/tt&gt; if the map contains no mapping for this key.<br>     * @see #put(Object, Object)<br>     */<br>    public V get(Object key) {<br> if (key == null)<br>     return getForNullKey();<br>        int hash = hash(key.hashCode());<br>        for (Entry&lt;K,V&gt; e = table[indexFor(hash, table.length)];<br>             e != null;<br>             e = e.next) {<br>            Object k;<br>            if (e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k)))<br>                return e.value;//--关键在这里。<br>        }<br>        return null;<br>    }<br><br>通过代码可以得知，如果一个Key对应2个Value，看到注释的部分吗？ 他按顺序找到后，直接就 Return a.value了。而不会循环Person2.</div>
<br><img src="/images/smiles/icon_arrow.gif" alt=""> 源代码一贴，神秘感就没了,哈哈</div>
<p><br><br>源码就是硬道理，不过[youjianbo_han_87]可能理解错了楼主的意图了，楼主是在put后，修改了key的关键域字段，人为改变了对象的hashCode和equals的行为（相对put时的状态），给我们设计提了个醒哦：key尽量使用状态不可变的类（偶一般都是Long、Integer、String做key）</p>
<p> </p>
<p><br>这是个坏的例子：既然person使用id做为关键域，逻辑上关键域就不应当再修改了，否则程序或代码行为不可预知。</p>
<p><br>呵呵，以前项目中用map做缓存，都是用的String做key，就是看中了String不可变，建议缓存key对象中这样的关键域做成了final，呵呵调用的想是坏都不行（也遇到过和楼主一样的情形，调用者重用了返回的key，搞三搞四，调试了蛮久才发现，后来基本上返回的尽量new或者clone一个对象）<br><br><strong><span style="color: #ff0000; font-size: medium;">map只认put时的key状态，put后对key修改了关键域-&gt;改变了hashCode和equals行为，当然再次get时会按照新的hashCode和equals来定位Entry了</span></strong><br></p>
<p> </p>

15 楼 bradwoo8621 2011-02-14  

IDE用的是JRE就没源码, JDK就有源码.

Java Collection包是大奖作品, 经典代码啊~~

14 楼 youjianbo_han_87 2011-02-14  

yangleilt 写道

源码在哪里看呀！！我有jdk文档，但是看到的都是相当于uml图的那种解释！没有源码呀？？

莫非你没有用IDE(Eclipse或者NetBeans)? 用IDE了，直接Ctrl+鼠标按住这个类，就会自动跳到JDK API源码了

13 楼 umeit 2011-02-14  

虽然youjianbo_han_87兄贴出了源码，但还请emsn兄把这个系列的第一课做一个总结吧。

12 楼 rocketball 2011-02-14  

emsn 写道

谢谢大家捧场，个人学习的一个记录，欢迎参加讨论，有空多去看看源代码吧。

我今天在公司看到一个同事在看Java.util。然后发现这个贴，公司在杭州

11 楼 accp001 2011-02-14  

看贴留名，这是规则

10 楼 emsn 2011-02-14  

谢谢大家捧场，个人学习的一个记录，欢迎参加讨论，有空多去看看源代码吧。

9 楼 emsn 2011-02-14  

yangleilt 写道

源码在哪里看呀！！我有jdk文档，但是看到的都是相当于uml图的那种解释！没有源码呀？？

这位同学，下下来的jdk里有源代码的压缩包，名字叫src.zip,可以解压看也可以用eclipse attach进去看，推荐后者。注意，不是jdk文档，你的文档可能是jdk用javadoc 生成的文档。

8 楼 zhangyuanjie 2011-02-14  

楼主这个很经典，重写了hashCode方法，将两个不同的Key保存在HashMap中，然后再修改Key。这样HaspMap中就能出现两个一样的Key了。
然后再取值时，你用到的p1,p2所对应的hash只能是第一个key的hash值为hash(paramObject.hashCode())，根据这个hash值，只能对应一个Entry,所以只能取出第一个值。
  public V get(Object paramObject)
  {
    if (paramObject == null)
      return getForNullKey();
    int i = hash(paramObject.hashCode());
    Entry localEntry = this.table[indexFor(i, this.table.length)];
    while (localEntry != null)
    {
      Object localObject;
      if ((localEntry.hash == i) && ((((localObject = localEntry.key) == paramObject) || (paramObject.equals(localObject)))))
        return localEntry.value;
      localEntry = localEntry.next;
    }

    return null;
  }

7 楼 emsn 2011-02-14  

youjianbo_han_87 写道

1. 先鄙视下论坛规则，我好久没上了，竟然要回答什么尿尿问题。
2. 贴出 JDK1.5_update_22中 HashMap的 get方法的源码：
/**
     * Returns the value to which the specified key is mapped in this identity
     * hash map, or <tt>null</tt> if the map contains no mapping for this key.
     * A return value of <tt>null</tt> does not <i>necessarily</i> indicate
     * that the map contains no mapping for the key; it is also possible that
     * the map explicitly maps the key to <tt>null</tt>. The
     * <tt>containsKey</tt> method may be used to distinguish these two cases.
     *
     * @param   key the key whose associated value is to be returned.
     * @return  the value to which this map maps the specified key, or
     *          <tt>null</tt> if the map contains no mapping for this key.
     * @see #put(Object, Object)
     */
    public V get(Object key) {
if (key == null)
    return getForNullKey();
        int hash = hash(key.hashCode());
        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;
    }

通过代码可以得知，如果一个Key对应2个Value，看到注释的部分吗？ 他按顺序找到后，直接就 Return a.value了。而不会循环Person2.

源代码一贴，神秘感就没了,哈哈

6 楼 yangleilt 2011-02-14  

源码在哪里看呀！！我有jdk文档，但是看到的都是相当于uml图的那种解释！没有源码呀？？

5 楼 huangfoxAgain 2011-02-14  

隐约记得key 对应的后面貌似一个 列表

4 楼 zhouxianglh 2011-02-14  

p2的id与p1相同,即修改了p1,p1已经不是之前的p1了又怎么能获取原来的value?记得HashMap是根据hashCode来作为依据存储,读取的

3 楼 youjianbo_han_87 2011-02-14  

1. 先鄙视下论坛规则，我好久没上了，竟然要回答什么尿尿问题。
2. 贴出 JDK1.5_update_22中 HashMap的 get方法的源码：
/**
     * Returns the value to which the specified key is mapped in this identity
     * hash map, or <tt>null</tt> if the map contains no mapping for this key.
     * A return value of <tt>null</tt> does not <i>necessarily</i> indicate
     * that the map contains no mapping for the key; it is also possible that
     * the map explicitly maps the key to <tt>null</tt>. The
     * <tt>containsKey</tt> method may be used to distinguish these two cases.
     *
     * @param   key the key whose associated value is to be returned.
     * @return  the value to which this map maps the specified key, or
     *          <tt>null</tt> if the map contains no mapping for this key.
     * @see #put(Object, Object)
     */
    public V get(Object key) {
if (key == null)
    return getForNullKey();
        int hash = hash(key.hashCode());
        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;
    }

通过代码可以得知，如果一个Key对应2个Value，看到注释的部分吗？ 他按顺序找到后，直接就 Return a.value了。而不会循环Person2.

2 楼 psjay 2011-02-14  

期待LZ的下篇帖子。

1 楼 yutuer 2011-02-13  

map是按照散列来找的吧,你把p2修改了之后,就相当于p1的散列了,那样map找的时候不就只能找到p1的了吗,永远都取不到p2的了