黑马程序员技术交流社区

标题: HashMap应该是无序的,这怎么感觉在排序? [打印本页]
作者: belief丶Only    时间: 2014-1-1 22:34
标题: HashMap应该是无序的,这怎么感觉在排序?
  1. Map<Integer,String> map =new  HashMap<Integer,String>();
  2.                 map.put(5, "frj");
  3.                 map.put(4, "dfh");
  4.                 map.put(9, "sdg");
  5.                 map.put(2, "sdgsdf");
  6.                 map.put(8, "as");
  7.                
  8.                 Iterator<Integer> it = map.keySet().iterator();
  9.                 while(it.hasNext()){
  10.                         Integer key = it.next();
  11.                         String value = map.get(key);
  12.                         System.out.println(key+":"+value+"");
  13.                 }
复制代码

为什么?谁能解释一下!
打印结果是:
2:sdgsdf
4:dfh
5:frj
8:as
9:sdg
作者: 疯子的昨天    时间: 2014-1-1 23:13
因为这种取出方式是先将键存入到SET集合中，然后通过迭代器取出值。SET集合底层按照哈希值排序。
作者: treecolor166    时间: 2014-1-1 23:43
HashMap中的key等同于一个set集合，set集合存储元素的特点是无需不可重复，你多执行几次试试也许就不一样了
作者: 张洪慊    时间: 2014-1-2 16:08
本帖最后由 张洪慊 于 2014-1-2 16:45 编辑

首先你要了解存入的key所属类的hashCode方法:
Integer中hashCode()已被复写:
  1. public int hashCode() {
  2.         return value;//这个value就是你的Integer对象对应的int值
  3.     }
复制代码


接着向HashMap添加元素用到三个方法:
  1. //put
  2. public V put(K key, V value) {
  3.         if (table == EMPTY_TABLE) {
  4.             inflateTable(threshold);
  5.         }
  6.         if (key == null)
  7.             return putForNullKey(value);
  8.         int hash = hash(key);//这个会按照哈希算法求出key的哈希值
  9.         int i = indexFor(hash, table.length);//hash&table.length-1算出在哈希表中的index
  10.         for (Entry<K,V> e = table; e != null; e = e.next) {
  11.             Object k;
  12.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  13.                 V oldValue = e.value;
  14.                 e.value = value;
  15.                 e.recordAccess(this);
  16.                 return oldValue;
  17.             }
  18.         }

  20.         modCount++;
  21.         addEntry(hash, key, value, i);
  22.         return null;
  23.     }
复制代码
  1. final int hash(Object k) {
  2.         int h = hashSeed;
  3.         if (0 != h && k instanceof String) {
  4.             return sun.misc.Hashing.stringHash32((String) k);
  5.         }

  7.         h ^= k.hashCode();//将调用Integer的hashCode:例如添加key=5,返回5

  9.         // This function ensures that hashCodes that differ only by
  10.         // constant multiples at each bit position have a bounded
  11.         // number of collisions (approximately 8 at default load factor).
  12.         h ^= (h >>> 20) ^ (h >>> 12);
  13.         return h ^ (h >>> 7) ^ (h >>> 4);
  14.     }
复制代码
h ^= (h >>> 20) ^ (h >>> 12); h ^ (h >>> 7) ^ (h >>> 4);
算出来到底是多少?
你不妨让计算机帮我们算:
int h=5;
h ^= (h >>> 20) ^ (h >>> 12);
h ^ (h >>> 7) ^ (h >>> 4);
h的结果依然是5
那么计算出index: (初始表长16)
5&(16-1)=5
那么他将被添加到table[5]中
这么绕了一大圈,每个int值算出来的哈希值还是该int值...
加断点Debug:

但是如果添加的int值为16(表长16,最大index:15)
此时:
[attach]33669[/attach]

上图:key为16计算出的hash=17,17&(16-1)=1
那么在输出HashMap时,最先输出的元素 key=16的元素,接着输出key为4,5...这时候就不是从小到大.

究其原因就是Integer的hashCode方法直接返回其对应的int值,很大概率导致你的key与表中的索引一致,也就是你的输出结果,但不是绝对的,碰巧吧



table.PNG (49.99 KB, 下载次数: 46)

table.PNG
作者: belief丶Only    时间: 2014-1-2 16:18
张洪慊 发表于 2014-1-2 16:08
首先你要了解存入的key所属类的hashCode方法:
Integer中hashCode()已被复写:

很详细!!谢谢
作者: 张洪慊    时间: 2014-1-2 16:27
belief丶Only 发表于 2014-1-2 16:18
很详细!!谢谢

两张图有点不清,郁闷...
作者: 浮出一个美    时间: 2014-1-2 16:31
张洪慊 发表于 2014-1-2 16:08
首先你要了解存入的key所属类的hashCode方法:
Integer中hashCode()已被复写:

厉害。。。。。。。。。。。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2