java中HashMap的原理分析

我们先来看这样的一道面试题:

在 HashMap 中存放的一系列键值对,其中键为某个我们自定义的类型。放入 HashMap 后,我们在外部把某一个 key 的属性进行更改,然后我们再用这个 key 从 HashMap 里取出元素,这时候 HashMap 会返回什么?

文中已给出示例代码与答案,但关于HashMap的原理没有做出解释。

1. 特性

我们可以用任何类作为HashMap的key,但是对于这些类应该有什么限制条件呢?且看下面的代码:

public class Person {
  private String name;

  public Person(String name) {
    this.name = name;
  }
}

Map<Person, String> testMap = new HashMap<>();
testMap.put(new Person("hello"), "world");
testMap.get(new Person("hello")); // ---> null

本是想取出具有相等字段值Person类的value,结果却是null。对HashMap稍有了解的人看出来——Person类并没有override hashcode方法,导致其继承的是Object的hashcode(返回是其内存地址)。这也是为什么常用不变类如String(或Integer等)做为HashMap的key的原因。那么,HashMap是如何利用hashcode给key做快速索引的呢?

2. 原理

首先,我们来看《Thinking in Java》中一个简单HashMap的实现方案:

//: containers/SimpleHashMap.java
// A demonstration hashed Map.
import java.util.*;
import net.mindview.util.*;

public class SimpleHashMap<K,V> extends AbstractMap<K,V> {
 // Choose a prime number for the hash table size, to achieve a uniform distribution:
 static final int SIZE = 997;
 // You can't have a physical array of generics, but you can upcast to one:
 @SuppressWarnings("unchecked")
 LinkedList<MapEntry<K,V>>[] buckets =
  new LinkedList[SIZE];
 public V put(K key, V value) {
  V oldValue = null;
  int index = Math.abs(key.hashCode()) % SIZE;
  if(buckets[index] == null)
   buckets[index] = new LinkedList<MapEntry<K,V>>();
  LinkedList<MapEntry<K,V>> bucket = buckets[index];
  MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
  boolean found = false;
  ListIterator<MapEntry<K,V>> it = bucket.listIterator();
  while(it.hasNext()) {
   MapEntry<K,V> iPair = it.next();
   if(iPair.getKey().equals(key)) {
    oldValue = iPair.getValue();
    it.set(pair); // Replace old with new
    found = true;
    break;
   }
  }
  if(!found)
   buckets[index].add(pair);
  return oldValue;
 }
 public V get(Object key) {
  int index = Math.abs(key.hashCode()) % SIZE;
  if(buckets[index] == null) return null;
  for(MapEntry<K,V> iPair : buckets[index])
   if(iPair.getKey().equals(key))
    return iPair.getValue();
  return null;
 }
 public Set<Map.Entry<K,V>> entrySet() {
  Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
  for(LinkedList<MapEntry<K,V>> bucket : buckets) {
   if(bucket == null) continue;
   for(MapEntry<K,V> mpair : bucket)
    set.add(mpair);
  }
  return set;
 }
 public static void main(String[] args) {
  SimpleHashMap<String,String> m =
   new SimpleHashMap<String,String>();
  m.putAll(Countries.capitals(25));
  System.out.println(m);
  System.out.println(m.get("ERITREA"));
  System.out.println(m.entrySet());
 }
}

SimpleHashMap构造一个hash表来存储key,hash函数是取模运算Math.abs(key.hashCode()) % SIZE,采用链表法解决hash冲突;buckets的每一个槽位对应存放具有相同(hash后)index值的Map.Entry,如下图所示:

JDK的HashMap的实现原理与之相类似,其采用链地址的hash表table存储Map.Entry:

/**
 * The table, resized as necessary. Length MUST Always be a power of two.
 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

static class Entry<K,V> implements Map.Entry<K,V> {
  final K key;
  V value;
  Entry<K,V> next;
  int hash;
  …
}

Map.Entry的index是对key的hashcode进行hash后所得。当要get key对应的value时,则对key计算其index,然后在table中取出Map.Entry即可得到,具体参看代码:

public V get(Object key) {
  if (key == null)
    return getForNullKey();
  Entry<K,V> entry = getEntry(key);

  return null == entry ? null : entry.getValue();
}

final Entry<K,V> getEntry(Object key) {
  if (size == 0) {
    return null;
  }

  int hash = (key == null) ? 0 : hash(key);
  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;
}

可见,hashcode直接影响HashMap的hash函数的效率——好的hashcode会极大减少hash冲突,提高查询性能。同时,这也解释开篇提出的两个问题:如果自定义的类做HashMap的key,则hashcode的计算应涵盖构造函数的所有字段,否则有可能得到null。

(0)

相关推荐

  • Java8 HashMap的实现原理分析

    前言:Java8之后新增挺多新东西,在网上找了些相关资料,关于HashMap在自己被血虐之后痛定思痛决定整理一下相关知识方便自己看.图和有些内容参考的这个文章:http://www.jb51.net/article/80446.htm HashMap的存储结构如图:一个桶(bucket)上的节点多于8个则存储结构是红黑树,小于8个是单向链表. 1:HashMap的一些属性 public class HashMap<k,v> extends AbstractMap<k,v> impl

  • java无锁hashmap原理与实现详解

    java多线程环境中应用HashMap,主要有以下几种选择:使用线程安全的java.util.Hashtable作为替代​使用java.util.Collections.synchronizedMap方法,将已有的HashMap对象包装为线程安全的.使用java.util.concurrent.ConcurrentHashMap类作为替代,它具有非常好的性能.而以上几种方法在实现的具体细节上,都或多或少地用到了互斥锁.互斥锁会造成线程阻塞,降低运行效率,并有可能产生死锁.优先级翻转等一系列问题.

  • java HashMap 的工作原理详解

    HashMap的工作原理是近年来常见的Java面试题.几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考察的深度很深.这题经常出现在高级或中高级面试中.投资银行更喜欢问这个问题,甚至会要求你实现HashMap来考察你的编程能力.ConcurrentHashMap和其它同步集合的引入让这道题变得更加复杂.让我们开始探索的旅程吧! 先来些简单的问题 "你用过HashMap吗?&quo

  • 详解Java HashMap实现原理

    HashMap是基于哈希表的Map接口实现,提供了所有可选的映射操作,并允许使用null值和null建,不同步且不保证映射顺序.下面记录一下研究HashMap实现原理. HashMap内部存储 在HashMap内部,通过维护一个 瞬时变量数组table (又称:桶) 来存储所有的键值对关系,桶 是个Entry对象数组,桶 的大小可以按需调整大小,长度必须是2的次幂.如下代码: /** * 一个空的entry数组,桶 的默认值 */ static final Entry<?,?>[] EMPTY

  • java 中HashMap实现原理深入理解

    1. HashMap的数据结构 数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端.       数组 数组存储区间是连续的,占用内存严重,故空间复杂的很大.但数组的二分查找时间复杂度小,为O(1):数组的特点是:寻址容易,插入和删除困难: 链表 链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N).链表的特点是:寻址困难,插入和删除容易. 哈希表 那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提

  • java HashMap内部实现原理详解

    详解HashMap内部实现原理 内部数据结构 static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; 从上面的数据结构定义可以看出,HashMap存元素的是一组键值对的链表,以什么形式存储呢 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABL

  • 深入解析java HashMap实现原理

    Mark一下,同时可以很好的结合hashCode()和equals()方法,覆盖equals方法时最好覆盖hashcode(),保证equals的两个对象,hashcode也相等,反过来:hashcode()不等,一定能推出equals()也不等:hashcode()相等,equals()可能相等,也可能不等. 因为HashMap在get时,先比较hashcode,再比较equals,hashcode==&&equals,两者都为true,则认为是相同的key 1.    HashMap概

  • Java HashMap的工作原理

    大部分Java开发者都在使用Map,特别是HashMap.HashMap是一种简单但强大的方式去存储和获取数据.但有多少开发者知道HashMap内部如何工作呢?几天前,我阅读了java.util.HashMap的大量源代码(包括Java 7 和Java 8),来深入理解这个基础的数据结构.在这篇文章中,我会解释java.util.HashMap的实现,描述Java 8实现中添加的新特性,并讨论性能.内存以及使用HashMap时的一些已知问题. 内部存储 Java HashMap类实现了Map<K

  • java中HashMap的原理分析

    我们先来看这样的一道面试题: 在 HashMap 中存放的一系列键值对,其中键为某个我们自定义的类型.放入 HashMap 后,我们在外部把某一个 key 的属性进行更改,然后我们再用这个 key 从 HashMap 里取出元素,这时候 HashMap 会返回什么? 文中已给出示例代码与答案,但关于HashMap的原理没有做出解释. 1. 特性 我们可以用任何类作为HashMap的key,但是对于这些类应该有什么限制条件呢?且看下面的代码: public class Person { priva

  • java中TESTful架构原理分析

    目录 1. 什么是REST 2. 理解RESTful 2. 1 资源与URI 2. 2 统一资源接口 GET POST PUT DELETE 2. 3 资源的表述 在URI里边带上版本号 使用URI后缀来区分表述格式 如何处理不支持的表述格式 2. 4 资源的链接 2. 5 状态的转移 2. 5.1 应用状态与资源状态 2. 5.2 应用状态的转移 3. 总结 1. 什么是REST REST全称是Representational State Transfer,中文意思是表述(编者注:通常译为表征

  • Java中注解与原理分析详解

    目录 一.注解基础 二.注解原理 三.常用注解 1.JDK注解 2.Lombok注解 四.自定义注解 1.同步控制 2.类型引擎 一.注解基础 注解即标注与解析,在Java的代码工程中,注解的使用几乎是无处不在,甚至多到被忽视: 无论是在JDK源码或者框架组件,都在使用注解能力完成各种识别和解析动作:在对系统功能封装时,也会依赖注解能力简化各种逻辑的重复实现: 基础接口 在Annotation的源码注释中有说明:所有的注解类型都需要继承该公共接口,本质上看注解是接口,但是代码并没有显式声明继承关

  • Java HashMap实现原理分析(一)

    从本文开始,介绍一下最常用的一个集合对象HashMap,HashMap存储的是键值对,本文采用的基于JDK11的源码实现. 一般大家都知道HashMap是通过put操作把一组键值对(key和value)存储到HashMap中,然后可以通过get(key)去获取key对应的value.而最重要的这两个过程是怎么实现的呢?下面我们就来对put和get这两个过程做一个分析. HashMap基本工作原理 下面先看一段源码: /** * The table, initialized on first us

  • java中HashMap的7种遍历方式与性能分析

    目录 1.遍历方式 1.1 迭代器 EntrySet 1.2 迭代器 KeySet 1.3 ForEach EntrySet 1.4 ForEach KeySet 1.5 Lambda 表达式 1.6 Stream API 单线程 1.7 Stream API 多线程 1.8 代码汇总 2.性能分析 2.1 引入依赖 2.2 编写测试类 2.3 测试结果 2.4 分析 2.5 总结 1.遍历方式 1.1 迭代器 EntrySet /** * 1. 迭代器 EntrySet */ @Test pu

  • Java中死锁的原理实战分析

    本文实例讲述了Java中死锁的原理.分享给大家供大家参考,具体如下: 一 点睛 当两个线程相互等待对方释放同步监视器时就会发生死锁,Java虚拟机没有监测.也没有采用措施来处理死锁情况,所以多线程编程时应该采取措施避免死锁的出现. 一旦出现死锁,整个程序既不会发生任何异常,也不会给出任何提示,只是所有线程处于阻塞状态,无法继续. 二 代码 class A { public synchronized void foo( B b ) { System.out.println("当前线程名: &quo

  • Java LinkedHashMap 底层实现原理分析

    在实现上,LinkedHashMap很多方法直接继承自HashMap,仅为维护双向链表覆写了部分方法.所以,要看懂 LinkedHashMap 的源码,需要先看懂 HashMap 的源码. 默认情况下,LinkedHashMap的迭代顺序是按照插入节点的顺序.也可以通过改变accessOrder参数的值,使得其遍历顺序按照访问顺序输出. 这里我们只讨论LinkedHashMap和HashMap的不同之处,LinkedHashMap的其他操作和特性具体请参考HashMap 我们先来看下两者的区别:

  • java中object类实例分析

    问:什么是Object类? 答:Object类存储在java.lang包中,是所有java类(Object类除外)的终极父类.当然,数组也继承了Object类.然而,接口是不继承Object类的,Object类不作为接口的父类. 下面,我们就通过实例,对object进行分析 public class ObjectStu { /*Object类:java里所有类的父类,顶层的类 *equals:判断两个对象是否"相等"; *hashcode:返回一个对象的哈希码值,是一个整数 *因为之后

  • Java中synchronized实现原理详解

    记得刚刚开始学习Java的时候,一遇到多线程情况就是synchronized,相对于当时的我们来说synchronized是这么的神奇而又强大,那个时候我们赋予它一个名字"同步",也成为了我们解决多线程情况的百试不爽的良药.但是,随着我们学习的进行我们知道synchronized是一个重量级锁,相对于Lock,它会显得那么笨重,以至于我们认为它不是那么的高效而慢慢摒弃它. 诚然,随着Javs SE 1.6对synchronized进行的各种优化后,synchronized并不会显得那么

随机推荐