图的遍历:HashMap的遍历效率讨论来源: 发布时间:星期五, 2008年11月28日 浏览:227次 评论:0
HashMap的遍历效率讨论
经常遇到对HashMap中的key和value值对的遍历操作,有如下两种方法: Map<String, String[]> paraMap = new HashMap<String, String[]>(); ................ //第一个循环 Set<String> appFieldDefIds = paraMap.keySet(); for (String appFieldDefId : appFieldDefIds) { String[] values = paraMap.get(appFieldDefId); ...... } //第二个循环 for(Entry<String, String[]> entry : paraMap.entrySet()){ String appFieldDefId = entry.getKey(); String[] values = entry.getValue(); ....... } 第一种实现明显的效率不如第二种实现。 分析如下 Set<String> appFieldDefIds = paraMap.keySet(); 是先从HashMap中取得keySet 代码如下: public Set<K> keySet() { Set<K> ks = keySet; return (ks != null ? ks : (keySet = new KeySet())); } private class KeySet extends AbstractSet<K> { public Iterator<K> iterator() { return newKeyIterator(); } public int size() { return size; } public boolean contains(Object o) { return containsKey(o); } public boolean remove(Object o) { return HashMap.this.removeEntryForKey(o) != null; } public void clear() { HashMap.this.clear(); } } 其实就是返回一个私有类KeySet, 它是从AbstractSet继承而来,实现了Set接口。 再来看看for/in循环的语法 for(declaration : expression) statement 在执行阶段被翻译成如下各式 for(Iterator<E> #i = (expression).iterator(); #i.hashNext();){ declaration = #i.next(); statement } 因此在第一个for语句for (String appFieldDefId : appFieldDefIds) 中调用了HashMap.keySet().iterator() 而这个方法调用了newKeyIterator() Iterator<K> newKeyIterator() { return new KeyIterator(); } private class KeyIterator extends HashIterator<K> { public K next() { return nextEntry().getKey(); } } 所以在for中还是调用了 在第二个循环for(Entry<String, String[]> entry : paraMap.entrySet())中使用的Iterator是如下的一个内部类 private class EntryIterator extends HashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() { return nextEntry(); } } 此时第一个循环得到key,第二个循环得到HashMap的Entry 效率就是从循环里面体现出来的第二个循环此致可以直接取key和value值 而第一个循环还是得再利用HashMap的get(Object key)来取value值 现在看看HashMap的get(Object key)方法 public V get(Object key) { Object k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length); //Entry[] table Entry<K,V> e = table; while (true) { if (e == null) return null; if (e.hash == hash && eq(k, e.key)) return e.value; e = e.next; } } 其实就是再次利用Hash值取出相应的Entry做比较得到结果,所以使用第一中循环相当于两次进入HashMap的Entry中 而第二个循环取得Entry的值之后直接取key和value,效率比第一个循环高。 其实按照Map的概念来看也应该是用第二个循环好一点,它本来就是key和value的值对,将key和value分开操作在这里不是个好选择。 0
相关文章读者评论发表评论 |