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

如果任何人让我描述一下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对象总是被存储在数组的第一个位置

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索java
hashmap
深入理解hashmap、hashmap扩容机制、hashmap的扩容机制、hashmap的存储机制、hashmap存储机制,以便于您获取更多的相关知识。

时间: 2024-12-03 08:48:14

深入理解Java中的HashMap的实现机制_java的相关文章

深入理解java中i++和++i的区别_java

今天简单谈谈关于java的一个误区,相信很多刚开始学习java的朋友都会遇到这个问题,虽然问题很简单,但是经常容易搞混,说说java的i++和++i的区别. 先看一下代码: <span style="font-size:18px;">public class test { public static void main(String[] args) { int i = 0; for (int j = 0; j < 10; j++) { i=i++; } System.

剖析Java中的事件处理与异常处理机制_java

一.事件处理其实,由事件处理这个名字自然就想到MFC中的消息响应机制,就我的体会,它们应该算是南桔北枳的情形吧,我怀疑Java中的事件处理这个"新瓶"应是装的MFC中的消息响应这个"旧酒".     所谓的"事件"即如键盘按键.鼠标点击等这类由动作或什么导致某个状态改变并需要对这个改变作相应响应的这类改变.我们可以将Java中的事件分为按钮.鼠标.键盘.窗口.其它事件这几大类.    事件处理模型  1.   基于继承的事件处理模型(JDK1.0

10分钟带你理解Java中的弱引用_java

前言 本文尝试从What.Why.How这三个角度来探索Java中的弱引用,帮助大家理解Java中弱引用的定义.基本使用场景和使用方法. 一. What--什么是弱引用? Java中的弱引用具体指的是java.lang.ref.WeakReference<T>类,我们首先来看一下官方文档对它做的说明:      弱引用对象的存在不会阻止它所指向的对象被垃圾回收器回收.弱引用最常见的用途是实现规范映射(canonicalizing mappings,比如哈希表).      假设垃圾收集器在某个

如何理解java中的空实现

问题描述 如何理解java中的空实现 新建一个类实现某接口,然后这个类的构造方法重写接口的某个方法,这个方法没有方法体 也就是重写其抽象方法,那么这样是不是控实现呢 解决方案 没有空实现这个概念,只有抽象类中的抽象函数,和接口中的函数定义,它们只有函数定义. 有的时候,对于void类型的函数,我们只打上括号,没有任何代码,这通常被称为空实现,或者桩函数. 解决方案二: java 中的空指针,不为空,的理解CallBack 的理解和java实现对java 接口和实现的理解 解决方案三: java高

如何理解java中 对象.this方法 还有 类.this.方法的 意义

问题描述 如何理解java中 对象.this方法 还有 类.this.方法的 意义 如何理解java中 对象.this方法 还有 类.this.方法的 意义 有没有这两种语法规则呢 解决方案 this.方法是在某个对象的实例方法内,this代表当前实例.一般情况下不用写,除非它和参数重名才需要: class A { int a; int b; public void seta(int a) { this.a = a; //因为参数a和成员变量a都叫a,所以需要区分. b = a; //相当于th

如何理解java中的某些方法不是线程安全的(不能同步访问)。

问题描述 如何理解java中的某些方法不是线程安全的(不能同步访问). 如何理解java中的某些方法不是线程安全的(不能同步访问). 能同步访问的方法有哪些,如何判断一个方法能不能同步访问 解决方案 不是线程安全的(不能同步访问) 你说反了.不是线程安全的才需要同步访问.同步访问的意思就是串行执行,等前面执行完了,再执行后面的. 线程不安全的场合很多,比如像操作系统中的用户界面.打印机等外设.控制台输出,都不允许并发(设想两个程序同时要输出文字到同一个屏幕,那还不乱套了) 在代码中,每个线程有自

java编程思想-如何更好的理解java中的面向对象

问题描述 如何更好的理解java中的面向对象 现在学到java的面向对象,有时候会把很多知识点弄混乱,怎么样才能把面向对象的知识点梳理好啊 解决方案 万物皆对象!!!你可以这样理解,面向对象的思想主要是让我们程序员更好的理解编程,因为和机器交流语法比较难懂,所有为了让编程更简单人们就提出了面向对象的思想.就是我们将任何一个东西都可以想象成一个有血有肉的.比如一本书.我们可以知道书可以有书名,可以页数,可以有类容等等这就是我们所说的属性,书可能还有翻页等这些动作这就相当于方法(有些语言叫做函数)了

理解java中的深复制和浅复制_java

 Java语言的一个优点就是取消了指针的概念,但也导致了许多程序员在编程中常常忽略了对象与引用的区别,本文会试图澄清这一概念.并且由于Java不能通过简单的赋值来解决对象复制的问题,在开发过程中,也常常要要应用clone()方法来复制对象.本文会让你了解什么是影子clone与深度clone,认识它们的区别.优点及缺点.       看到这个标题,是不是有点困惑:Java语言明确说明取消了指针,因为指针往往是在带来方便的同时也是导致代码不安全的根源,同时也会使程序的变得非常复杂难以理解,滥用指针写

深入理解java中for和foreach循环_java

•for循环中的循环条件中的变量只求一次值!具体看最后的图片 •foreach语句是java5新增,在遍历数组.集合的时候,foreach拥有不错的性能. •foreach是for语句的简化,但是foreach并不能替代for循环.可以这么说,任何foreach都能改写为for循环,但是反之则行不通. •foreach不是java中的关键字.foreach的循环对象一般是一个集合,List.ArrayList.LinkedList.Vector.数组等. •foreach的格式: for(元素类