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)源代码:

 public V put(K key, V value)      
 {      
  // 如果 key 为 null,调用 putForNullKey 方法进行处理    
  if (key == null)      
  return putForNullKey(value);      
  // 根据 key 的 hashCode 计算 Hash 值    
  int hash = hash(key.hashCode());      
  // 搜索指定 hash 值在对应 table 中的索引    
  int i = indexFor(hash, table.length);     
  // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素    
  for (Entry<K,V> e = table[i]; e != null; e = e.next)      
  {      
      Object k;      
  // 找到指定 key 与需要放入的 key 相等(hash 值相同    
  // 通过 equals 比较放回 true)    
  if (e.hash == hash && ((k = e.key) == key      
          || key.equals(k)))      
      {      
          V oldValue = e.value;      
          e.value = value;      
          e.recordAccess(this);      
  return oldValue;      
      }      
  }      
  // 如果 i 索引处的 Entry 为 null,表明此处还没有 Entry     
  modCount++;      
  // 将 key、value 添加到 i 索引处    
  addEntry(hash, key, value, i);      
  return null;      
 }      

上面程序中用到了一个重要的接口: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)方法如下:

 static int hash(int h)      
 {      
     h ^= (h >>> 20) ^ (h >>> 12);      
  return h ^ (h >>> 7) ^ (h >>> 4);      
 }   

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

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

上面方法的代码很简单,但其中包含了一个非常优雅的设计:系统总是将新添加的 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 中一个构造器的代码:

 // 以指定初始化容量、负载因子创建 HashMap     
  public HashMap(int initialCapacity, float loadFactor)      
  {      
  // 初始容量不能为负数    
  if (initialCapacity < 0)      
  throw new IllegalArgumentException(      
  "Illegal initial capacity: " +      
              initialCapacity);      
  // 如果初始容量大于最大容量,让出示容量    
  if (initialCapacity > MAXIMUM_CAPACITY)      
          initialCapacity = MAXIMUM_CAPACITY;      
  // 负载因子必须大于 0 的数值    
  if (loadFactor <= 0 || Float.isNaN(loadFactor))      
  throw new IllegalArgumentException(      
          loadFactor);      
  // 计算出大于 initialCapacity 的最小的 2 的 n 次方值。    
  int capacity = 1;      
  while (capacity < initialCapacity)      
          capacity <<= 1;      
  this.loadFactor = loadFactor;      
  // 设置容量极限等于容量 * 负载因子    
      threshold = (int)(capacity * loadFactor);      
  // 初始化 table 数组    
      table = new Entry[capacity];            // ①    
      init();      
  }    

上面代码中粗体字代码包含了一个简洁的代码实现:找出大于 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()方法详解:

 public V get(Object key)      
 {      
  // 如果 key 是 null,调用 getForNullKey 取出对应的 value     
  if (key == null)      
  return getForNullKey();      
  // 根据该 key 的 hashCode 值计算它的 hash 码    
  int hash = hash(key.hashCode());      
  // 直接取出 table 数组中指定索引处的值,    
  for (Entry<K,V> e = table[indexFor(hash, table.length)];      
      e != null;      
  // 搜索该 Entry 链的下一个 Entr     
      e = e.next)         // ①    
  {      
      Object k;      
  // 如果该 Entry 的 key 与被搜索 key 相同    
  if (e.hash == hash && ((k = e.key) == key      
          || key.equals(k)))      
  return e.value;      
  }      
  return null;      
 }      

从上面代码中可以看出,如果 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对象)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户画像

6.2.2 折半查找

折半查找,又称二分查找,它适用于有序的顺序表。基本思路是:首先将给定值key与表中中间位置元素的关键字比较,若相等,则查找成功,返回该元素的存储位置;若不等,则...

631
来自专栏老马说编程

(41) 剖析HashSet / 计算机程序的思维逻辑

查看历史文章,请点击上方链接关注公众号。 上节介绍了HashMap,提到了Set接口,Map接口的两个方法keySet和entrySet返回的都是Set,本节,...

1889
来自专栏JavaEdge

Java中Collections.sort()方法的演变结果分析源码分析关于Java8中Collections.sort方法的修改

4327
来自专栏赵俊的Java专栏

LeetCode 804 Unique Morse Code Words

首先为每个单词的每个字符进行转码, 将转码后的数据放到 Set 集合中, 最后返回 Set 的长度。

1054
来自专栏TechBox

数据结构与算法之线性表前言线性表

1865
来自专栏用户3030674的专栏

Java 工具类—日期获得,随机数,系统命令,数据类型转换

1401
来自专栏用户画像

7.7.5 最佳归并树

文件经过置换-选择排序之后,得到的是长度不等的初始归并段。下面讨论如何组织初始归并段的归并顺序,使I/O访问次数最少。

711
来自专栏机器学习实践二三事

leetcode之-题19

题目 [图片] Given a linked list, remove the nth node from the end of list and re...

1987
来自专栏云霄雨霁

数据结构----二叉堆和优先权队列

1600
来自专栏腾讯IVWEB团队的专栏

ES6 中的 Set

ES6 新增了几种集合类型,本文主要介绍Set以及其使用。Set对象是值的集合,你可以按照插入的顺序迭代它的元素。 Set中的元素只会出现一次,即 Set 中的...

8080

扫码关注云+社区

领取腾讯云代金券