文档章节

集合类学习之Hashmap机制研究

Kerry_Han
 Kerry_Han
发布于 2013/08/30 14:08
字数 1962
阅读 34
收藏 0

1、遍历的两种实现方法

//新建

Map map=new HashMap();

//存储值

map.put()

//遍历方式一  
  
Iterator iterator=map.entrySet().Iterator();  
  
while(iterator.hasNext())  
  
{     
  
Map.Entry entry=(Map.Entry )iterator.next();  
  
Objcet key=entry.getKey();  
  
Objcet value=entry.getValue();  
  
}


//遍历方式二

Iterator iter = map.keySet().iterator();   
while (iter.hasNext()) {   
    Object key = iter.next();   
    Object val = map.get(key);   
}

2、原理研究


1、The HashMap class is roughly equivalent to <tt>Hashtable</tt>, except that it is unsynchronized and permits nulls.

2、An instance of HashMap has two parameters that affect its performance: initial capacity  and load factor.  The capacity  is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.  The load factor  is a measure of how full the hash table is allowed to get before its capacity is automatically increased.  When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed that is, internal data structures are rebuilt,so that the hash table has approximately twice the number of buckets.加载因子默认为0.75,较好的平衡了时间和空间开销

3、hashmap是非同步和允许null值的,对于多线程情况下,最好初始化时,如下定义:

Map m = Collections.synchronizedMap(new HashMap(...));  

4、源码分析

 

构造方法:

 

 /** 
   * The default initial capacity - MUST be a power of two.初始大小为16,必须为2的幂形式 
   */  
  static final int DEFAULT_INITIAL_CAPACITY = 16;  
  
 /** 
   * The maximum capacity, used if a higher value is implicitly specified 
   * by either of the constructors with arguments. 
   * MUST be a power of two <= 1<<30.最大为2的30次幂 
   */  
  static final int MAXIMUM_CAPACITY = 1 << 30;  
  /** 
   * The next size value at which to resize (capacity * load factor). 
   * @serial 
   */  
  int threshold;  
  
  /** 
   * The table, resized as necessary. Length MUST Always be a power of two. 
   */  
  transient Entry[] table;//存储的容器其实是个容量为capacity的数组  
  
  
  
//构造方法  
  
public HashMap(int initialCapacity, float loadFactor) {  
      if (initialCapacity < 0)  
          throw new IllegalArgumentException("Illegal initial capacity: " +  
                                             initialCapacity);  
      if (initialCapacity > MAXIMUM_CAPACITY)  
          initialCapacity = MAXIMUM_CAPACITY;  
      if (loadFactor <= 0 || Float.isNaN(loadFactor))  
          throw new IllegalArgumentException("Illegal load factor: " +  
                                             loadFactor);  
  
      // Find a power of 2 >= initialCapacity  
      int capacity = 1;  
      while (capacity < initialCapacity)  
          capacity <<= 1;  
  
      this.loadFactor = loadFactor;  
      threshold = (int)(capacity * loadFactor);  
      table = new Entry[capacity];/  /hashmap内部实现为Entry  
      init();

 

对于任意给定的对象,只要它的 hashCode() 返回值相同,那么程序调用 hash(int h) 方法所计算得到的 Hash 码值总是相同的。

 public V put(K key, V value)   
 {   
     // 如果 key 为 null,调用 putForNullKey 方法进行处理  
     if (key == null)   
         return putForNullKey(value);   
     // 根据 key 的 keyCode 计算 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;   
 } </pre><br>

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

  1.  Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。</p>  

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

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

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

    </pre>  

  5.  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;


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

  7.  在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据 Hash 算法来决定其存储位置;当需要取出一个 Entry 时,也会根据 Hash 算法找到其存储位置,直接取出该 Entry。</p>  

  8. <p>由此可见:HashMap 之所以能快速存、取它所包含的 Entry,完全类似于现实生活中母亲从小教我们的:不同的东西要放在不同的位置,需要时才能快速找到它。当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加  

  9.  Hash 表所占用的内存空间。掌握了上面知识之后,我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值;如果程序比较关心空间开销、内存比较紧张,可以适当地增加负载因子;如果程序比较关心时间开销,内存比较宽裕则可以适当的减少负载因子。通常情况下,程序员无需改变负载因子的值。如果开始就知道 HashMap 会保存多个 key-value 对,可以在创建时就使用较大的初始化容量,如果 HashMap 中 Entry 的数量一直不会超过极限容量(capacity * load factor),HashMap  

  10.  就无需调用 resize() 方法重新分配 table 数组,从而保证较好的性能。当然,开始就将初始容量设置太高可能会浪费空间(系统需要创建一个长度为 capacity 的 Entry 数组),因此创建 HashMap 时初始化容量设置也需要小心对待。 <

© 著作权归作者所有

共有 人打赏支持
Kerry_Han
粉丝 14
博文 174
码字总数 54257
作品 0
海淀
程序员
私信 提问
通过分析 JDK 源代码研究 Hash 存储机制

HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,HashSet 是 Set 接口的常用实现类。虽然 HashMap 和 HashSet 实现的接口规范不同...

红薯
2009/11/30
886
2
Java集合---大结局(总结概括终结篇)

文章写到这,感觉该做一个总结了,也是时候结束了, 最常用的集合类基本上已经写完了,剩下的就不再继续探索了,感兴趣的自行研究,应该还会有几篇番外篇,关于并发包JUC中的集合,如current...

起个名忒难
2017/11/11
0
0
Java集合 --- LinkedHashMap底层实现和原理(源码解析)

概述 文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的有些类做了改动,增加了阅读的难度,虽然是1.7,但是对于1.8做了重大改动的内容,文章也会进行说明。 LinkedHashMap,见...

起个名忒难
2017/09/24
0
0
一名3年工作经验的java程序员应该具备的职业技能

一名3年工作经验的Java程序员应该具备的技能,这可能是Java程序员们比较关心的内容。我这里要说明一下,以下列举的内容不是都要会的东西—-但是如果你掌握得越多,最终能得到的评价、拿到的薪...

老道士
07/16
0
0
Java容器源码分析-HashSet vs TreeSet vs LinkedHashSet

这几天看了下容器的源码,总结一下HashSet vs TreeSet vs LinkedHashSet的区别, 如下图,collection的继承实现分支,这里先只讲解set分支 1、HashSet vs TreeSet vs LinkedHashSet三者的数据...

贾浩v
2017/10/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何解决 homebrew 更新慢的问题

之前一直困扰于 Homebrew 的更新速度,曾试过修改更新源(清华、中科大等)的方式,但是并没什么卵用;也试过设置 curl 代理的方式,但是 brew 走的好像不是 curl 的方式,所以也没用。 通过...

whoru
12分钟前
0
0
TiDB EcoSystem Tools 原理解读系列(二)TiDB-Lightning Toolset 介绍

简介 TiDB-Lightning Toolset 是一套快速全量导入 SQL dump 文件到 TiDB 集群的工具集,自 2.1.0 版本起随 TiDB 发布,速度可达到传统执行 SQL 导入方式的至少 3 倍、大约每小时 100 GB,适合...

TiDB
14分钟前
0
0
【Visual Studio 扩展工具】如何在ComponentOneFlexGrid树中显示RadioButton

概述 在ComponentOne Enterprise .NET控件集中,FlexGrid表格控件是用户使用频率最高的控件之一。它是一个功能强大的数据管理工具,轻盈且灵动,以分层的形式展示数据(数据呈现更加直观)。...

葡萄城技术团队
16分钟前
0
0
Maven环境隔离

Maven环境隔离 1. 什么是Maven环境隔离 顾名思义,Maven环境隔离就是将开发中的环境与beat环境、生产环境分隔开,方便进行开发和维护。这个在实际项目中用的还是很多的,如果你的项目用的Mav...

蚂蚁-Declan
16分钟前
1
0
day182-2018-12-19-英语流利阅读-待学习

“性感”时代已去,维密将如何转身? Daniel 2018-12-19 1.今日导读 维多利亚的秘密(Victoria's Secret)这个内衣品牌,最近似乎步入了“中年危机”——曾经打遍天下的“性感”内衣,在主打...

飞鱼说编程
16分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部