Java HashMap 简介与工作原理

本文概要

  • HashMap 简介
  • HashMap 工作原理
    • 属性介绍
    • 方法介绍
    • 数据的存储结构
  • 相关参考

链表和数组可以按照人们的意愿排列元素的次序。但若想查看某个指定的元素,却忘记了位置,就需要访问所有元素,直到找到为止。 如果集合包含的元素太多,会消耗很多时间。为了快速查找所需的对象,我们来看HashMap。

HashMap简介

映射表(Map)数据结构。映射表用来存放键值对。如果提供了键,就能查找到值。 Java类库为映射表提供了两个通用的实现:HashMap和TreeMap。这两个类都实现了Map接口。

HashMap采取的存储方式为:链表数组或二叉树数组。 散列映射表对键进行散列,数映射表的整体顺序对元素进行排序,并将其组织成搜索树。 散列或比较函数只能左右与键。与键关联的值不能进行散列或比较。

每当往映射表中添加或检索对象时,必须同时提供一个键。即通过Key查找Value。 键必须是唯一的。不能对同一个键存放两个值。如果对同一个键两次调用put方法,后一个值将会取代第一个值。

HashMap 继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。 HashMap 的实现不是同步的,这意味着它不是线程安全的。它的key、value都可以为null。此外,HashMap中的映射不是有序的。

下面是构造函数

123456

public HashMap()public HashMap(int initialCapacity)public HashMap(int initialCapacity, float loadFactor)// 包含 "子Map" 的构造函数 public HashMap(Map<? extends K, ? extends V> map)

用给定的容量和装填因子构造一个空散列映射表。 装填因子是一个0.0~1.0之间的数值。这数值决定散列表填充的百分比。默认装填因子是0.75。 一旦到了这个百分比,就要将其再散列(rehashed)到更大的表中,并将现有元素插入新表,并舍弃原来的表。

HashMap 工作原理

  • JDK 1.8

HashMap 继承 AbstractMap,实现了Map、Cloneable、java.io.Serializable接口

12

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

内部节点类

内部数据结构类,基础hash节点

12345

/** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */static class Node<K,V> implements Map.Entry<K,V>

内部数据结构类,二叉树节点

123456

/** * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn * extends Node) so can be used as extension of either regular or * linked node. */static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>

常量定义

默认容量必须是2的次方,这里是16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

最大容量必须小于等于 1<<30 。若设置的容量大于最大容量,将其限制在最大容量。 static final int MAXIMUM_CAPACITY = 1 << 30;

超过此阈值,将某个元素的链表结构转换成树结构 static final int TREEIFY_THRESHOLD = 8;

小于等于此阈值,将二叉树结构转换成链表结构 static final int UNTREEIFY_THRESHOLD = 6;

状态变量

已存储的键值对数量,map中有多少个元素 transient int size;

当存储的数量达到此值后,需要重新分配大小(capacity * load factor) int threshold;

此HashMap的结构被修改的次数 transient int modCount;

存储数据的数组。必要时会重新分配空间。长度永远是2的次方。不需要序列化。 它的长度会参与存入元素索引的计算。假设长度n为默认的16,那么通过(n - 1) & hash计算得到的索引范围是[0, 15] 装载节点的数组table。首次使用时会初始化,必要时重新分配大小。长度是2的次方。 transient Node<K,V>[] table;

table的存储结构,利用链表

list1

或者二叉树结构

tree1

链表结构和二叉树结构会根据实际使用情况互相转换。具体参见UNTREEIFY_THRESHOLDTREEIFY_THRESHOLD

构造函数

带容量和装载因子的构造函数。检查输入的容量值,将其限制在0到最大容量之间。检查装载因子。

123456789101112

public HashMap(int initialCapacity, float loadFactor) { 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); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity);}

方法

获取key对象的hash值。高位与低位进行亦或(XOR)计算。

1234

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

创建一个常规节点

1234

// Create a regular (non-tree) nodeNode<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next);}

初始化或让table的尺寸放大一倍 final Node<K,V>[] resize()

LinkedHashMap用的回调

1234

// Callbacks to allow LinkedHashMap post-actionsvoid afterNodeAccess(Node<K,V> p) { }void afterNodeInsertion(boolean evict) { }void afterNodeRemoval(Node<K,V> p) { }

put(K key, V value)方法流程

调用put方法时,发生了什么?

添加键值对的方法。重点看putVal方法。将尝试插入的键值对暂时称为目标元素

  • 检查table实例是否存在,获取table的长度
  • 检查输入的hash值,计算得到索引值
    • 若table中对应索引值中没有元素,插入新建的元素
    • 检查当前是否需要扩充容量
  • 尝试更新现有的元素
  • 若使用了二叉树结构,调用二叉树节点类的插入方法putTreeVal
  • 遍历内部元素,插入新值或更新原有值
  • 检查是否要扩大存储空间 1 2 3 4 5 6 7 8 9public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * @param onlyIfAbsent 若为true,则不改变已有的值 * @param evict 若为false,table处于创建状态 */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

实例 HashMap<String, String>初始化并调用put方法

12345678910111213

HashMap<String, String> strMap = new HashMap<>(); strMap.put("one", "value"); strMap.put("two", "value"); strMap.put("three", "value"); System.out.println("hash(\"one\") = " + hash("one")); System.out.println("hash(\"two\") = " + hash("two")); System.out.println("hash(\"three\") = " + hash("three"));/*hash("one") = 110183hash("two") = 115277hash("three") = 110338829*/

已知"one"的hash值是110183,通过(n - 1) & hash计算存储索引。 默认容量n=16,计算得到索引是7。以此类推。

get 方法流程

计算输入key对象的hash值,根据hash值查找。 若map中不存在相应的key,则返回null。

1234

public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value;}

从源码中学到的实用方法

求hash值的方法

1234

public static int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

大于且最接近输入值的2的次方数

12345678910111213

/** * Returns a power of two size for the given target capacity. * MAXIMUM_CAPACITY 是上限 */public static int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}

原文发布于微信公众号 - java工会(javagonghui)

原文发表时间:2018-05-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

2 条评论
登录 后参与评论

相关文章

来自专栏前端架构与工程

JavaScript递归中的作用域问题

需求是这样的,从子节点寻找指定className的父节点,一开始就想到递归(笨!),Dom结构如下: <div class="layer_1"> <di...

1698
来自专栏博岩Java大讲堂

Java集合--HashMap解惑

3294
来自专栏Java Edge

Java8集合源码解析-Hashtable源码剖析1 概述2 源码解析rehash方法3 总结

2656
来自专栏大数据钻研

44 个 JavaScript 变态题解析

当初笔者做这套题的时候不仅怀疑智商, 连人生都开始怀疑了…. 不过, 对于基础知识的理解是深入编程的前提. 让我们一起来看看这些变态题到底变态不变态吧! 第1题...

3226
来自专栏F_Alex

数据结构与算法(六)-背包、栈和队列

  前言:许多基础数据类型都和对象的集合有关。具体来说,数据类型的值就是一组对象的集合,所有操作都是关于添加、删除或是访问集合中的对象。而且有很多高级数据结构都...

774
来自专栏有趣的Python

2-玩转数据结构-不要小瞧数组

数组中索引从0开始,Java语法中要求数组存放同一类型的元素,可以通过中括号下标的方式取到元素。

4314
来自专栏移动开发的那些事儿

数据结构?从HashMap的源码分析开始!

首先,先看下inflateTable方法,这个是初始化HashMap里面的线性表的空间:

581
来自专栏Java爬坑系列

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

  前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。

714
来自专栏后端之路

原来你是这样的LinkedHashMap之简单缓存实现

本篇介绍一下LinkedHashMap 背景 开发者需要基于插入顺序的容器(很常见的需求),而hashMap是不支持这种操作的【hashMap的iterator...

1828
来自专栏cmazxiaoma的架构师之路

通过分析LinkedHashMap了解LRU

我们都知道LRU是最近最少使用,根据数据的历史访问记录来进行淘汰数据的。其核心思想是如果数据最近被访问过,那么将来访问的几率也更高。在这里提一下,Redis缓存...

593

扫码关注云+社区