Java中HashMap的实现机制详解编程语言
数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。
数组:存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;
Java中主要是ArrayList和Vector,动态数组
链表:存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易。
java中的LinkedList实现了双向链表
哈希表:一种寻址容易、插入也容易的数据结构
哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法—— 拉链法,我们可以理解为“链表的数组” ,如图:
从上图我们可以发现哈希表是由数组+链表组成的
HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。
首先HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。
HashMap的存取实现
既然是线性数组,为什么能随机存取?这里HashMap用了一个小算法,大致是这样实现:
// 存储时: int hash = key.hashCode(); // 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值 int index = hash % Entry[].length; Entry[index] = value; // 取值时: int hash = key.hashCode(); int index = hash % Entry[].length; return Entry[index];1)put 疑问:如果两个key通过hash%Entry[].length得到的index相同,会不会有覆盖的危险? 这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方, 第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止,HashMap的大致实现,我们应该已经清楚了。
span public V put(K key, V value) { if (key == null) return putForNullKey(value); //null总是放在数组的第一个链表中 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); //遍历链表 for (Entry K,V e = table[i]; e != null; e = e.next) { Object k; //如果key在链表中已存在,则替换为新value if (e.hash == hash ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; modCount++; addEntry(hash, key, value, i); return null; void addEntry(int hash, K key, V value, int bucketIndex) { Entry K,V e = table[bucketIndex]; table[bucketIndex] = new Entry K,V (hash, key, value, e); //参数e, 是Entry.next //如果size超过threshold,则扩充table大小。再散列 if (size++ = threshold) resize(2 * table.length); }
当然HashMap里面也包含一些优化方面的实现,这里也说一下。比如:Entry[]的长度一定后,随着map里面数据的越来越长,这样同一个index的链就会很长,会不会影响性能?HashMap里面设置一个因子,随着map的size越来越大,Entry[]会以一定的规则加长长度。
2)getspan public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); //先定位到数组元素,再遍历该元素处的链表 for (Entry K,V e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash ((k = e.key) == key || key.equals(k))) return e.value; return null; } span3)null key的存取
null key总是存放在Entry[]数组的第一个元素。
private V putForNullKey(V value) { for (Entry K,V e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; modCount++; addEntry(0, null, value, 0); return null; private V getForNullKey() { for (Entry K,V e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; return null; }
4)确定数组index:hashcode % table.length取模
HashMap存取时,都需要计算当前key应该对应Entry[]数组哪个元素,即计算数组下标;
indexFor中的h (length-1)就相当于h%length,用于计算index也就是在table数组中的下标
hash方法是对hashcode进行二次散列,以获得更好的散列值
为了更好理解这里我们可以把这两个方法简化为 int index= key.hashCode()/table.length,以put中的方法为例可以这样替换
算法如下:
int hash = hash(key.hashCode());//计算hash
int i = indexFor(hash,table.length);//计算在数组中的存储位置
//上面两行可以这样简化:
int i = key.hashCode()%table.length;
static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h 20) ^ (h 12); return h ^ (h 7) ^ (h static int indexFor(int h, int length) { return h (length-1); }
HashMap默认初始化时会创建一个默认容量为16的Entry数组,默认加载因子为0.75,同时设置临界值为16*0.75
注意table初始大小并不是构造函数中的initialCapacity!!
而是 = initialCapacity的2的n次幂!!!!
6)clear()方法 clear方法非常简单,就是遍历table然后把每个位置置为null,同时修改元素个数为0需要注意的是clear方法只会清楚里面的元素,并不会重置capactiy
containsKey方法是先计算hash然后使用hash和table.length取摸得到index值,遍历table[index]元素查找是否包含key相同的值
span public boolean containsKey(Object key) { return getEntry(key) != null; final Entry K,V getEntry(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); for (Entry K,V e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash ((k = e.key) == key || (key != null key.equals(k)))) return e; return null; }
containsValue方法就比较粗暴了,就是直接遍历所有元素直到找到value,由此可见HashMap的containsValue方法本质上和普通数组和list的contains方法没什么区别,你别指望它会像containsKey那么高效
public boolean containsValue(Object value) { if (value == null) return containsNullValue(); Entry[] tab = table; for (int i = 0; i tab.length ; i++) for (Entry e = tab[i] ; e != null ; e = e.next) if (value.equals(e.value)) return true; return false; }8)remove方法
remove方法和put get类似,计算hash,计算index,然后遍历查找,将找到的元素从table[index]链表移除
public V remove(Object key) { Entry K,V e = removeEntryForKey(key); return (e == null ? null : e.value); final Entry K,V removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); 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; Object k; if (e.hash == hash ((k = e.key) == key || (key != null key.equals(k)))) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; prev = e; e = next; return e; }解决hash冲突的办法 开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列) 建立一个公共溢出区
Java中hashmap的解决办法就是采用的链地址法。
再散列rehash过程当哈希表的容量超过默认容量时,必须调整table的大小。当容量已经达到最大可能值时,那么该方法就将容量调整到Integer.MAX_VALUE返回,这时,需要创建一张新表,将原表的映射到新表中。
具体过程为:先创建一个容量为table.length*2的新table,修改临界值,然后把table里面元素计算hash值并使用hash与table.length*2重新计算index放入到新的table里面
这里需要注意下是用每个元素的hash全部重新计算index,而不是简单的把原table对应index位置元素简单的移动到新table对应位置
/** * Rehashes the contents of this map into a new array with a * larger capacity. This method is called automatically when the * number of keys in this map reaches its threshold. * If current capacity is MAXIMUM_CAPACITY, this method does not * resize the map, but sets threshold to Integer.MAX_VALUE. * This has the effect of preventing future calls. * @param newCapacity the new capacity, MUST be a power of two; * must be greater than current capacity unless current * capacity is MAXIMUM_CAPACITY (in which case value * is irrelevant). void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); /** * Transfers all entries from current table to newTable. 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; do { Entry K,V next = e.next; //重新计算index int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); }
转载出处:
http://www.cnblogs.com/lzrabbit/p/3721067.html
转载出处:
http://blog.csdn.net/vking_wang/article/details/14166593
HashMap的性能参数:
HashMap 包含如下几个构造器:
HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。
HashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子为 0.75 的 HashMap。
HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap。
HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数,它们是初始容量initialCapacity和加载因子loadFactor。
initialCapacity:HashMap的最大容量,即为底层数组的长度。
loadFactor:负载因子loadFactor定义为:散列表的实际元素数目(n)/ 散列表的容量(m)。
负载因子衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是O(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。
HashMap的实现中,通过threshold字段来判断HashMap的最大容量:
Java代码
![收藏代码](http://blog.ytso.com/zb_users/plugin/LazyLoad/usr/loading.gif)
结合负载因子的定义公式可知,threshold就是在此loadFactor和capacity对应下允许的最大元素数目,超过这个数目就重新resize,以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时, resize后的HashMap容量是容量的两倍:
Java代码
![收藏代码](http://blog.ytso.com/zb_users/plugin/LazyLoad/usr/loading.gif)
Fail-Fast机制:
我们知道java.util.HashMap不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map,那么将抛出ConcurrentModificationException,这就是所谓fail-fast策略。
这一策略在源码中的实现是通过modCount域,modCount顾名思义就是修改次数,对HashMap内容的修改都将增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。
Java代码
在迭代过程中,判断modCount跟expectedModCount是否相等,如果不相等就表示已经有其他线程修改了Map:
注意到modCount声明为volatile,保证线程之间修改的可见性。
Java代码
在HashMap的API中指出:
由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器本身的 remove 方法,其他任何时间任何方式的修改,迭代器都将抛出ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不冒在将来不确定的时间发生任意不确定行为的风险。
注意,迭代器的快速失败行为不能得到保证,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/13770.html
cjava相关文章
- java jersey使用总结_Java Jersey2使用总结
- java 读取字符串文件_Java读取文件为字符串
- java在线播放_Java实现视频在线播放flv视频
- java生成高质量缩略图的代码实现详解编程语言
- Java实现字符串反转的8种9种方法详解编程语言
- Java实现 图片水印或者文字水印详解编程语言
- Java 冒泡排序算法实现详解编程语言
- java实现RSA加密和解密详解编程语言
- Java插入排序实现详解编程语言
- Java 通过 BigDecimal 实现数值四舍五入详解编程语言
- Java程序优化细节详解编程语言
- java字符串的替换replace、replaceAll、replaceFirst的区别详解编程语言
- 使用Java连接SQL Server数据库,快速高效地管理数据(java连接sqlserver数据库)