`
123003473
  • 浏览: 1064091 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

HashMap的遍历效率讨论

    博客分类:
  • java
 
阅读更多
经常遇到对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分开操作在这里不是个好选择。

【转载地址】http://hi.baidu.com/injava/item/aac168cd66af7a090bd93a3e
分享到:
评论

相关推荐

    java遍历Map对象的说有数据

    我们将重点讨论通过`entrySet()`方法和`keySet()`方法来实现遍历的过程。 #### 方法一:使用`entrySet()` `entrySet()`方法返回一个包含映射中的所有映射关系的`Set`视图。这使得我们可以迭代整个映射,同时访问每...

    JAVA遍历map的几种实现方法代码

    以下将详细介绍标题和描述中提到的几种遍历Map的Java实现方法,并讨论它们的效率问题。 1. **keySet遍历** 使用`keySet()`方法获取Map的所有键,然后通过迭代器或者增强for循环遍历键。这种方法只遍历键,如果需要...

    2.Java7_8+中的+HashMap+和+ConcurrentHashMap+全解析1

    接下来,我们讨论Java 7的ConcurrentHashMap,这是一个线程安全的HashMap实现。与HashMap不同,ConcurrentHashMap采用了分段锁(Segment)的设计,将整个散列表分为多个独立的段,每个段有自己的锁。这样,在多线程...

    Java集合框架HashMap说明.doc

    下面将详细讨论HashMap的定义、构造函数、数据结构以及其性能优化策略。 首先,HashMap类继承了AbstractMap并实现了Map接口,提供了键值对的存储和访问功能。AbstractMap作为一个抽象类,提供了Map接口的部分实现,...

    Java 集合学习指南 - v1.1.pdf

    首先,我们来讨论HashMap。HashMap是Java集合框架中一个非常重要的Map接口的实现,它基于哈希表的原理来存储键值对。在HashMap中,它把键对象的哈希码作为索引,将对象存储在对应位置的数组中。如果两个键对象的哈希...

    实验05 Java集合.doc

    最后,我们用HashMap展示了Map的基本用法,添加键值对,遍历并打印键值对,删除指定键的元素,再次检查集合大小。 思考题中,我们讨论了List、Set和Map的区别,以及为什么优先选择集合框架而非数组。集合框架提供了...

    数据结构.mdaaa

    综上所述,本文从不同角度介绍了几种常见的数据结构及其基本操作,同时也讨论了Java中`HashMap`的一些关键实现细节。理解这些基础数据结构的概念和工作原理对于编程至关重要,有助于开发者更好地选择合适的数据结构...

    阿里P7面试题包含解答

    这里主要讨论的是`ArrayList`、`LinkedList`、`Vector`以及`HashMap`、`HashTable`、`TreeMap`的区别。 **ArrayList、LinkedList和Vector的区别** 1. **存储方式**: - `ArrayList`和`Vector`都是基于动态数组...

    杭州-阿里云-Java中级.pdf

    本文档主要讨论了 Java 中的 Collection 框架,特别是 List 和 Set 的区别、HashSet 的实现机制、HashMap 的线程安全性问题、扩容机制等。 List 和 Set 的区别: List 和 Set 都是继承自 Collection 接口,但是...

    Java面试-集合.doc

    HashMap的效率通常高于Hashtable,因为无需处理同步问题。两者的哈希算法相似,所以在性能上差异不大。 5. **List和Map的区别**:List是单列集合,存储有序且可重复的元素,如ArrayList或LinkedList。Map是双列集合...

    程序员必备数据结构知识

    - 链表(LinkedList)不需连续存储,插入和删除操作快,但访问元素需要遍历,效率较低。 - 栈(Stack)是一种后进先出(LIFO)的数据结构,常用于函数调用、表达式求值等。 - 队列(Queue)是一种先进先出(FIFO...

    Java 集合类面试题.docx

    - **LinkedList** 使用双向链表实现,增删元素(特别是头尾操作)效率高,但访问中间元素需要遍历,效率较低。 - **ArrayList** 通过数组实现,访问元素速度快,但插入和删除元素需要移动后续元素,效率相对较低。...

    ordered-map:按值排序的HashMap

    今天我们要讨论的是一个特殊类型的映射数据结构,即"ordered-map",它是一个按照特定顺序存储键值对的HashMap。这个数据结构在Rust编程语言中被广泛使用,因此在Rust社区中也被称为"OrdMap"或"BTreeMap"。 `ordered...

    各种类集 的区别1

    3. **操作效率**:无论是ArrayList还是Vector,从末尾添加和删除元素、获取指定位置的元素都非常快,时间复杂度为O(1)。但在中间位置进行插入和删除操作,ArrayList和Vector都需要移动后续元素,时间复杂度为O(n-i)...

    7-java进阶-集合1

    本节主要讨论的是Java集合中的高级话题,特别是关于`List`、`Set`接口以及它们的实现类,如`ArrayList`、`LinkedList`、`HashSet`、`HashMap`等。 首先,集合框架的核心是`Collection`接口,它是所有单个数据存储的...

    Java常见面试题300

    这里我们主要讨论Java面试中常见的两个问题:HashMap解决哈希冲突的方法以及GC(垃圾收集)的概念。 HashMap在Java中是一个非常重要的数据结构,它提供了高效的键值对存储和访问。哈希冲突是HashMap面临的主要挑战...

    比hashtable查找起来方便,转换类型也简单

    总之,`Hashtable`虽然在早期的Java版本中被广泛使用,但由于其限制和性能原因,在现代Java开发中,我们通常会优先考虑使用`HashMap`、`ConcurrentHashMap`等替代品,以便更好地利用现代Java特性和提高代码效率。

    Java Map 集合类简介

    3. 访问效率:HashMap通常具有最快的查找速度,而TreeMap和LinkedHashMap在特定情况下可能更优。 4. 遍历顺序:如果需要保持插入顺序或访问顺序,LinkedHashMap是理想的选择。 了解并熟练掌握这些Map的特性和用法,...

    java的hashtable的用法.pdf

    在这个讨论中,我们将深入理解`Hashtable`的用法、特点以及如何在实际编程中应用它。 1. **基本操作**: - `size()`:返回`Hashtable`中键值对的数量。 - `isEmpty()`:如果`Hashtable`为空,返回`true`,否则...

    sesvc.exe 阿萨德

    本篇主要想讨论 ConcurrentHashMap 这样一个并发容器,在正式开始之前我觉得有必要谈谈 HashMap,没有它就不会有后面的 ConcurrentHashMap。 HashMap 众所周知 HashMap 底层是基于 数组 + 链表 组成的,不过在 jdk...

Global site tag (gtag.js) - Google Analytics