Java HashMap 分析之四:查找和内存使用

拼搏现实的明天。 2021-09-10 04:54 196阅读 0赞

有了前面的分析，获取元素的逻辑就非常清晰。首先，调用者传递key，从key的hashCode方法获得值后，调用hash函数做一些低位置换，保证hash值的均匀分布，之后和size-1按位与后得到数组的位置。然后取出对应位置的链表，遍历该链表，查找hash值相等，并且key的引用或者值相等的对象，然后返回。代码见下面：

**\[java\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  public V get(Object key) \{  
2.      if (key == null)  
3.          return getForNullKey();  
4.      int hash = hash(key.hashCode());  
5.      for (Entry<K,V> e = table\[indexFor(hash, table.length)\];  
6.           e != null;  
7.           e = e.next) \{  
8.          Object k;  
9.          if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
10.             return e.value;  
11.     \}  
12.     return null;  
13. \}

算法时间复杂度平均是O(1)，如果hash code很糟糕，让其退化成链表，则是O(N).即便是O(1),也要注意，实际上计算hash用了好几步，绝对比直接从数组中获取某个元素的O(1)时间要长的多。

### 内存消耗 ###

有一个很好的工具，可以帮助我们检查Java对象内存的消耗。从这里下载jar包：[http://sizeof.sourceforge.net/][http_sizeof.sourceforge.net]  
解压后将SizeOf.jar复制到某个目录，比如我的/home/chenshu,在项目中加入这个jar包，并且设置JVM参数：-javaagent:/home/chenshu/SizeOf.jar。  
这个类库提供了一些静态函数，利用java.lang.Instrument的Instrumentation.getObjectSize()，能够计算Java对象真正在虚拟机里面占用的内存大小。下面的代码创建了一个只保存一个对象的HashMap,并计算内存占用。

**\[java\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  public static void main(String\[\] args) \{  
2.          // TODO code application logic here  
3.          HashMap<String,String> map = new HashMap<String,String>();  
4.          String put = map.put("a", "b");  
5.          String size = SizeOf.humanReadable(SizeOf.deepSizeOf(map));  
6.          System.out.println(size);  
7.    
8.      \}

结果是304字节，64bitJVM。真的很浪费内存，比我估计的要大多了！可见HashMap不是用来存放少量数据的。而且考虑到计算hash那么的复杂，如果只是喜欢Map这种Key,Value形式的接口，但并不保存较大数据量，应该考虑别的Map了。 Java其实提供了很多种Map,滥用HashMap的结果是只能开发“企业级“的应用，并且被我这种老程序员笑为富二代。：）  
因此，在大数据量（个人认为超过1万），并且需要快速查找和插入的时候，HashMap是非常好的选择。但是如果数据量不大的情况下，以tree实现的Map也是一个不错的选择，毕竟节省很多内存。而且tree还可以实现set这样的数据结构，有时候比Map更符合我们的需求。  
如果你现在拿起来就不假思索的使用HashMap（我知道这样的程序员太多了），请慎重。因为让你变得平凡的并不是项目进度紧或者工资低，而是对自己的要求不够高。

[view plain]: http://blog.csdn.net/csfreebird/article/details/7359065#
[http_sizeof.sourceforge.net]: http://sizeof.sourceforge.net/