每日Java(20150716-0720)

Java中的hash存储机制(以HashMap为主)

1. HashMap实现原理分析

1.1 概述:

看了HashMap源码的说明(HashMap.java),说明的非常好,尝试先翻译一下:
 
Hash table是基于Map接口的实现,这个实现提供了map的所有操作,同时允许null values和null key。(HashMap类和Hashtable基本可以等同,除了HashMap是非同步的(unsynchronized)且允许null键值)。HashMap不保证map中的顺序一直不变;
 
如果假设hash函数可以均匀地把元素分配在桶中,那么这个实现可以提供常量时间的基本操作(get方法和put方法);在集合层面上的迭代要求时间和HashMap实例的容量(capacity)以及大小(key-value映射对的数目)成比例;因此,如果要求高的迭代性能,最好不要把初始容量设置过高(或者把load factor设置的过低);
 
影响HashMap实例性能的有两个参数:初始容量和负载因子(load factor);初始容量是指创建hash表时分配的容量,load factor是一个衡量指标,当hash表的使用率大于这个指标时,hash表将会自动扩容(rehashed,容量将会翻倍);load factor默认为0.75,在时间和空间使用率上取得了一个很好的平衡;
 
注意这个实现是非同步的(not synchronized),如果多个线程同时访问一个hash map, 同时至少一个线程修改了map的结构(添加或删除一个mapping,仅仅改变一个已经存在的key的value,这不算结构修改),必须外在地执行同步化操作。如果没有这种对象存在,map需要被装箱(wrapped),如:
Map m = Collections.synchronizedMap(new HashMap(…));
 

1.2 HashMap的数据结构

在Java中,基本的存储数据的结构有两种,一个是数组,一个事模拟指针(引用)。所有的数据结构都可以用这两个基本结构来构造的,HashMap就是一个“链表的数组”的数据结构。如下图所示:
hashmap
由上图可以看出,HashMap底层就是一个数组结构,数组的每一项又是一个链表。当新建一个HashMap的时候,就会初始化一个数组,源码如下:

从源码中可以看出,Entry就是数组中的元素,每个Map.Entry就是一个key-value对,Entry持有一个指向下一个元素的引用,这就构成了链表。

1.3 HashMap的存储实现

1.3.1 存储

上面方法提供了一个根据 hashCode() 返回值来计算 Hash 码的方法:hash(),这个方法是一个纯粹的数学计算,其方法如下:

对于任意给定的对象,只要它的 hashCode() 返回值相同,那么程序调用 hash 方法所计算得到的 Hash 码值总是相同的。接下来程序会调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下:

h&(length-1)运算等价于对length取模,即h % length,举例如下所示:
h&(length-1)                h                  length-1
       4 & (16-1)         00100      &     01111      =      00100 (4)
       5 & (16-1)         00101       &     01111      =      00101 (5)
      18 & (16-1)        10010       &     01111      =      00010(2)
      23 & (16-1)       10111         &     01111      =      00111(7)
      ———————————————————————————————————————–

根据上面 put 方法的源代码可以看出,当程序试图将一个 key-value 对放入 HashMap 中时,程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value,但 key 不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部。

当向 HashMap 中添加 key-value 对,由其 key 的 hashCode() 返回值决定该 key-value 对(就是 Entry 对象)的存储位置。当两个 Entry 对象的 key 的 hashCode() 返回值相同时,将由 key 通过 eqauls() 比较值决定是采用覆盖行为(返回 true),还是产生 Entry 链(返回 false)。

上面程序中还调用了 addEntry(hash, key, value, i); 代码,其中 addEntry 是 HashMap 提供的一个包访问权限的方法,该方法仅用于添加一个 key-value 对。下面是该方法的代码:

上面方法的代码很简单,但其中包含了一个非常优雅的设计:系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象,那新添加的 Entry 对象指向原有的 Entry 对象(产生一个 Entry 链),如果 bucketIndex 索引处没有 Entry 对象,也就是上面程序1处代码的 e 变量是 null,也就是新放入的 Entry 对象指向 null,也就是没有产生 Entry 链。

1.3.2 读取

当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ——也就是没有通过指针产生 Entry 链时,此时的 HashMap 具有最好的性能:当程序通过 key 取出对应 value 时,系统只要先计算出该 key 的 hashCode() 返回值,在根据该 hashCode 返回值找出该 key 在 table 数组中的索引,然后取出该索引处的 Entry,最后返回该 key 对应的 value 即可。看 HashMap 类的 get(K key) 方法代码:

从上面代码中可以看出,如果 HashMap 的每个 bucket 里只有一个 Entry 时,HashMap 可以根据索引、快速地取出该 bucket 里的 Entry;在发生“Hash 冲突”的情况下,单个 bucket 里存储的不是一个 Entry,而是一个 Entry 链,系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那系统必须循环到最后才能找到该元素。

归纳起来简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据 Hash 算法来决定其存储位置;当需要取出一个 Entry 时,也会根据 Hash 算法找到其存储位置,直接取出该 Entry。由此可见:HashMap 之所以能快速存、取它所包含的 Entry,完全类似于现实生活中母亲从小教我们的:不同的东西要放在不同的位置,需要时才能快速找到它。

当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。

掌握了上面知识之后,我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值;如果程序比较关心空间开销、内存比较紧张,可以适当地增加负载因子;如果程序比较关心时间开销,内存比较宽裕则可以适当的减少负载因子。通常情况下,程序员无需改变负载因子的值。

1.4 HashSet的实现

对于 HashSet 而言,它是基于 HashMap 实现的,HashSet 底层采用 HashMap 来保存所有元素,因此 HashSet 的实现比较简单,查看 HashSet 的源代码,可以看到如下代码:
由上面源程序可以看出,HashSet 的实现其实非常简单,它只是封装了一个 HashMap 对象来存储所有的集合元素,所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存,而 HashMap 的 value 则存储了一个 PRESENT,它是一个静态的 Object 对象。HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的,因此 HashSet 和 HashMap 两个集合在实现本质上是相同的。
 

2. HashSet和HashMap的区别

 
*HashMap* *HashSet*
HashMap实现了Map接口 HashSet实现了Set接口
HashMap储存键值对 HashSet仅仅存储对象
使用put()方法将元素放入map中 使用add()方法将元素放入set中
HashMap中使用键对象来计算hashcode值 HashSet使用成员对象来计算hashcode值,对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性,如果两个对象不同的话,那么返回false
HashMap比较快,因为是使用唯一的键来获取对象 HashSet较HashMap来说比较慢
 

3. HashMap和HashTable的区别

HashMap和Hashtable都实现了Map接口,但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有:线程安全性,同步(synchronization),以及速度。
  • HashMap几乎可以等价于Hashtable,除了HashMap是非synchronized的,并可以接受null(HashMap可以接受为null的键值(key)和值(value),而Hashtable则不行)。
  • HashMap是非synchronized,而Hashtable是synchronized,这意味着Hashtable是线程安全的,多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。
  • 另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。
  • 由于Hashtable是线程安全的也是synchronized,所以在单线程环境下它比HashMap要慢。如果你不需要同步,只需要单一线程,那么使用HashMap性能要好过Hashtable。
  • HashMap不能保证随着时间的推移Map中的元素次序是不变的。
注:
  • sychronized意味着在一次仅有一个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要首先获得同步锁,其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。
  •  Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator,然后其它的线程试图“结构上”更改集合对象,将会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的,因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改,再调用set()方法,将会抛出IllegalArgumentException异常。
  •  结构上的更改指的是删除或者插入一个元素,这样会影响到map的结构。
 
 
 

参考文献:

  1. 通过分析 JDK 源代码研究 Hash 存储机制
  2. 深入Java集合学习系列:HashMap的实现原理
  3. 深入Java集合学习系列:HashMap的实现原理
  4. Java 7之集合类型第4篇 – HashMap
  5. HashMap源码分析(基于JDK1.6)
  6. Java 集合系列10之 HashMap详细介绍(源码解析)和使用示例
  7. Java HashMap的工作原理
  8. HashMap的工作原理(针对面试的一些问题给出解答)
  9. HashMap和HashSet的区别
  10. HashMap和Hashtable的区别
 
 

发表评论