电光石火-穿越时空电光石火-穿越时空


HashSet/HashMap详解

HashMap和HashSet是Java Collection接口两个重要的成员,其中HashMap是Map接口常用的实现类,HashSet是Set接口常用的实现类。虽然HashMap和HashSet实现的接口不一样,但是底层实现都使用了哈希表算法,存储机制完全一样。甚至HashSet本身就采用了HashMap来实现的!


详解HashSet、HashMap的源代码分析及其哈希表存储机制:


HashSet和HashMap存储的特点:(1)不允许元素重复出现(HashMap集合中key不能重复);(2)不保存元素添加的先后顺序;(3)底层都采用了哈希表的算法(必须要同时实现hashCode()和equals()方法);(4)本质上也是数组存储,HashMap底层是数组 + 链表存储数据。


对于HashMap而言,系统将Entry(key -value)元素作为一个整体来处理,系统总是根据Hash算法来计算出key-value的存储的位置,这样就可以保证快速存、取Map中的key-value对了!

在讲解集合时需指出一点:虽然集合表面上看存储的是Java对象,实际上存储的对象的引用。也就是说:Java集合实际上是多个引用变量所组成的集合,而这些引用指向实际堆内存中的Java对象!


HashMap的存储实现:

首先我们看看HashMap中put(K key,V value)源代码:

[java] view plain copy
  1. public V put(K key, V value)     
  2. {     
  3.  // 如果 key 为 null,调用 putForNullKey 方法进行处理    
  4.  if (key == null)     
  5.      return putForNullKey(value);     
  6.  // 根据 key 的 hashCode 计算 Hash 值    
  7.  int hash = hash(key.hashCode());     
  8.  // 搜索指定 hash 值在对应 table 中的索引    
  9.      int i = indexFor(hash, table.length);    
  10.  // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素    
  11.  for (Entry<K,V> e = table[i]; e != null; e = e.next)     
  12.  {     
  13.      Object k;     
  14.      // 找到指定 key 与需要放入的 key 相等(hash 值相同    
  15.      // 通过 equals 比较放回 true)    
  16.      if (e.hash == hash && ((k = e.key) == key     
  17.          || key.equals(k)))     
  18.      {     
  19.          V oldValue = e.value;     
  20.          e.value = value;     
  21.          e.recordAccess(this);     
  22.          return oldValue;     
  23.      }     
  24.  }     
  25.  // 如果 i 索引处的 Entry 为 null,表明此处还没有 Entry     
  26.  modCount++;     
  27.  // 将 key、value 添加到 i 索引处    
  28.  addEntry(hash, key, value, i);     
  29.  return null;     
  30. }     


上面程序中用到了一个重要的接口:Map.Entry,这是Map接口中内置的静态接口。每个Map.entry其实就是一个key-value对,从上面的程序可以看出:当系统存储HashMap中的key-value对时,完全没有考虑Entry元素中的value值,仅仅只是根据key来计算并决定每个Entry的存储位置,这也就说明前面的结论,我们完全可以把Map集合中的value当成key的附属,当系统决定key存储的位置,value的值也就随即存储!


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

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

[java] view plain copy
  1. static int hash(int h)     
  2. {     
  3.     h ^= (h >>> 20) ^ (h >>> 12);     
  4.     return h ^ (h >>> 7) ^ (h >>> 4);     
  5. }  




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



当向 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 对。下面是该方法的代码: 

[java] view plain copy
  1. void addEntry(int hash, K key, V value, int bucketIndex)     
  2. {     
  3.     // 获取指定 bucketIndex 索引处的 Entry     
  4.     Entry<K,V> e = table[bucketIndex];     // ①    
  5.     // 将新创建的 Entry 放入 bucketIndex 索引处,并让新的 Entry 指向原来的 Entry     
  6.     table[bucketIndex] = new Entry<K,V>(hash, key, value, e);     
  7.     // 如果 Map 中的 key-value 对的数量超过了极限    
  8.     if (size++ >= threshold)     
  9.         // 把 table 对象的长度扩充到 2 倍。    
  10.         resize(2 * table.length);    // ②    
  11. }   




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

JDK源码:

Hash 算法的性能选项 



根据上面代码可以看出,在同一个 bucket 存储 Entry 链的情况下,新放入的 Entry 总是位于 bucket 中,而最早放入该 bucket 中的 Entry 则位于这个 Entry 链的最末端。 



上面程序中还有这样两个变量: 



    * size:该变量保存了该 HashMap 中所包含的 key-value 对的数量。 

    * threshold:该变量包含了 HashMap 能容纳的 key-value 对的极限,它的值等于 HashMap 的容量乘以负载因子(load factor)。 

    * load factor:该变量就是保证了HashMap存取效率最高的平衡度(默认0.75)



从上面程序中②号代码可以看出,当 size++ >= threshold 时,HashMap 会自动调用 resize 方法扩充 HashMap 的容量。每扩充一次,HashMap 的容量就增大一倍。 



上面程序中使用的 table 其实就是一个普通数组,每个数组都有一个固定的长度,这个数组的长度就是 HashMap 的容量。HashMap 包含如下几个构造器: 



    * HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。 

    * HashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子为 0.75 的 HashMap。 

    * HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap。
 




当创建一个 HashMap 时,系统会自动创建一个 table 数组来保存 HashMap 中的 Entry,下面是 HashMap 中一个构造器的代码: 

[java] view plain copy
  1. // 以指定初始化容量、负载因子创建 HashMap     
  2.  public HashMap(int initialCapacity, float loadFactor)     
  3.  {     
  4.      // 初始容量不能为负数    
  5.      if (initialCapacity < 0)     
  6.          throw new IllegalArgumentException(     
  7.         "Illegal initial capacity: " +     
  8.              initialCapacity);     
  9.      // 如果初始容量大于最大容量,让出示容量    
  10.      if (initialCapacity > MAXIMUM_CAPACITY)     
  11.          initialCapacity = MAXIMUM_CAPACITY;     
  12.      // 负载因子必须大于 0 的数值    
  13.      if (loadFactor <= 0 || Float.isNaN(loadFactor))     
  14.          throw new IllegalArgumentException(     
  15.          loadFactor);     
  16.      // 计算出大于 initialCapacity 的最小的 2 的 n 次方值。    
  17.      int capacity = 1;     
  18.      while (capacity < initialCapacity)     
  19.          capacity <<= 1;     
  20.      this.loadFactor = loadFactor;     
  21.      // 设置容量极限等于容量 * 负载因子    
  22.      threshold = (int)(capacity * loadFactor);     
  23.      // 初始化 table 数组    
  24.      table = new Entry[capacity];            // ①    
  25.      init();     
  26.  }   


上面代码中粗体字代码包含了一个简洁的代码实现:找出大于 initialCapacity 的、最小的 2 的 n 次方值,并将其作为 HashMap 的实际容量(由 capacity 变量保存)。例如给定 initialCapacity 为 10,那么该 HashMap 的实际容量就是 16。 

程序①号代码处可以看到:table 的实质就是一个数组,一个长度为 capacity 的数组。 



对于 HashMap 及其子类而言,它们采用 Hash 算法来决定集合中元素的存储位置。当系统开始初始化 HashMap 时,系统会创建一个长度为 capacity 的 Entry 数组,这个数组里可以存储元素的位置被称为“桶(bucket)”,每个 bucket 都有其指定索引,系统可以根据其索引快速访问该 bucket 里存储的元素。 



无论何时,HashMap 的每个“桶”只存储一个元素(也就是一个 Entry),由于 Entry 对象可以包含一个引用变量(就是 Entry 构造器的的最后一个参数)用于指向下一个 Entry,因此可能出现的情况是:HashMap 的 bucket 中只有一个 Entry,但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。如图 1 所示:


HashMap中读取实现:get()方法详解:

[java] view plain copy
  1. public V get(Object key)     
  2. {     
  3.  // 如果 key 是 null,调用 getForNullKey 取出对应的 value     
  4.  if (key == null)     
  5.      return getForNullKey();     
  6.  // 根据该 key 的 hashCode 值计算它的 hash 码    
  7.  int hash = hash(key.hashCode());     
  8.  // 直接取出 table 数组中指定索引处的值,    
  9.  for (Entry<K,V> e = table[indexFor(hash, table.length)];     
  10.      e != null;     
  11.      // 搜索该 Entry 链的下一个 Entr     
  12.      e = e.next)         // ①    
  13.  {     
  14.      Object k;     
  15.      // 如果该 Entry 的 key 与被搜索 key 相同    
  16.      if (e.hash == hash && ((k = e.key) == key     
  17.          || key.equals(k)))     
  18.          return e.value;     
  19.  }     
  20.  return null;     
  21. }     




从上面代码中可以看出,如果 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 表所占用的内存空间;


注意:HashSet底层实现算法都是挪用了HashMap底层桑算法的实现,HashSet存储的元素不允许重复,HashMap中存储的key就不允许重复,就完全符合这一原则;并且HashMap集合中的value是附属,完全不用考虑,知道key存储的位置就直接知道对应value的位置,所以HashSet只管元素存储的位置(即key存储的位置),而value就是一个新的Object对象(并且每一个key对应的value都是一样的Object对象)

本博客所有文章如无特别注明均为原创。作者:似水的流年
版权所有:《电光石火-穿越时空》 => HashSet/HashMap详解
本文地址:http://ilkhome.cn/index.php/archives/235/
欢迎转载!复制或转载请以超链接形式注明,文章为 似水的流年 原创,并注明原文地址 HashSet/HashMap详解,谢谢。

评论