首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

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

2012-11-01 
java中HashCode的作用和Map的实现结构Map 是一种数据结构,用来实现key和value 的映射。通过Key可以找到Valu

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的类。

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

1 楼 lovejavaei 2009-06-28   理解的还不够深入,再往下研究,会有更多的收获 2 楼 liu0107613 2009-06-28   非常感谢楼主的支持,刚开始研究这方面,很多方面的知识还需要学习,请楼主多多包涵。
我会继续努力的。。。。 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>

热点排行