java中HashCode的作用和Map的实现结构

Map 是一种数据结构，用来实现key和value 的映射。通过Key可以找到Value。实现类包括

HashMap，LinkedHashMap，TreeMap

 

 

    /**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
     */
    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);
    }

 

    /**
     * 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) {
        if (key == null)
            return putForNullKey(value);
        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;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

 

 

HashMap 是以数组的结构，用哈希函数值跟数组的长度做位与运算，获取对应数组的索引。浏览key值时，不保证顺序。
LinkedHashMap 是以双向列表的结构做实现的，浏览key值时候，可以保证顺序。LinkedHashMap继承HashMap ，不同的是数据存储结构。

TreeMap 是以二叉树实现的Map接口。Map中的key值按照从小到大的顺序排列。key要实现comparable

 TreeMap  是用二叉树结构存储的，根据key找value的时间复杂度是o(以2为底，n的对数）

查找和插入的性能都没有hashmap好，但是可以实现key的有序存放。所以增加了hashMap的类。

二叉树的中序遍历就是从小到大的顺序排列。

评论

3 楼 mycigar 2009-07-01  

<div class="quote_title">liu0107613 写道</div>
<div class="quote_div">
<p>Map 是一种数据结构，用来实现key和value 的映射。通过Key可以找到Value。实现类包括</p>
<p>HashMap，LinkedHashMap，TreeMap </p>
<p> </p>
<p> </p>
<p>    /**<br>     * Applies a supplemental hash function to a given hashCode, which<br>     * defends against poor quality hash functions.  This is critical<br>     * because HashMap uses power-of-two length hash tables, that<br>     * otherwise encounter collisions for hashCodes that do not differ<br>     * in lower bits. Note: Null keys always map to hash 0, thus index 0.<br>     */<br>    static int hash(int h) {<br>        // This function ensures that hashCodes that differ only by<br>        // constant multiples at each bit position have a bounded<br>        // number of collisions (approximately 8 at default load factor).<br>        h ^= (h &gt;&gt;&gt; 20) ^ (h &gt;&gt;&gt; 12);<br>        return h ^ (h &gt;&gt;&gt; 7) ^ (h &gt;&gt;&gt; 4);<br>    }</p>
<p> </p>
<p> </p>
<p>    /**<br>     * Returns index for hash code h.<br>     */<br>    static int indexFor(int h, int length) {<br>        return h &amp; (length-1);<br>    }</p>
<p> </p>
<p>    /**<br>     * Associates the specified value with the specified key in this map.<br>     * If the map previously contained a mapping for the key, the old<br>     * value is replaced.<br>     *<br>     * @param key key with which the specified value is to be associated<br>     * @param value value to be associated with the specified key<br>     * @return the previous value associated with &lt;tt&gt;key&lt;/tt&gt;, or<br>     *         &lt;tt&gt;null&lt;/tt&gt; if there was no mapping for &lt;tt&gt;key&lt;/tt&gt;.<br>     *         (A &lt;tt&gt;null&lt;/tt&gt; return can also indicate that the map<br>     *         previously associated &lt;tt&gt;null&lt;/tt&gt; with &lt;tt&gt;key&lt;/tt&gt;.)<br>     */<br>    public V put(K key, V value) {<br>        if (key == null)<br>            return putForNullKey(value);<br>        int hash = hash(key.hashCode());<br>        int i = indexFor(hash, table.length);<br>        for (Entry&lt;K,V&gt; e = table[i]; e != null; e = e.next) {<br>            Object k;<br>            if (e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k))) {<br>                V oldValue = e.value;<br>                e.value = value;<br>                e.recordAccess(this);<br>                return oldValue;<br>            }<br>        }</p>
<p>        modCount++;<br>        addEntry(hash, key, value, i);<br>        return null;<br>    }</p>
<p> </p>
<p> </p>
<p>HashMap 是以数组的结构，用哈希函数值跟数组的长度做位与运算，获取对应数组的索引。浏览key值时，不保证顺序。<br>LinkedHashMap 是以双向列表的结构做实现的，浏览key值时候，可以保证顺序。LinkedHashMap继承HashMap ，不同的是数据存储结构。</p>
<p>TreeMap 是以二叉树实现的Map接口。Map中的key值按照从小到大的顺序排列。key要实现comparable</p>
<p> </p>
</div>
<p> </p>
<p>原来看数据结构的时候，我觉得没啥大用，后来看Java的时候，发现数据结构的重要性了。</p>

2 楼 liu0107613 2009-06-28  

非常感谢楼主的支持，刚开始研究这方面，很多方面的知识还需要学习，请楼主多多包涵。
我会继续努力的。。。。

1 楼 lovejavaei 2009-06-28  

理解的还不够深入，再往下研究，会有更多的收获