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

系统管理员 2022-03-31 02:19 355阅读 0赞

### 获取元素 ###

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

**\[java\]** [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][] [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/sheismylife/article/details/7359065
[http_sizeof.sourceforge.net]: http://sizeof.sourceforge.net/