- 浏览: 36423 次
文章分类
- 全部博客 (35)
- java (36)
- Toast to C (1)
- Java二进制指令代码解析 (1)
- CHAR (1)
- varchar以及varchar2的区别 (1)
- Java学习笔记(二)----JBoss发展现状 (1)
- Enum的策略模式 (1)
- j2EE开发群 欢迎加入该群一起学习 群号:172429747 (1)
- clipRect 介绍 (1)
- 认识Java程序之对象间消息传递 (1)
- Android的Location功能代码 (1)
- Android的Activity之间的通信 (1)
- 关于提高自己JAVA水平的十大技术讨论(转) (1)
- 推荐三本书 (1)
- C#打印DataGrid中的数据 (1)
- 注意新技术的风险是否会超过获得成功的几率 (1)
- MapXtreme2004代码 简单专题图的显示 (1)
- 在网页中插入RM视频文件的历程 (1)
- 《使用 Microsoft .NET 的企业解决方案模式》读书笔记2 (1)
- xml格式字符串与java对象互转 (1)
- 手机wifi传文件的一简单代码 (1)
- HOWTO: Disable HTTP Methods in Apache (1)
- SQL 笔试题(摘) (1)
- java的ProcessBuilder阻塞问题 (1)
- 现在在郑州做java开发想去深圳 (1)
- Could not find a JavaScript runtime (1)
- 构造方法,重载,多个,无参,参数,this,super (1)
- Servlet多线程 (1)
- 如何使SOLR系统自动AUTO COMMIT (1)
- Linux下Mysql表名区分大小写 (1)
- 好玩的游戏合集~~ (1)
- HashMap源码分析 (1)
- 以一个枢纽值二分一个数组 (1)
最新评论
-
liuyes:
写的有点乱呀
HashMap源码分析 -
chenglinjava:
来北京吧!!!
现在在郑州做java开发想去深圳
[size=medium;]HashMap源码分析[/size]
HashMap用来存储key-value对,内部使用拉链法Hash表作为存储结构,key-value被封装成Entry<K, V>,Entry也是链表结点。
1. Hash表的内部结构如下:
<span style="white-space: pre;"> Entry<K, V> table[];</span>
table[0]-->Entry(K,V)-->Entry(K,V) table[1]-->Entry(K,V) table[2] table[3]-->Entry(K,V) table[.]
Entry<K,V>数据域代码:
<span style="white-space: pre;">static class Entry<K,V> implements Map.Entry<K,V> {</span>
final K key; V value; final int hash; [b] Entry<K,V> next;[/b] }
HashMap的Key-Value对,被包装成Entry(K,V),根据key计算hash值,确定在table数组的下标位置,数组元素为链表的链表头,被计算hash映射到相同数组下标位置的key-value都被存储在这个链表当中,这就是解决hash冲突的办法 。
2.HashMap中查找目标Entry<K,V>
也就是说根据key进行hash只能找到Entry(K,V)在哪个链表当中,查找到具体确切的Entry(K,V)还需要遍历整个链表的每个节点,针对每个节点去匹配key值,如果链表很长,那么效率就会很低,体现不出Hash表的优势。理想的情况是每个链表不多于一个节点,这样通过hash就可以直接找到目标Entry(K,V),能够在O(1)内实现元素的查找,像数组一样,在存储内容与存储位置之间建立直接的映射关系。
3.HashMap中的扩容
为了提升Hash表的性能,在HashMap中存储的k-v对数目超过了预定的负载量threshold时,就对HashMap进行扩容,实际上就是使用table[]数组成倍增加,这样做的目的是使每个链表长度较为短小,能够实现快速的定位目标结点;但是扩容需要对原HashMap中的每个结点重新计算存储位置,迁移到新的table[]当中,这也是一笔不少的开销,应该减少扩容的次数,所以根据应用场景选择一个合适的loadFactor和capacity比较重要,loadFactor和capacity可以在HashMap的构造函数中设置。
Threshold计算: threshold = (int)(capacity * loadFactor);( 当前容量 * 负载因子)
<p style="margin: 0px;"> Static int final DEFAULT_INITIAL_CAPACITY = 16;
<p style="margin: 0px;">
<p style="margin: 0px;"> 4.HashMap不是线程安全的,代码中没有任何的同步措施,在多线程中环境中需要注意。
<p style="margin: 0px;">
<p style="margin: 0px;"> 5.代码分析
<p style="margin: 0px;"> 构造函数
<p style="margin: 0px;">
<p style="margin: 0px;">
//指定初始容量和负载因子的构造函数 public HashMap(int initialCapacity, float loadFactor) { //检测参数的合法性initialCapacity, 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; //当HashMap存储的键值对数,超过threshold,就需要对整个hash table进行扩展 //threshold = capactiy * loadFactor;通过负载因子计算得来. threshold = (int)(capacity * loadFactor); //为HashMap依赖的table申请空间 table = new Entry[capacity]; init(); }
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }
<span style="white-space: pre;"> public HashMap(int initialCapacity) {</span>
this(initialCapacity, DEFAULT_LOAD_FACTOR); }
get(k)方法
public V get(Object key) { //如果key是null,返回一个Object对象作内部处理,HashMap中可以使用null作为key Object k = maskNull(key); //计算此k(key)对应的hash值 int hash = hash(k); //indexFor:h & (length-1) //计算此key在hash表中的映射到的数组元素位置(每个元素是一个指向链表的头结点) int i = indexFor(hash, table.length); //取得链表头,映射到数组同一位置的元素被组织成一个链表(冲突解决方法) Entry<K,V> e = table[i]; while (true) { //如果查找到链表末尾,表示没有查找到,返回null if (e == null) return null; //判断所以给key,与存储在HashTable中key是否完全相等 //如果完全相等,则查找到目标key-value对,返回value object //x与y两个key完全相等的条件:x == y || x.equals(y); //也就是说如果两个key内容相等或者指向同一个对象引用,均算作相等。 if (e.hash == hash && eq(k, e.key)) return e.value; //继续查找下一个元素 e = e.next; } }
put(k,V)
<span style="white-space: pre;"> public V put(K key, V value) {</span>
//如果key为null,通过maskNull转换成Object对象进行内部存储操作 K k = maskNull(key); //计算key对应的hash值,确定在Hash数组中的位置 int hash = hash(k); int i = indexFor(hash, table.length); //找到链表的头结点后,首先在链表中确定此key是否被其它的key-value对所占用 for (Entry<K,V> e = table[i]; e != null; e = e.next) { [b]//如果此key已经在HashMap中存在,则更新此key-value中的value值[/b] if (e.hash == hash && eq(k, e.key)) { V oldValue = e.value; e.value = value; e.recordAccess(this); //并且返回oldValue return oldValue; } } modCount++; //确定此key不存在HashMap中后,直接将key-value存入HashMap中,也就是插入链表中 [b]addEntry(hash, k, value, i);[/b] return null; } void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; //Entry内部用来封装key-value对 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); /[b]/如果当前HashMap中存储的k-v对数目(size)超过threshold,需要对整个HashMap进行扩容 //扩展成原来的2倍大小[/b] if (size++ >= threshold) resize(2 * table.length); } void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //为HashMap分配新的内存空间 Entry[] newTable = new Entry[newCapacity]; //迁移旧HashMap上的数据到新的空间newTable上 transfer(newTable); table = newTable; //重新计算负载上限 threshold = (int)(newCapacity * loadFactor); } void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { //取出数组元素中的链表头结点 Entry<K,V> e = src[j]; //如果链表不是空的 if (e != null) { src[j] = null; //为链表中的每一个结点重新分配新的位置在newTable当中 //因为位置的计算是hash & (length-1);length改变了,所以存储位置也跟着变了 do { Entry<K,V> next = e.next; //计算结点e的新的存储位置在newTable中 int i = indexFor(e.hash, newCapacity); //将结点添加到链表newTable[i]中 e.next = newTable[i]; newTable[i] = e; //e指向下一个结点 e = next; } while (e != null); } } }
remove(k)方法
<span style="white-space: pre;"> public V remove(Object key) {</span>
Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value); } Entry<K,V> removeEntryForKey(Object key) { //根据key计算hash值,映射到数组下标位置,找到链表头 Object k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; while (e != null) { Entry<K,V> next = e.next; //查找封装目标key-value的Entry if (e.hash == hash && eq(k, e.key)) { modCount++; size--; [b]//这种情况只有在链表中只有一个结点时候才会才成立[/b] if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } //在遍历过程中记录当前结点e的前驱 prev = e; e = next; } return e; }
eq()用于比较两个key是否相等
两个key相等的条件是:(1).两者指向同一个引用
(2).两者equals相等(考虑是否要重写key类的equals(),根据需要)
<span style="white-space: pre;"> static boolean eq(Object x, Object y) {</span>
return x == y || x.equals(y); }
发表评论
-
以一个枢纽值二分一个数组
2012-02-08 15:17 866划分算法由两个指针开始,分别指向数组的两头。在左边的指 ... -
好玩的游戏合集~~
2012-02-07 16:19 1048因为刚接触windows phone不久,自己平时收藏 ... -
Linux下Mysql表名区分大小写
2012-02-04 13:58 11431、Linux下mysql安装完后是默认:区分表名的 ... -
如何使SOLR系统自动AUTO COMMIT
2012-02-03 16:49 904转自:http://blog.csdn.net/thu ... -
Servlet多线程
2012-02-03 13:24 920? <div class="Se ... -
构造方法,重载,多个,无参,参数,this,super
2012-02-02 14:29 2414构造方法名([参数列表]){ ? [this([参数 ... -
Could not find a JavaScript runtime
2012-02-02 13:19 775My Rails3.1 app worked fine ... -
现在在郑州做java开发想去深圳
2012-01-31 14:43 916 &nb ... -
java的ProcessBuilder阻塞问题
2011-12-28 18:08 1344<span style="color: ... -
SQL 笔试题(摘)
2011-12-28 11:29 1001(1)表名:购物信息 购物人 商品名称 ... -
HOWTO: Disable HTTP Methods in Apache
2011-12-21 14:59 918<h3 class="entry-h ... -
手机wifi传文件的一简单代码
2011-12-20 13:39 1313手机与笔记本传文件的方法有很多种,如果不方便使用蓝牙 ... -
xml格式字符串与java对象互转
2011-12-20 11:34 1433import java.lang.reflect. ... -
《使用 Microsoft .NET 的企业解决方案模式》读书笔记2
2011-12-19 10:39 710第2章 组织模式 面向对象编程的基本元素是类。但是,如 ... -
在网页中插入RM视频文件的历程
2011-12-19 08:59 980俺最早想到的是直接利用Frontpage2003,看看 ... -
MapXtreme2004代码 简单专题图的显示
2011-12-15 14:24 712MapControl1.Map.Clear();< ... -
注意新技术的风险是否会超过获得成功的几率
2011-12-14 18:28 360</span></span> ... -
C#打印DataGrid中的数据
2011-12-14 16:59 1338<span style="" ... -
推荐三本书
2011-12-13 15:19 693推荐最近一直在看的三本书,很好,真的很好,别的也没什么 ... -
关于提高自己JAVA水平的十大技术讨论(转)
2011-12-13 14:29 1023本文来自<font col ...
相关推荐
1.面试必考之HashMap源码分析与实现 伸缩性角度看HashMap的不足
面试中,HashMap的源码分析与实现是一个常见的考察点,因为它涉及到数据结构、并发处理和性能优化等多个核心领域。本篇文章将深入探讨HashMap的内部工作原理、关键特性以及其在实际应用中的考量因素。 HashMap基于...
《HashMap 源码解析——JDK11版本》 HashMap是Java中广泛使用的非同步散列表,其设计和实现是高效且灵活的。在JDK1.8之前,HashMap的底层数据结构采用的是数组+链表的方式,这种方式称为“拉链法”来解决哈希冲突。...
hashmap的原理啊思想。
#### 二、HashMap线程安全问题分析 在多线程环境中,`HashMap`的主要线程安全问题包括但不限于: 1. **链表死循环问题**:在JDK 1.7中,当多个线程同时进行`put`操作时,可能会出现链表死循环的情况,这是一个严重...
Java集合系列之HashMap源码分析 Java集合系列之HashMap源码分析是Java集合系列中的一篇非常重要的文章,它详细介绍了Java集合系列之HashMap源码,具有很高的参考价值。下面我们将对HashMap源码进行详细的分析。 ...
哈希映射(HashMap)是Java编程语言中广泛使用的数据结构之一,主要提供键值对的存储和查找功能。HashMap的实现基于哈希表的概念,它通过计算对象的哈希码来快速定位数据,从而实现了O(1)的平均时间复杂度。在深入...
微信小程序详细图文教程 泉州大白网络科技 目录 一.微信小程序申请 二....1.申请服务器 2.部署服务器 3.域名申请和配置 三....一....申请,并认证(未认证不能发布,认证需要300元,目前只支持企业认证)详细见官网说明。...
JAVA之hashmap源码分析 Mobile-Dev-Analysis Analysis of android or java 红岩网校工作站移动开发部学员分组学习 为了让大家学的更加坚固,采取小组学习的方式帮助大家学习,同时在学习研究的过程中需要不断的做...
JAVA之hashmap源码分析 无头Android堆分析器 “哈哈!” -纳尔逊 此存储库已弃用 创建该项目的目的是通过重新打包其他存储库中的堆转储解析器来提供堆转储解析器。 LeakCanary现在有它自己的。 该解析器在Maven ...
JAVA之hashmap源码分析Superword是Java开源项目,致力于研究英语单词分析和辅助阅读,包括但不限于拼写相似度,定义相似度,发音相似度,拼写转换规则,前缀和动态前缀,后缀以及动态后缀,词根,复合词,文本辅助...
四、HashMap源码分析 HashMap是一种基于散列表实现的Map,提供了快速的键值对存储和检索能力。HashMap的继承体系中,它继承了AbstractMap,实现了Map接口。 HashMap的主要属性包括键值对数组table、键值对个数size...
面试必考之HashMap源码分析与实现 ,微服务架构之Spring Cloud Eureka 场景分析与实战,高性能必学之Mysql主从架构实践 ,架构师不得不知道的Spring事物不能回滚的深层次原因 ,分库分表之后分布式下如何保证ID全局...
在本文中,我们将深入探讨如何使用Java在Android平台上实现模拟登录知乎并抓取用户信息的过程。... 首先,我们需要了解的是Android的网络访问机制。Android系统为了安全性和用户体验,对网络访问进行了限制,必须在...
《HashMap源码剖析》 HashMap是Java编程语言中一个非常重要的数据结构,它在实际开发中被广泛应用。作为集合框架的一部分,HashMap实现了Map接口,提供了高效、非同步的键值对存储功能。在这个10页的PDF文档中,...
本篇文章将通过分析一个名为"MyHashMap"的手写HashMap源码,来探讨HashMap的内部机制,帮助提升编程能力。 首先,HashMap的核心是基于哈希表的数据结构,它利用键(Key)的哈希函数将键映射到数组的特定位置,从而...