Java中对HashMap的深度分析

在Java的世界里,无论类还是各种数据,其结构的处理是整个程序的逻辑以及性能的关键。由于本人接触了一个有关性能与逻辑同时并存的问题,于是就开始研究这方面的问题。找遍了大大小小的论坛,也把《Java 虚拟机规范》,《apress,.java.collections.(2001),.bm.ocr.6.0.shareconnector》,和《Thinking in Java》翻了也找不到很好的答案,于是一气之下把JDK的 src 解压出来研究,扩然开朗,遂写此文,跟大家分享感受和顺便验证我理解还有没有漏洞。 这里就拿HashMap来研究吧。

  HashMap可谓JDK的一大实用工具,把各个Object映射起来,实现了“键--值”对应的快速存取。但实际里面做了些什么呢?

  在这之前,先介绍一下负载因子和容量的属性。大家都知道其实一个 HashMap 的实际容量就 因子*容量,其默认值是 16×0.75=12; 这个很重要,对效率很一定影响!当存入HashMap的对象超过这个容量时,HashMap 就会重新构造存取表。这就是一个大问题,我后面慢慢介绍,反正,如果你已经知道你大概要存放多少个对象,最好设为该实际容量的能接受的数字。

  两个关键的方法,put和get:

  先有这样一个概念,HashMap是声明了 Map,Cloneable, Serializable 接口,和继承了 AbstractMap 类,里面的 Iterator 其实主要都是其内部类HashIterator 和其他几个 iterator 类实现,当然还有一个很重要的继承了Map.Entry 的 Entry 内部类,由于大家都有源代码,大家有兴趣可以看看这部分,我主要想说明的是 Entry 内部类。它包含了hash,value,key 和next 这四个属性,很重要。put的源码如下

  public Object put(Object key, Object value) {
  Object k = maskNull(key);

  这个就是判断键值是否为空,并不很深奥,其实如果为空,它会返回一个static Object 作为键值,这就是为什么HashMap允许空键值的原因。

  int hash = hash(k);
  int i = indexFor(hash, table.length);

  这连续的两步就是 HashMap 最牛的地方!研究完我都汗颜了,其中 hash 就是通过 key 这个Object的 hashcode 进行 hash,然后通过 indexFor 获得在Object table的索引值。

  table???不要惊讶,其实HashMap也神不到哪里去,它就是用 table 来放的。最牛的就是用 hash 能正确的返回索引。其中的hash算法,我跟JDK的作者 Doug 联系过,他建议我看看《The art of programing vol3》可恨的是,我之前就一直在找,我都找不到,他这样一提,我就更加急了,可惜口袋空空啊!!!

  不知道大家有没有留意 put 其实是一个有返回的方法,它会把相同键值的 put 覆盖掉并返回旧的值!如下方法彻底说明了 HashMap 的结构,其实就是一个表加上在相应位置的Entry的链表:

  for (Entry e = table[i]; e != null; e = e.next) {
  if (e.hash == hash && eq(k, e.key)) {
  Object oldvalue = e.value;
  e.value = value; //把新的值赋予给对应键值。
  e.recordAccess(this); //空方法,留待实现
  return oldvalue; //返回相同键值的对应的旧的值。
  }
  }
  modCount++; //结构性更改的次数
  addEntry(hash, k, value, i); //添加新元素,关键所在!
  return null; //没有相同的键值返回
  }

  我们把关键的方法拿出来分析:

  void addEntry(int hash, Object key, Object value, int bucketIndex) {
  table[bucketIndex] = new Entry(hash, key, value, table[bucketIndex]);

  因为 hash 的算法有可能令不同的键值有相同的hash码并有相同的table索引,如:key=“33”和key=Object g的hash都是-8901334,那它经过indexfor之后的索引一定都为i,这样在new的时候这个Entry的next就会指向这个原本的table[i],再有下一个也如此,形成一个链表,和put的循环对定e.next获得旧的值。到这里,HashMap的结构,大家也十分明白了吧?

  if (size++ >= threshold) //这个threshold就是能实际容纳的量
  resize(2 * table.length); //超出这个容量就会将Object table重构

  所谓的重构也不神,就是建一个两倍大的table(我在别的论坛上看到有人说是两倍加1,把我骗了),然后再一个个indexfor进去!注意!!这就是效率!!如果你能让你的HashMap不需要重构那么多次,效率会大大提高!

  说到这里也差不多了,get比put简单得多,大家,了解put,get也差不了多少了。对于collections我是认为,它是适合广泛的,当不完全适合特有的,如果大家的程序需要特殊的用途,自己写吧,其实很简单。(作者是这样跟我说的,他还建议我用LinkedHashMap,我看了源码以后发现,LinkHashMap其实就是继承HashMap的,然后override相应的方法,有兴趣的同人,自己looklook)建个 Object table,写相应的算法,就ok啦。

  举个例子吧,像 Vector,list 啊什么的其实都很简单,最多就多了的同步的声明,其实如果要实现像Vector那种,插入,删除不多的,可以用一个Object table来实现,按索引存取,添加等。

  如果插入,删除比较多的,可以建两个Object table,然后每个元素用含有next结构的,一个table存,如果要插入到i,但是i已经有元素,用next连起来,然后size++,并在另一个table记录其位置。

(0)

相关推荐

  • Java8 HashMap的实现原理分析

    前言:Java8之后新增挺多新东西,在网上找了些相关资料,关于HashMap在自己被血虐之后痛定思痛决定整理一下相关知识方便自己看.图和有些内容参考的这个文章:http://www.jb51.net/article/80446.htm HashMap的存储结构如图:一个桶(bucket)上的节点多于8个则存储结构是红黑树,小于8个是单向链表. 1:HashMap的一些属性 public class HashMap<k,v> extends AbstractMap<k,v> impl

  • java HashMap通过value反查key的代码示例

    复制代码 代码如下: import java.util.ArrayList;import java.util.HashMap;import java.util.Iterator;import java.util.Map;import java.util.Set;public class MapValueGetKey {  public static void main(String[] args) {    Map map = new HashMap<>();    map.put(1,&qu

  • Java中HashMap和TreeMap的区别深入理解

    首先介绍一下什么是Map.在数组中我们是通过数组下标来对其内容索引的,而在Map中我们通过对象来对对象进行索引,用来索引的对象叫做key,其对应的对象叫做value.这就是我们平时说的键值对. HashMap通过hashcode对其内容进行快速查找,而 TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的). HashMap 非线程安全 TreeMap 非线程安全 线程安全 在Java里,线程安全一般体

  • 深入理解Java中的HashMap的实现机制

    如果任何人让我描述一下HashMap的工作机制的话,我就简单的回答:"基于Hash的规则".这句话非常简单,但是要理解这句话之前,首先我们得了解什么是哈希,不是么? 什么是哈希 哈希简单的说就是对变量/对象的属性应用某种算法后得到的一个唯一的串,用这个串来确定变量/对象的唯一性.一个正确的哈希函数必须遵守这个准则. 当哈希函数应用在相同的对象或者equal的对象的时候,每次执行都应该返回相同的值.换句话说,两个相等的对象应该有相同的hashcode. 注:所有Java对象都从Objec

  • java使用hashMap缓存保存数据的方法

    本文实例讲述了java使用hashMap缓存保存数据的方法.分享给大家供大家参考,具体如下: private static final HashMap<Long, XXX> sCache = new HashMap<Long, XXX>(); private static int sId = -1; public static void initAlbumArtCache() { try { //... if (id != sId) { clearCache(); sId = id

  • 举例详解Java编程中HashMap的初始化以及遍历的方法

    一.HashMap的初始化 1.HashMap 初始化的文艺写法    HashMap 是一种常用的数据结构,一般用来做数据字典或者 Hash 查找的容器.普通青年一般会这么初始化: HashMap<String, String> map = new HashMap<String, String>(); map.put("Name", "June"); map.put("QQ", "2572073701"

  • JAVA HashMap详细介绍和示例

    第1部分 HashMap介绍HashMap简介HashMap 是一个散列表,它存储的内容是键值对(key-value)映射.HashMap 继承于AbstractMap,实现了Map.Cloneable.java.io.Serializable接口.HashMap 的实现不是同步的,这意味着它不是线程安全的.它的key.value都可以为null.此外,HashMap中的映射不是有序的.HashMap 的实例有两个参数影响其性能:"初始容量" 和 "加载因子".容量

  • Java集合之HashMap用法详解

    本文实例讲述了Java集合之HashMap用法.分享给大家供大家参考,具体如下: HashMap是最常用的Map集合,它的键值对在存储时要根据键的哈希码来确定值放在哪里. HashMap 中作为键的对象必须重写Object的hashCode()方法和equals()方法 import java.util.Map; import java.util.HashMap; public class lzwCode { public static void main(String [] args) { M

  • Java HashMap的工作原理

    大部分Java开发者都在使用Map,特别是HashMap.HashMap是一种简单但强大的方式去存储和获取数据.但有多少开发者知道HashMap内部如何工作呢?几天前,我阅读了java.util.HashMap的大量源代码(包括Java 7 和Java 8),来深入理解这个基础的数据结构.在这篇文章中,我会解释java.util.HashMap的实现,描述Java 8实现中添加的新特性,并讨论性能.内存以及使用HashMap时的一些已知问题. 内部存储 Java HashMap类实现了Map<K

  • java无锁hashmap原理与实现详解

    java多线程环境中应用HashMap,主要有以下几种选择:使用线程安全的java.util.Hashtable作为替代​使用java.util.Collections.synchronizedMap方法,将已有的HashMap对象包装为线程安全的.使用java.util.concurrent.ConcurrentHashMap类作为替代,它具有非常好的性能.而以上几种方法在实现的具体细节上,都或多或少地用到了互斥锁.互斥锁会造成线程阻塞,降低运行效率,并有可能产生死锁.优先级翻转等一系列问题.

  • java遍历HashMap简单的方法

    本文实例讲述了java遍历HashMap简单的方法.分享给大家供大家参考.具体实现方法如下: import java.util.HashMap; import java.util.Iterator; import java.util.Set; public class HashSetTest { public static void main(String[] args) { HashMap map = new HashMap(); map.put("a", "aa"

  • Java中HashMap和Hashtable及HashSet的区别

    Hashtable类   Hashtable继承Map接口,实现一个key-value映射的哈希表.任何非空(non-null)的对象都可作为key或者value. 添加数据使用put(key,value),取出数据使用get(key),这两个基本操作的时间开销为常数. Hashtable通过initial   capacity和load   factor两个参数调整性能.通常缺省的load   factor   0.75较好地实现了时间和空间的均衡.增大load   factor可以节省空间但

随机推荐