- 浏览: 16686 次
- 性别:
最新评论
HashMap的实现过程
一、从Hash说起
还记得,我们第一次接触Hash这个词,是在学数据结构,讲到查找一节,引入哈希表的时候。
对于像顺序查找、折半查找、二叉排序树查找等查找,关键字在存储结构中的位置是随机的,即关键字与它的存储位置之间存在着不确定性的关系,因而这样的查找方法是建立在“比较”的基础上。而查找的效率也主要依赖于查找过程中所进行比较的次数。
哈希表的引入,提供了有别于上面所说查找的另外一种查找方式。即关键字与它所存储的位置之间有着一个确定的对应关系,这样当我们要查找指定关键字时,只要通过这样的一个映射关系,就可以得到它的存储地址,从而可以很快地找到关键字。
而这种映射关系就是所谓的哈希函数了,哈希函数的作用在于,它提供关键字到其存储地址的一种映射。不同的哈希函数,一般来说,就会有不同的映射结果。对于单值的映射来说,只要哈希函数一确定,输入相同的关键字,就会得到相同的映射结果,而输入不同的关键字,也有可能得到相同的映射结果。不过一旦出现这种现象,可就糟了,因为,如果我们直接将映射结果所指空间作为关键字的存储位置,那这样将会出现两个不同的关键字被存储在同一个存储空间中,这样肯定是不行的,所以我们必须对这样的结果还需进行一个加工处理。对于这样现象,我们叫它冲突(Hash冲突),而当冲突出现时,我们需要对它进行处理,以使得最后每个关键字都能够找到它唯一的一个存储空间。
对于冲突的处理有许多方法,在这里,我们用的是挂链法。即,当我们用哈希函数处理不同的关键字,得到相同的映射结果,我们姑且把这样相同的映射结果所对应的空间叫做“第一地址”,然后我们在“第一地址”上挂一个链表(即“第一地址”存储链表的首地址),而链表里的元素就是实实在在所保存的关键字,只要当不同的关键字通过该哈希函数得到相同的映射结果,我们就把该关键字加到“第一地址”下的链表中存储。当我们访问该关键字时,首先通过哈希函数找到“第一地址”,然后遍历链表即可。
我们用哈希表这一名词来表示存储这些关键字的结构。在这里,哈希表就是我们常说的“数组+链表”的结构了。数组空间存储就是上面所说的“第一地址”,即数组下标索引指的就是“第一地址”,通过索引,我们可以找到存有关键字的链表,然后再遍历链表就可以找到指定的关键字了。
附“哈希表”的定义(数据结构(严蔚敏版)):
哈希表:根据设定的哈希函数H(key)和处理冲突的方法,将一组关键字映像到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为哈希表,这一映像过程称为哈希造表或散列,所得存储位置称哈希地址或散列地址。
针对以上构造的哈希表,当我们存储的元素不是单值元素,而是像Map中键值对的形式的元素时,这时这种结构就是我们谈论的HashMap了,不过实际中的HashMap存储的元素还有hash值,以及指向下一个结点的引用。具体的东西,我们一看源码即可知晓。
对于Map,我们知道,有put(Object key , Object value)、get(Object key)、remove(Object key)、containsKey(Object key)、containsValue(Object value)等方法,同样,HashMap中也含有这些方法,下面我们从HashMap的源码中截取这些方法,自定义一个HashMap。
二、从源码中截取经典自定义HashMap
1、定义内部类Entry<K,V>,封装所存数据
/** * 内部类:封装数据,作为链表的结点 * @author wanghaoliang * * @param <K> * @param <V> */ static class Entry<K,V>{ K key; V value; int hash;//参与h & (length-1)的hash码值 Entry<K,V> next; Entry(K k,V v,int h,Entry<K,V> n){ key=k; value=v; hash=h; next=n; } }
2、自定义带有初始容量和装载因子的构造器
/** * 指定初始容量和装载因子的构造器 * @param initialCapacity * @param loadFactor */ public MyHashMap(int initialCapacity,float loadFactor){ //IllegalArgumentException非法参数处理 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); //初始化参数 int capacity=1; while(capacity<initialCapacity) capacity<<=1; this.loadFactor=loadFactor; //计算阀值 threshold=(int)(capacity*loadFactor); //对hash表初始化 table=new Entry[capacity]; }
3、定义put(K key,V value)等函数,关联指定的Key和Value,并加入到链表中
/** * 关联指定的Key和Value, * 如果map中已经有了指定的Key的映射,则新的value会覆盖老的value * 如果map中没有指定的Key,则调用addEntry方法,添加新的mapping * 返回老的value值 * 如果返回Null,则说明map中不存在指定 * @param key * @param value * @return */ public V put(K key,V value){ //HashMap中允许存放null键和null值 if(key==null) return putForNullKey(value); int hash = hash(key.hashCode()); int i= indexFor(hash, table.length); //遍历table,查看其中是否已有指定的Key,若有,则用新的Value覆盖旧的Value for(Entry<K,V> e=table[i];e!=null;e=e.next){ Object k=e.key; if(e.hash==hash&&(key==k||key.equals(k))){ V oldValue=e.value; e.value=value; return oldValue; } } //table中没有指定Key的映射,故加入该映射到链表中 addEntry(hash,key, value, i); return null; }
4、定义get(K key)等函数,通过指定键获取对应的Value
/**
* 返回指定的键(Key)所对应的值(Value)
* @param key
* @return
*/
public V get(K key){
if(key==null)
return getForNullKey();
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=e.key;
//先比较hash,再比较key值
if(e.hash==hash&&(key==k)||key.equals(k))
return e.value;
}
return null;
}
5、定义remove(K key)等函数,通过指定键移除对应的映射关系
/** * 移除指定的Key所对应的映射 * 返回Entry<K,V> * @param key * @return */ public Entry<K,V> removeEntryForKey(K key){ //如果key为null,则对应的hash值为0 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=e.key; //遍历链表,找到指定的结点 if(e.hash==hash&&(key==k||key.equals(k))){ size--; if(prev==e)//要删除的结点为首结点 table[i]=next; else prev.next=next; return e; } prev=e; e=next; } return e; }
6、定义containsKey(K key)和containsValue(V value)函数,判断指定的K或V是否存在于HashMap中
/** * 判断table中是否含有指定的Key * @param key * @return */ public boolean containsKey(K key){ return getEntry(key)!=null; }
/** * 判断table中是否含有指定的Value * @param value * @return */ public boolean containsValue(V 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; }
7、测试
三、源码要点分析
1、为什么table表的大小为2的幂次方?
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
我们知道,选择哈希函数构造哈希表时,应尽量避免冲突,即构造一个均匀的哈希表,使得表中的每个索引空间被映射到的概率都是均等的。对于一片有限的连续的存储空间(数组),如果将不同的关键字比较均匀地映射到这一片存储空间呢?是的,我们一般采用“除留取余法”,即拿hash%table.length所得值,作为索引空间。但是计算机对于%(取余运算)较耗时间,而计算机对于&(位与运算),即hash & (table.length-1) 却是大大地节省了时间,而只有当table.length为2的幂次方时,上面的hash & (table.length-1)才具有等价的hash%table.length效果。
2、为什么还要再哈希?
即为什么当我们调用key.hashcode()返回一个哈希值时,为什么不直接将key.hashcode()作为最终的hash值,而还要经过如下的这一操作?
/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
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 >>> 4);
}
大概看了一下源码中的对此函数的注释可知,原始的key.hashcode()返回得到的hash值,如果参与hash & (table.length-1)运算,在低字节上很容易相同,即就很容易产生冲突,为了使得冲突减少,所以系统增加了上面的这一操作,它是原始hash的补充,旨在使得key的最终的hash码值,在参与hash & (table.length-1)运算能够达到一个分布均匀的结果值,即最大化地减少冲突。
附:完整代码
package whlHashMap2; import java.util.Map; /** * 自定义HashMap * @author wanghaoliang * */ public class MyHashMap<K,V> { //最大的初始容量,必须<=2的30次方 static final int MAXIMUM_CAPACITY = 1 << 30; //阀值=capacity * load factor int threshold; //装载因子 final float loadFactor; //hash表 transient Entry[] table; //键值对的个数 transient int size; /** * 指定初始容量和装载因子的构造器 * @param initialCapacity * @param loadFactor */ public MyHashMap(int initialCapacity,float loadFactor){ //IllegalArgumentException非法参数处理 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); //初始化参数 int capacity=1; while(capacity<initialCapacity) capacity<<=1; this.loadFactor=loadFactor; //计算阀值 threshold=(int)(capacity*loadFactor); //对hash表初始化 table=new Entry[capacity]; } /** * 补充性的hash函数 * @param h * @return */ static int hash(int h){ h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } /** * 返回对应的hashCode在数组中的索引 * 等价于h%length操作 */ static int indexFor(int h, int length) { return h & (length-1); } /** * 添加链表结点 * @param hash:关键字所对应的hash值 * @param key:键值对中的Key * @param value:键值对张的Value * @param bucketIndex数组索引 */ void addEntry(int hash,K key,V value,int bucketIndex){ Entry<K,V> next=table[bucketIndex]; table[bucketIndex]=new Entry<K,V>(key,value,hash,next); if(size++ >= threshold) resize(2*table.length); } /** * 改变table的大小 * @param newCapacity:新的大小容量 * newCapacity必须满足:不超过MAXIMUM_CAPACITY,并且为2的幂次方 */ 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]; //从oldTable中转移数据到newTable中 transfer(newTable); table=newTable; threshold=(int)(newCapacity*loadFactor); } /** * 从oldTable中转移数据到newTable中 * @param 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;//清空原始Hash表 //原始链表数据在新的链表中顺序被倒置了 do{ Entry<K,V> next=e.next; int i=indexFor(e.hash, newCapacity); e.next=newTable[i]; newTable[i]=e; e=next; }while(e!=null); } } } /** * 关联指定的Key和Value, * 如果map中已经有了指定的Key的映射,则新的value会覆盖老的value * 如果map中没有指定的Key,则调用addEntry方法,添加新的mapping * 返回老的value值 * 如果返回Null,则说明map中不存在指定 * @param key * @param value * @return */ public V put(K key,V value){ //HashMap中允许存放null键和null值 if(key==null) return putForNullKey(value); int hash = hash(key.hashCode()); int i= indexFor(hash, table.length); //遍历table,查看其中是否已有指定的Key,若有,则用新的Value覆盖旧的Value for(Entry<K,V> e=table[i];e!=null;e=e.next){ Object k=e.key; if(e.hash==hash&&(key==k||key.equals(k))){ V oldValue=e.value; e.value=value; return oldValue; } } //table中没有指定Key的映射,故加入该映射到链表中 addEntry(hash,key, value, i); return null; } /** * 当Key为Null时的put(K,V)方法处理 * @param value * @return */ 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; return oldValue; } } addEntry(0, null, value, 0); return null; } /** * 返回指定的键(Key)所对应的值(Value) * @param key * @return */ public V get(K key){ if(key==null) return getForNullKey(); 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=e.key; //先比较hash,再比较key值 if(e.hash==hash&&(key==k)||key.equals(k)) return e.value; } return null; } /** * 当Key为Null时的get(K)方法处理 * @return */ private V getForNullKey(){ for(Entry<K,V> e=table[0];e!=null;e=e.next){ if(e.key==null) return e.value; } return null; } /** * 判断table中是否含有指定的Key * @param key * @return */ public boolean containsKey(K key){ return getEntry(key)!=null; } /** * 判断table中是否含有指定的Value * @param value * @return */ public boolean containsValue(V 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; } /** * 当Value为Null是的containsValue(V)方法处理 * @return */ private boolean containsNullValue(){ Entry[] tab=table; for(int i=0;i<tab.length;i++) for(Entry e=tab[i];e!=null;e=e.next) if(e.value==null) return true; return false; } /** * 返回指定Key所对应的映射 * @param key * @return */ public Entry<K,V> getEntry(K key){ //若key为null,则对应hash码值为0 int hash=(key==null)?0:hash(key.hashCode()); int i=indexFor(hash, table.length); for(Entry<K,V> e=table[i];e!=null;e=e.next){ Object k=e.key; if(e.hash==hash&&(key==k||key.equals(k))) return e; } return null; } /** * 移除指定的Key所对应的映射 * 返回Value * @param key * @return */ public V remove(K key){ Entry<K,V> e =removeEntryForKey(key); return (e ==null ? null:e.value); } /** * 移除指定的Key所对应的映射 * 返回Entry<K,V> * @param key * @return */ public Entry<K,V> removeEntryForKey(K key){ //如果key为null,则对应的hash值为0 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=e.key; //遍历链表,找到指定的结点 if(e.hash==hash&&(key==k||key.equals(k))){ size--; if(prev==e)//要删除的结点为首结点 table[i]=next; else prev.next=next; return e; } prev=e; e=next; } return e; } /** * 直接移除所指的映射 * @param o:被移除的映射对象 * @return */ public Entry<K,V> removeMapping(Object o){ if(!(o instanceof Map.Entry)) return null; Map.Entry<K, V> entry=(Map.Entry<K, V>)o; Object key=entry.getKey(); 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=e.key; if(e.hash==hash&&(key==k||key.equals(k))){ size--; if(prev==e) table[i]=next; else prev.next=next; return e; } prev=e; e=next; } return e; } /** * 内部类:封装数据,作为链表的结点 * @author wanghaoliang * * @param <K> * @param <V> */ static class Entry<K,V>{ K key; V value; int hash;//参与h & (length-1)的hash码值 Entry<K,V> next; Entry(K k,V v,int h,Entry<K,V> n){ key=k; value=v; hash=h; next=n; } } }
<!--EndFragment-->
相关推荐
通过`hashCode()`和`equals()`的合理使用,以及数组和链表的结合,HashMap实现了高效的键值对存储和查找。了解这些实现细节对于优化代码性能和避免潜在问题至关重要。在实际编程中,应充分考虑哈希冲突的处理、负载...
总的来说,通过HashMap实现词典查询,我们可以充分利用其高效的查找机制,为用户提供快速的查询服务。同时,理解HashMap的内部机制对于优化查询性能和处理潜在问题至关重要。在实际项目中,还需要考虑如何优雅地处理...
在Java编程语言中,集合框架是开发者日常工作中不可或缺的一部分,HashMap作为其中的重要成员,它的实现原理对于理解Java性能优化和数据结构有深远的意义。HashMap是一个基于哈希表的数据结构,它实现了Map接口,...
《Jdk1.8中的HashMap实现原理》 HashMap作为Java编程语言中常用的数据结构,它在Jdk1.8中的实现结合了哈希表、链表以及红黑树的特性,提供高效且灵活的键值对存储功能。本文将深入探讨HashMap的内部结构、工作原理...
在resize()方法的实现中,我们可以看到HashMap使用了power-of-two expansion机制,即每次扩容时,数组的长度都会翻倍。这使得HashMap的扩容机制更加高效。同时,在resize()方法中,我们还可以看到HashMap使用了 ...
HashMap实现了Map接口,提供了所有映射操作。它不保证映射的顺序,尤其在多线程环境下,映射的顺序可能会发生变化。HashMap通过哈希函数来计算键(key)在数组中的位置,以便快速访问。 2. **数据结构**: HashMap...
### HashMap的实现原理 #### 1. HashMap概述 HashMap 是 Java 集合框架中一个非常重要的类,它实现了 Map 接口,并提供了基于哈希表的存储方式。与其它 Map 实现不同的是,HashMap 允许使用 `null` 键和 `null` 值...
HashMap 源码实现红黑树添加元素和删除元素 HashMap 中使用红黑树来存储元素,是为了提高查找、插入和删除操作的性能。红黑树是一种自平衡二叉树,可以保持二叉树的平衡,从而获得较高的查找性能。 红黑树的创建...
以下是对JDK 1.8 HashMap实现原理的详细解释。 首先,HashMap是一个基于哈希表的数据结构,它实现了Map接口。它不保证映射的顺序,并且是非同步的。这意味着在多线程环境中,如果不进行同步控制,可能会出现并发...
《HashMap底层实现原理》 HashMap是Java编程语言中一个非常重要的数据结构,它在实际开发中被广泛应用。HashMap提供了一种高效、灵活的方式来存储和检索键值对数据,它的核心特性是快速查找,通常时间复杂度为O(1)...
面试中,HashMap的源码分析与实现是一个常见的考察点,因为它涉及到数据结构、并发处理和性能优化等多个核心领域。本篇文章将深入探讨HashMap的内部工作原理、关键特性以及其在实际应用中的考量因素。 HashMap基于...
HashMap是Java集合框架的一个重要组成部分,它实现了Map接口,能够存储键值对映射。在Java编程语言中,最基本的数据结构有两种:数组和引用(模拟指针)。所有的复杂数据结构都可以基于这两种基本结构构建出来,...
### HashMap中的Hash函数构造问题详解 #### 一、引言 在Java中,`HashMap`是一种非常常用的集合类,它提供了基于键值对的数据存储方式。`HashMap`内部使用哈希表来存储数据,其中最关键的部分就是哈希函数的设计。...
ConcurrentHashMap是线程安全的HashMap实现,它使用分段锁(Segment)来提高并发性能。在put过程中,首先根据键的哈希值确定所在的段,然后在该段上加锁,执行put操作。这样可以避免全局锁,提升并发效率。每个段...
HashSet是基于HashMap实现的,它不存储值,只存储键。当向HashSet添加元素时,实际上是在HashMap中添加键,而值是默认的null。由于HashSet没有值的概念,所以它不提供键值对的关联操作,仅提供基本的添加、删除和...
这个过程虽然消耗资源,但是能保持HashMap的高效性能。 11. **HashMap的实现细节**:在Java 8之后,为了优化性能,当链表长度达到8时,HashMap会将链表转换为红黑树,这降低了查找、插入和删除的时间复杂度,尤其是...
下面我们将深入探讨 HashMap 的数据结构、 put 方法的实现细节和 Hash 码的计算过程。 HashMap 的数据结构 HashMap 的数据结构可以分为两部分:数组和链表。数组是 HashMap 的基本结构,链表是数组元素的具体实现...
接下来的部分内容则详细展示了如何利用HashMap实现缓存功能。 ### HashMap作为缓存机制 #### 基本概念与原理 HashMap是Java集合框架的一部分,它实现了Map接口,能够存储键值对数据。其内部使用哈希表来存储数据...