HashMap提高篇(2)--HashMap的存取方法的源码实现

2019-11-06 09:50:47

字体：大中小

来源：转载

供稿：网友

HashMap概述 HashMap是基于哈希表的Map接口的非同步实现，以key-value的形式存在。key-value总是会当做一个整体来处理，系统会根据Hash算法来计算key-value的存储位置，我们总是可以通过key快速地存、取value。

下面讲解一下HashMap的存取方法。

1.采取的jdk版本：

这里写图片描述

2.类的定义

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

HashMap实现了Map接口，继承AbstractMap。其中Map接口定义了键映射到值的规则，而AbstractMap类提供 Map 接口的骨干实现，以最大限度地减少实现此接口所需的工作，其实AbstractMap类已经实现了Map，这里标注Map LZ觉得应该是更加清晰吧。

3.HashMap的默认主要几个常量和变量

//HashMap最大容量static final int MAXIMUM_CAPACITY = 1 << 30; //已经储存了多少个键值对 transient int size; //默认初始化容量 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认负载因子大小 static final float DEFAULT_LOAD_FACTOR = 0.75f;//定义了一个数组链表transient Node<K,V>[] table;//apacity * loadFactor 这两个数的乘积int threshold;

4.HashMap的构造函数

//构造一个带指定初始容量和加载因子的空 HashMap。public HashMap(int initialCapacity, float loadFactor)//构造一个带指定初始容量的空 HashMap。public HashMap(int initialCapacity)//构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMappublic HashMap()//构造一个和原来一样的HashMappublic HashMap(Map<? extends K, ? extends V> m)

HashMap在使用 public HashMap(int initialCapacity, float loadFactor) 构造方法初始化时，容量会通过 static final int tableSizeFor(int cap) 变为一个 2^n 的比指定的容量大的一个数。

简单的介绍一下这个方法，源码如下：

static final 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; }拿 2^29 +1 这个数举例，经过 int n = cap - 1，先将它转换为二进制数位 1 后面28 个零；进过 n |= n >>> 1，变成两个 1 后面 26 个零进过 n |= n >>> 2，变成四个 1 后面 24 个零……进过 n |= n >>> 16，全变成 1；

自己去体会吧^_^

HashMap的数据结构： HashMap源码：

//定义源码 359 行transient Node<K,V>[] table;//初始化源码 703 行Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

这里写图片描述

由此可以看出HashMap是Hash表的拉链法实现，他是由Node构成的“链表的数组”。

Node的数据结构： Node源码：

static class Node<K,V> implements Map.Entry<K,V> { //Hash值 final int hash; //key的值 final K key; //value的值 V value; //指向下一个Node节点 Node<K,V> next;}

数据结构图：

这里写图片描述

Node的构造函数

//通过hash值 key value Node 节点创建一个NodeNode(int hash, K key, V value, Node<K,V> next);

Hash表的最主要的一点就是Hash函数，来看看HashMap是如何构造Hash函数的。

Hash函数

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

其实看起来也挺简单的…… 哈哈。

put方法

源码：

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

计算 key 的Hash值，调用 putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) 方法。

putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) 方法。

参数解析：

onlyIfAbsent 当为 false 的时候，如果 Hash值和key值都相同的话就不会去覆盖原有的Value

源码:

//链表数组是否被初始化 627-628行if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;//若 i = (n - 1) & hash 下标没有被赋值，创建一个节点，令Hash表的 i 下标为当前的节点。629-630if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);//若 Hash 表的 i 下标不为空，并且Hash表的 i 节点的Hash值和key值与新节点的相同，将第 i 个节点的值赋值给局部变量 633-635行if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) e = p;//若 Hash 表的 i 下标不为空，并且Hash表的 i 节点//与新节点的Hash值相同而key值与不相同相同，//就遍历该节点的链表，若找到与新节点相同的Hash值和key，//那么就赋值给局部变量，没有找到就插入到链表的最后 //639-651 行for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e;}//用新传入的value覆盖原来的value，返回原来value的值 652-658行if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) //进行覆盖 e.value = value; afterNode access(e); //返回原来的value return oldValue;} //对修改次数和HashMap储存的键值对的数量进行修改（只有 new 了新的节点这个值才会被修改，覆盖不会产生修改） 660-664行++modCount;//判断是否需要扩容（默认是不超过容量的3/4）if (++size > threshold) //进行扩容 resize();//空函数的 666afterNodeInsertion(evict);返回return null;

put方法总结：

首先计算key的Hash值。判断这个Hash在对应的Hash表中是有值，若没有值，直接赋值，若有值，遍历该节点构成的链表，若存在相同的key和Hash值则覆盖该节点的value，若存在相同的key但是没有相同的value的话，那么就通过传入的参数新创建一个节点，添加到给链表的最后面。若是新创建的节点，返回null,若是覆盖节点，返回原来覆盖的节点。

get方法：

源码（554-557行）：

public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value;}首先通过Hash函数计算Hash值； 2.该方法掉用了 getNode(int hash, Object key) 方法；

差看一下该方法： 源码（566-584行）：

final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k;bi //判断Hash表是否为空，长度是否大于 0 ， //并获取下标 (n - 1) & hash 的节点 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //若第一个节点的Hash值和key只相同的话就返回该节点 if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; //若第一个节点的Hash值和key不相同，就遍历该节点组成的链表 if ((e = first.next) != null) { //忽略 ^_^ if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { //寻找具有相同Hash值和key值得节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null;}

get方法总结

通过 Hash 值计算所在的下标；若第一个节点的 Hash 值和 key 值都相同的话，直接返回，若不相同，查找下一个节点；没有找到返回空；

贴张帅照

这里写图片描述