HashMap的遍历

Posted on | In | Visitors:

HashMap中的 keySet() 方法

  • 返回映射中所包含的键的 set 视图，
  • 返回类型为 Set 。如果只查询 HashMap 中的所有键，可以用到这个方法。

entrySet()

  • 返回此映射所包含的映射关系（映射关系是指键值对）的 collection 视图
  • 在返回的集合中，每个元素都是一个Map.Entry。
  • 与keySet()不同的是，keySet只返回所有的键。 而entrySet则返回的是键值对，不仅包含键，还包括键的值。

Map的四种遍历方式

1.for each map.entrySet()

1
2
3
4
5
Map<String, String> map = new HashMap<String, String>();
for (Entry<String, String> entry : map.entrySet()) {
	entry.getKey();
	entry.getValue();
}

2.显示调用map.entrySet()的集合迭代器

1
2
3
4
5
6
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
	Map.Entry<String, String> entry = iterator.next();
	entry.getKey();
	entry.getValue();
}

3.for each map.keySet()，再调用get获取

1
2
3
4
Map<String, String> map = new HashMap<String, String>();
for (String key : map.keySet()) {
    map.get(key);
}

4.for each map.entrySet()，用临时变量保存map.entrySet()

1
2
3
4
5
Set<Entry<String, String>> entrySet = map.entrySet();
for (Entry<String, String> entry : entrySet) {
    entry.getKey();
    entry.getValut();
}

HashMap遍历方式比较

试验得，第三种方式（for each map.keySet()，再调用get获取）最耗时，性能最差。

来看 HashMap entrySet 和 keySet 的源码：

1
2
3
4
5
6
7
8
9
10
11
private final class KeyIterator extends HashIterator<K> {
	public K next() {
		return nextEntry().getKey();
	}
}
 
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
	public Map.Entry<K,V> next() {
		return nextEntry();
	}
}

分别是keySet()和entrySet()返回的set的迭代器，从中我们可以看到只是返回值不同而已，父类相同，所以性能相差不多。
但是，第三种方式，多了一步根据key get得到value的操作。

get(key) 的时间复杂度根据hash算法而异，源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public V get(Object key) {
	if (key == null)
		return getForNullKey();
	Entry<K,V> entry = getEntry(key);
 
	return null == entry ? null : entry.getValue();
}
 
/**
 * Returns the entry associated with the specified key in the
 * HashMap.  Returns null if the HashMap contains no mapping
 * for the key.
 */
final Entry<K,V> getEntry(Object key) {
	int hash = (key == null) ? 0 : hash(key);
	for (Entry<K,V> e = table[indexFor(hash, table.length)];
		 e != null;
		 e = e.next) {
		Object k;
		if (e.hash == hash &&
			((k = e.key) == key || (key != null && key.equals(k))))
			return e;
	}
	return null;
}

get 的时间复杂度取决于for循环循环次数，即hash算法。

总结

从上面的分析来看：
HashMap的循环，如果既需要key也需要value，直接用：

1
2
3
4
5
Map<String, String> map = new HashMap<String, String>();
for (Entry<String, String> entry : map.entrySet()) {
	entry.getKey();
	entry.getValue();
}

如果只是遍历 key 而无需 value 的话，可以用：

1
2
3
4
Map<String, String> map = new HashMap<String, String>();
for (String key : map.keySet()) {
	// key process
}