Java之HashMap系列--遍历的方法及其性能

怼烎@ 2023-09-29 15:24 7阅读 0赞

原文网址：[Java之HashMap系列--遍历的方法及其性能\_IT利刃出鞘的博客-CSDN博客][Java_HashMap_--_IT_-CSDN]

## 简介 ##

本文用示例介绍HashMap遍历的方法及其性能。

> **技术资料与交流** ==>分享**靠谱**资料：Java**真实**面试题汇总、简历模板、PDF书籍、PPT模板等；分享Java**实用技术**；帮助**优化简历**；。详见：[资料与交流][Link 1]

## **遍历方法** ##

<table> 
 <tbody> 
 <tr> 
 <td> 方法 </td> 
 <td> 说明/示例 </td> 
 </tr> 
 <tr> 
 <td> for each map.entrySet() </td> 
 <td> Map&lt;String, String&gt; map = new HashMap&lt;String, String&gt;(); for (Entry&lt;String, String&gt; entry : map.entrySet()) { &nbsp;&nbsp;entry.getKey(); &nbsp;&nbsp;entry.getValue(); } </td> 
 </tr> 
 <tr> 
 <td> 调用map.entrySet()的集合迭代器 </td> 
 <td> Iterator&lt;Map.Entry&lt;String, String&gt;&gt; iterator = map.entrySet().iterator(); while (iterator.hasNext()) { &nbsp;&nbsp;entry.getKey(); &nbsp;&nbsp;entry.getValue(); } </td> 
 </tr> 
 <tr> 
 <td> for each map.keySet()，再调用get获取 </td> 
 <td> Map&lt;String, String&gt; map = new HashMap&lt;String, String&gt;(); for (String key : map.keySet()) { &nbsp;&nbsp;map.get(key); } </td> 
 </tr> 
 </tbody> 
</table>

## **遍历方法对比** ##

三种遍历方式的性能测试及对比

测试环境：Windows7 32位系统 3.2G双核CPU 4G内存，Java 7，Eclipse -Xms512m -Xmx512m

测试结果：

<table> 
 <tbody> 
 <tr> 
 <td>map size</td> 
 <td>10,000</td> 
 <td>100,000</td> 
 <td>1,000,000</td> 
 <td>2,000,000</td> 
 </tr> 
 <tr> 
 <td>for each entrySet</td> 
 <td>2ms</td> 
 <td>6ms</td> 
 <td>36ms</td> 
 <td>91ms</td> 
 </tr> 
 <tr> 
 <td>for iterator entrySet</td> 
 <td>0ms</td> 
 <td>4ms</td> 
 <td>35ms</td> 
 <td>89ms</td> 
 </tr> 
 <tr> 
 <td>for each keySet</td> 
 <td>1ms</td> 
 <td>6ms</td> 
 <td>48ms</td> 
 <td>126ms</td> 
 </tr> 
 </tbody> 
</table>

遍历方式结果分析（由上表可知）：

*  for each entrySet与for iterator entrySet性能等价
 *  for each keySet由于要再调用get（key）获取值，比较耗时（若hash散列算法较差，会更加耗时）
 *  在循环过程中若要对map进行删除操作，只能用for iterator entrySet（在HahsMap非线程安全里介绍）。

HashMap entrySet源码

private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
 public Map.Entry<K,V> next() {
 return nextEntry();
 }
 }

HashMap keySet源码

private final class KeyIterator extends HashIterator<K> {
 public K next() {
 return nextEntry().getKey();
 }
 }

由源码可知：

keySet()与entrySet()都是返回set的迭代器。父类相同，只是返回值不同，因此性能差不多。只是keySet()多了一步根据key get value的操作而已。get的时间复杂度取决于for循环的次数，即hash算法。

public V get(Object key) {
 if (key == null)
 return getForNullKey();
 Entry<K,V> entry = getEntry(key);
 return null == entry ? null : entry.getValue();
 }
 /**
 1. Returns the entry associated with the specified key in the
 2. HashMap. Returns null if the HashMap contains no mapping
 3. 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;
 }

## **使用场景总结** ##

<table> 
 <tbody> 
 <tr> 
 <td> 方法 </td> 
 <td> 使用场景 </td> 
 </tr> 
 <tr> 
 <td> for each map.entrySet() </td> 
 <td> 循环中需要key、value，但不对map进行删除操作 </td> 
 </tr> 
 <tr> 
 <td> 调用map.entrySet()的集合迭代器 </td> 
 <td> 循环中需要key、value，且要对map进行删除操作 </td> 
 </tr> 
 <tr> 
 <td> for each map.keySet() </td> 
 <td> 循环中只需要key </td> 
 </tr> 
 </tbody> 
</table>

[Java_HashMap_--_IT_-CSDN]: https://knife.blog.csdn.net/article/details/124903222
[Link 1]: https://app.yinxiang.com/fx/d2ac6ff4-94c5-4e5f-9d4f-f5dfc344ede6