java 高效的hashmap遍历方法


Hashmap的遍历,key和value通常的方法有两种,及使用entryset或者keyset遍历,下面我们来看下实例。

public class TestHashMap {	

private static void test1(){//效率低
Map<String,String> map = new HashMap<String,String>();
long time1 = System.currentTimeMillis(); 
for (int i = 0; i < 100000; i++) {
map.put("two"+i, 2+"");  
map.put("three"+i, 3+"");  
map.put("four"+i, 4+"");  
map.put("five"+i, 5+"");  
}

for (Iterator<String> iterator = map.keySet().iterator(); iterator.hasNext();) {
String s = iterator.next();
String m = map.get(s);
}
long time2 = System.currentTimeMillis();
long time = time2-time1;
System.out.println(time);
}




private static void test2(){//效率高
Map<String,String> map = new HashMap<String,String>();
long time1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
map.put("two"+i, 2+"");  
map.put("three"+i, 3+"");  
map.put("four"+i, 4+"");  
map.put("five"+i, 5+"");  
}
for (Iterator<Entry<String, String>> iterator = map.entrySet().iterator(); iterator.hasNext();) {
Entry<String, String> s = iterator.next();
String m = s.getValue();
String n = s.getKey();
}
long time2 = System.currentTimeMillis();
long time = time2-time1;
System.out.println(time);
}


public static void main(String[] args){
test1();
test2();
}

}

Hashmap是一个通过散列表实现的存储,底层是数组存放的元素,而hashmap的一个元素就是一个entry,也就是一个key-value的键值对,所以通过entry的遍历可以一次获取到key-value的键值对。但是通过keyset遍历的话,是先set集合里取出key,然后再通过map.get(key)活得value,通过hashmap源码分析得知,get(key)方法是又进行了一次迭代,找到entry,从而获得到的value,所以效率上用entry遍历更高。下面来看下map的get源码:


public V get(Object key) {
        if (key == null) {
            HashMapEntry<K, V> e = entryForNullKey;
            return e == null ? null : e.value;
        }


        // Doug Lea‘s supplemental secondaryHash function (inlined)
        int hash = key.hashCode();
        hash ^= (hash >>> 20) ^ (hash >>> 12);
        hash ^= (hash >>> 7) ^ (hash >>> 4);


        HashMapEntry<K, V>[] tab = table;
        for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
                e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                return e.value;
            }

        }
        return null;
    }

通过源码分析得知,当通过 key 取出对应 value 时,系统只要先计算出该 key 的 hashCode() 返回值,在根据该 hashCode 返回值找出该 key 在 table 数组中的索引,取出该索引处的 Entry,最后返回该 key 对应的 value 即可,此时如果对应的索引只存取一个entry,效率最高,但是如果hash冲突导致,存储的是一个entry链,就需要遍历找到需要的entry,这时候效率就要下降了。

但是大家有没有发现hashmap遍历是无序的呢,我们会在接下来的文章给大家讲解,谢谢。


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。