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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

C++ STL之排序算法

排序算法和查找算法差不多,也涉及到迭代器区间问题,关于该问题的注意事项就不在啰嗦了 一、全部排序sort、stable_sort sort是一种不稳定排序,使用...

1925
来自专栏calmound

Is It A Tree?(并查集)

判断树是否唯一 1.只有一个根节点,(1)在一棵树上一个根节点。1 2 3 2就是两个根节点(1)只有一棵树 2.不成环,入度不大于1 由于数组运行超界导致wa...

3336
来自专栏刘笑江的专栏

通过Swift学函数式编程

在文章SWIFT IS A LOT LIKE SCALA [1] 提到Swift和Scala有很大的相似之处,在某些特性甚至比Scala对函数式编程的支持更友好...

1625
来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第五章 Kotlin面向对象编程(OOP)一个OOP版本的HelloWorld构造函数传参Data Class定义接口&实现之写pojo bean定一个Rectangle对象封

We frequently create a class to do nothing but hold data. In such a class some s...

1684
来自专栏Java爬坑系列

【Java入门提高篇】Day33 Java容器类详解(十五)PriorityQueue详解

 今天要介绍的是基础容器类(为了与并发容器类区分开来而命名的名字)中的另一个成员——PriorityQueue,它的大名叫做优先级队列,想必即使没有用过也该有所...

1081
来自专栏数据结构与算法

codevs 1213 解的个数

1213 解的个数 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 已知整数x...

3354
来自专栏闵开慧

曾经做过的40道程序设计课后习题总结(三)

曾经做过的40道程序设计课后习题总结(三) 课后习题目录 1 斐波那契数列 2 判断素数 3 水仙花数 4 分解质因数 5 杨辉三角 6 学习成绩查询 7 求最...

3878
来自专栏noteless

[十六]基础类型BigInteger简介

final int[] mag;保存数字的数据 字节序为大端模式,大端模式就是低地址存储高位

1684
来自专栏java达人

数字的陷阱

Java中对数字的处理,如四舍五入,如加减乘除,貌似是一个很基础很简单的知识点,但是如果你没有对他进行充分了解,很容易掉进它的陷阱里。 1、浮点数运算 先来看一...

1868
来自专栏海天一树

程序员必须掌握的8大排序算法

分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)...

3138

扫码关注云+社区