- 浏览: 16620 次
- 性别:
-
最新评论
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-->
- 大小: 7.3 KB
发表评论
相关推荐
通过`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接口，能够存储键值对数据。其内部使用哈希表来存储数据...