欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

深入理解Java中的HashMap的实现机制

程序员文章站 2024-03-05 17:10:25
如果任何人让我描述一下hashmap的工作机制的话,我就简单的回答:“基于hash的规则”。这句话非常简单,但是要理解这句话之前,首先我们得了解什么是哈希,不是么? 什么...

如果任何人让我描述一下hashmap的工作机制的话,我就简单的回答:“基于hash的规则”。这句话非常简单,但是要理解这句话之前,首先我们得了解什么是哈希,不是么?

什么是哈希
哈希简单的说就是对变量/对象的属性应用某种算法后得到的一个唯一的串,用这个串来确定变量/对象的唯一性。一个正确的哈希函数必须遵守这个准则。

当哈希函数应用在相同的对象或者equal的对象的时候,每次执行都应该返回相同的值。换句话说,两个相等的对象应该有相同的hashcode。

注:所有java对象都从object类继承了一个默认的hashcode()方法。这个方法将对象在内存中的地址作为整数返回,这是一个很好的hash实现,他确保了不同的对象拥有不同的hashcode。

关于entry类的一点介绍
一个map的定义是:一个映射键(key)到值(value)的对象。非常简单对吧。

所以,在hashmap中一定有一定的机制来存储这些键值对。使得,hashmap有一个 内部类entry,看起来像这样。
 

static class entry<k,v> implements
 
map.entry<k,v>
{
    final k key;
    v value;
    entry<k,v> next;
    final int hash;
    ...//more code goes here
}

当然,entry类有属性用来存储键值对映射。key被final标记,除了key和value ,我们还能看到两个变量next和hash。接下来我们试着理解这些变量的含义。

put()方法实际上做了什么
再进一步看put方法的实现之前,我们有必要看一看entry实例在数组中的存储, hashmap中是这样定义的:
 

/**
   * the table, resized as necessary. length must always be a power of two.
   */
  transient entry[] table;
现在再来看put方法的实现。
 
/**
* associates the specified value with the specified key in this map.
* if the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
*        
 
<tt>null</tt> if there was no mapping for <tt>key</tt>.
*         (a
 
<tt>null</tt> return can also indicate that the map
*         previously
 
associated <tt>null</tt> with <tt>key</tt>.)
*/
public v put(k key, v value) {
if (key == null)
return putfornullkey(value);
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;
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;
}

让我们一步一步的看
首先,检查key是否为null,如果key是null值被存在table[0]的位置,因为null 的hashcode始终为0
接下来,通过key的hashcode()方法计算了这个key的hash值,这个hash值被用来 计算存储entry对象的数组中的位置。jdk的设计者假设会有一些人可能写出非常差的hashcode()方法,会出现一些 非常大或者非常小的hash值。为了解决这个问题,他们引入了另外一个hash函数,接受对象的hashcode(),并转换 到适合数组的容量大小。

接着是indexfor(hash,table,length)方法,这个方法计算了entry对象存储 的准确位置。
接下来就是主要的部分,我们都知道两个不相等的对象可能拥有过相同的 hashcode值,两个不同的对象是怎么存储在相同的位置[叫做bucket]呢?
答案是linkedlist。如果你记得,entry类有一个next变量,这个变量总是指向 链中的下一个变量,这完全符合链表的特点。

所以,在发生碰撞的时候,entry对象会被以链表的形式存储起来,当一个entry 对象需要被存储的时候,hashmap检查该位置是否已近有了一个entry对象,如果没有就存在那里,如果有了就检查 她的next属性,如果是空,当前的entry对象就作为已经存储的entry对象的下一个节点,依次类推。

如果我们给已经存在的key存入另一个value会怎么样的?逻辑上,旧的值将被替 换掉。在检测了entry对象的存储位置后,hashmap将会遍历那个位置的entry链表,对每一个entry调用equals方法 ,这个链表中的所有对象都具有相同的hashcode()而equals方法都不等。如果发现equals方法有相等的就执行替换 。

在这种方式下hashmap就能保证key的唯一性。

get方法的工作机制
现在我们已经了解了hashmap中存储键值对的机制。下一个问题是:怎样从一个 hashmap中查询结果。
其实逻辑跟put是一样的,如果传入的key有匹配就将该位置的value返回,如果 没有就返回null.
 

/**
* returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>more formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}.  (there can be at most one such mapping.)
*
* <p>a return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* the {@link #containskey containskey} operation may be used to
* distinguish these two cases.
*
* @see #put(object, object)
*/
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;
}

上面的代码看起来跟put()方法很像,除了if (e.hash == hash && ((k = e.key) == key || key.equals(k)))。

注意点

  •     存储entry对象的数据结构是一个叫做entry类型的table数组。
  •     数组中一个特定的索引位置称为bucket,因为它可以容纳一个linkedlist 的第一个元素的对象。
  •     key对象的hashcode()需要用来计算entry对象的存储位置。
  •     key对象的equals()方法需要用来维持map中对象的唯一性。
  •     get()和put()方法跟value对象的hashcode和equals方法无关。
  •     null的hashcode总是0,这样的entry对象总是被存储在数组的第一个位置