Java中的数据结构-HashMap
2021-02-19 06:20
标签：only 类型 bst existing 执行 就是 method shell 结构 HashMap通过继承 在接口实现关系上来看为多余操作 但有一点要注意，在使用反射获取实现接口时，如果不是显示实现某接口而是通过继承来实现该接口，则不会获取该接口类型，这一点在使用动态代理时要注意 HashMap实现了 HashMap实现了 （1）哈希表 哈希表也成为散列表，它是根据关键字经过 HashMap 使用数组作为哈希表，来存储Key的hash()信息 （2）链表 因为 （3）红黑树 红黑树为一颗平衡二叉树 当元素越来越多时，hash碰撞也会越来越严重，链表的长度会变得很大，此时如果我们想要查找该链表的的某一个元素，其时间复杂度为\(O(n)\)，必须采用一个阈值，当链表的长度达到该阈值时，便应该将链表转化为一颗红黑树，从而将时间复杂度从\(O(n)\)降低为\(O(logn)\),从而改善Hash表的查找性能 （1）缺省table长度 （2）table长度的最大值 （3）缺省负载因子 （4）树化阈值-链表长度 （5）树化阈值-HashMap元素个数 （6）树降为链表的阈值 （1）HashMap元素个数 （2）Hash表结构修改次数 （3）扩容阈值 （4）负载因子 （1）静态结点类源码 结点Node类为实现了 重写的 重写的 （1）Hash表源码 Hash表定义源码: 为了能够通过确定计算的hashcod找到桶的位置，HashMap中底层采用Node transient修饰在序列化时会被跳过 （2）确定桶的位置 （3）长度的确定 hash表长度计算方法源码: 该方法的作用是，当初始化时，通过传入capacity返回一个大于等于当前值cap的一个数字，并且这个数字一定是2的次方数 该方法不断通过右移然后进行‘或’操作，可以将传入的cap中的首非0位之后的0位填满，变为 例： Hash表的长度必须为2的整数次幂 （4）hash值的计算： hash扰动函数源码:(实际上产生的就是 如果key为null则hash值为0，位置计算结果也为0（从putVal方法的第一种情况可以看出），会替换掉 当table长度比较小时，从前面位置算法 h>>16的结果的高16位全为0， 例： hash扰动原理参考 （1） （2）其它构造方法 其它构造方法源码 （1） 源码: 套娃方法，该方法首先计算调用 （2） 源码： 套娃方法，计算hash值，调用 （3）putAll 源码： 套娃方法，调用 （3） putVal源码 整个方法的流程： 传入的参数 方法执行逻辑： （1）扩容原因 （2）核心 resize方法源码： 确定新的表容量以及新的扩容阈值逻辑： 开始将旧表元素分配到新的表上 使用 如果：oldTab!=null，说明扩容之前数组就已经被创建了，此时开始遍历 如果： 令 如果：e.next == null（即当前桶位只有一个元素），则让 如果：e为树的根结点，调用 如果：e为链表的头结点，创建4个链表结点 开始循环：创建结点 最后将两条链表的尾结点置null 将 元素的分配，扩容完成！！！ （1） 源码 套娃方法，调用removeNode方法，获取其返回的被删除结点，返回该结点的value （2） 源码 套娃方法，调用removeNode方法，返回是否删除成功 （3）核心 源码 方法逻辑： （1） 源码： 调用 （2） 源码： 调用 （1） 该方法实现了通过传入函数式接口，来对传入的key值对应的结点进行操作，如果找不到key对应的结点，会进行插入一个新的结点 源码： 方法逻辑 使用方法 （2） 该方法如果没有检测到该key所对应结点，会添加一个新的结点 使用方法 （3） 该方法如果检测到该key所对应结点，会添加一个新的结点 使用方法 （1）merge方法 该方法与compute类似，只不过以 如果oldValue为null或者节点不存在，则直接取value参数(不是映射后的value)作为节点的value值 同样的，作为特殊情况，如果计算出来的value值为null，删除节点 使用方法 （1） 源码 （1）clear方法 源码 判断table是否初始化，如果不为空，每个位置置为null,等待JVM回收各个结点即可 （1） 源码： 套娃方法,先用hash函数获取key的hash值，getNode去寻找Node结点，如果找到则返回value值，没找到则返回null （2） 源码： 套娃方法，和get方法类似，只不过如果找不到结点则返回传入的默认值 （2）核心 源码： 方法逻辑Java数据结构-HashMap
1. HashMap
1.1 HashMap介绍
1.1.1 HashMap介绍
1.1.2 HashMap继承图
AbstractMap实现了Map接口,且本身也实现了Map接口
HashMap.class.getInterfaces()//[interface java.util.Map, interface java.lang.Cloneable, interface java.io.Serializable]
Serializable接口，可以通过java.io.ObjectStream进行序列化Cloneable接口，实现了浅拷贝，通过以下代码可以证实：
HashMap map = new HashMap();
map.put(1, "first");
HashMap copiedMap = (HashMap) map.clone();
System.out.println(copiedMap.get(1)==map.get(1));//true
copiedMap.put(2, "second");
System.out.println(map);//{1=first}
1.2 HashMap 组成结构
1.2.1 Hashmap底层数据结构
hash()函数处理，将值映射到哈希表上的某一个位置，以该位置作为关键字的存储位置，无论存在哪，只需要进行一次hash计算，便可以找到该位置，整个查找过程时间复杂度为\(O(1)\)
hash()函数是将key值映射到有限的空间中，如果hash()函数碰撞性设计的不完善，或者哈希表存储的元素过多，必然会导致不同元素的hash值相同,即位置冲突，此时我们采用的方式一般有：
hash()函数映射关系使元素分布地更加均匀，降低碰撞几率
2.HashMap源码解析
2.1 HashMap属性源码解析
2.1.1 HashMap中的静态常量
static final int DEFAULT_INITIAL_CAPACITY = 1
static final int MAXIMUM_CAPACITY = 1
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
static final int UNTREEIFY_THRESHOLD = 6;
2.1.2 HashMap中的属性
transient int size;
transient int modCount;
int threshold;
threshold = loadFactor * capacity
final float loadFactor;
2.1.3 HashMap中的存储结点
static class NodeMap.Entry接口的一个静态内部类，主要包含：
hash计算值：后面构造时用以保存hashcode,避免每次重新计算key：键value：值next:指向下一个结点的引用：如果发生哈希碰撞，使用链式结构存储hash值相同的键值对hash()方法将key和value经Objects.hashCode(Object o)处理后进行与操作，使得hash()函数映射更加随机均匀equals方法中只有传入结点为自身结点或者key与value调用equals方法比较都为真时，结果才为真（主要用于后面查找元素时的比较）2.1.4 Hash表
transient Node
put一个结点时，通过以下算法来确定结点应该位于哪个桶
index = (table.length - 1) & node.hash，也就是说位置完全取决于node.hash的后几位(table.length-1的二进制位数)
static final int tableSizeFor(int cap) {
int n = cap;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
0..11...1的形式，即\(2^{n的二进制位数+1}-1\)
cap = 10
n = 10 - 1 => 9
0b1001 | 0b0100 => 0b1101
0b1101 | 0b0011 => 0b1111
0b1111 | 0b0000 => 0b1111 = 15
return 15 + 1 = 16
cap = 16
n = 16;
0b10000 | 0b01000 =>0b11000
0b11000 | 0b00110 =>0b11110
0b11110 | 0b00001 =>0b11111
return 31 + 1 = 32;
hash(K key)
Node.hash，用于后面Node对象的构造)static final int hash(Object key) {
int h;//h=0
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
table[0]桶位的key为null的元素
index = (table.length-1)|node.hash()可以看出，如果不经处理，计算的index只取决于结点的hash的后几位(table.length-1的二进制长度)，这样会使不同元素的位置结果相同概率大大增加(h = key.hashCode()) ^ (h >>> 16)就可以让结果hash的高16位为key.hashCode()的高16位，使得高16位也参与hash值的计算，增加低16位的随机性
h = key.hashCode() = 0b 0010 0101 1010 1100 0011 1111 0010 1110
0b 0010 0101 1010 1100 _ 0011 1111 0010 1110
^
0b 0000 0000 0000 0000 _ 0010 0101 1010 1100 (h>>>16)
=> 0010 0101 1010 1100 _ 0001 1010 1000 0010
2.2 HashMap数据的改变
2.2.1 构造方法分析
HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity, float loadFactor) {
//前面都是校验传入参数是否合法，不合法抛出 IllegalArgumentException
//initialCapacity必须是大于0 ，最大值为 MAX_CAPACITY
if (initialCapacity MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//loadFactor必须大于0且不是NaN
if (loadFactor
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75
//现在的扩容阈值thershold = 0
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
//现在的扩容阈值thershold = 0
//调用putMapEntries，添加键值对s
putMapEntries(m, false);
}
putMapEntries方法源码：final void putMapEntries(Map extends K, ? extends V> m, boolean evict) {
//获取键值对map长度
int s = m.size();
if (s > 0) {
//如果table没有初始化，先计算一系列属性再初始化
if (table == null) { // pre-size
//计算初始的table长度
float ft = ((float)s / loadFactor) + 1.0F;
//选取table长度与最大长度的最小值
int t = ((ft threshold)
threshold = tableSizeFor(t);
}
//如果map的长度大于扩容阈值，扩容table
else if (s > threshold)
resize();
//遍历调用put方法添加键值对
for (Map.Entry extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
m.entrySet(),依次插入键值对2.2.2 键值对的添加 put方法分析
put(K key, V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
hash()方法计算hash值(并不是key.hashCode()),调用putVal以替换的方式进行结点插入操作,返回之前结点的valueputIfAbsent
@Override
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
putVal以非替换的方式进行结点插入操作，返回之前结点的value
public void putAll(Map extends K, ? extends V> m) {
putMapEntries(m, true);
}
putMapEntries(m, true)实现添加传入的map的所有的键值对putVal
/**
* Implements Map.put and related methods.
*
* @param hash hash for key -key的hash值
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don‘t change existing value -true:如果该元素已经存在与HashMap中就不操作了
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
//tab：引用当前hashMap的散列表
//p：表示当前散列表的元素
//n：表示散列表数组的长度
//i：表示路由寻址结果
Node
int hash：上层调用者经过hash扰动后的hash值K key,V vey：键，值boolean onlyIfAbsent：如果为true,则对相同的元素不进行替换处理boolean evict：没用，后面并没有做什么工作
p为null
Node e,K k
p.hash值与传入的hash值相同，并且p.key==key或者说key通过equals方法比较为true
e=p)，下一步进行结点的值的替换p为红黑树结点
p开始遍历,binCount=0,之后每次循环+1
(e=p.next)==null,e为当前结点p的下一个结点)，说明并没有找到该元素，new 新的结点插入到链表尾部(p.next = new Node(...))
binCount >= TREEIFY_THRESHOLD - 1))，即当binCount到达7时，即插入操作后链表长度为8时（binCount从0开始计数，而p开始就对应第一个结点），调用树化方法e.hash值与传入的hash值相同，并且e.key==key或者说equals方法比较为true
oldvalue = e.value
!onlyIfAbsent || oldValue == null
return oldvalue;(源码中并没有方法体{没有内容}，在这里没用)++size>thershold,超过扩容阈值，则执行扩容方法return null2.2.3 hash表table扩容 resize方法分析
resize方法
/**
* @return the table
*/
final Node
MAXIMUN_CAPCITY=1，则将扩容阈值设为整数最大值，返回原table（已经无法扩容了）
newCap = oldCap，如果newCap小于
MAXIMUN_CAPCITY并且旧的负载oldCap大于默认表容量16，则新的扩容阈值等于旧的扩容阈值翻倍oldThr>0(构造HashMap时除了无参默认方法其他都直接或间接设置了thorshold),让新的表容量等于旧的扩容阈值newCap=oldThr
oldCap == 0，oldThr == 0(使用无参构造方法)，让newCap = 默认表容量16，newThr = 默认负载因子*默认表容量
newCap创建新的数组newTaboldTab.for(j = 0;j
(Node e = oldTab[j]) != null，即当前节点不为空：oldTab[j] = null 方便GC回收旧的数组newTab[e.hash & (newCap - 1)] = e;（利用新的表容量的位置算法，让e赋值到新表的相应位置）((TreeNode去进行树中结点在新表的分配loHead,loTail,hiHead,hiTail
index = e.hash & (15=1111b),也就是说是因为该链表的hash后4位相同，所以才分配到该链表上
next = e.next
(e.hash & oldCap) == 0
newTab[j] = loHead，newTab[j+oldCap] = hiHead2.2.4 删除键值对 remove方法分析
remove(K)方法
public V remove(Object key) {
Noderemove(K,V)方法
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
removeNode方法
/**
* Implements Map.remove and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node
removeTreeNode(this, tab, movable)方法，删除并保存树的结点2.2.5 替换结点值 replace方法分析
replace(K,V)
@Override
public V replace(K key, V value) {
NodegetNode方法通过比较key来找到需要替换的结点，将value赋给该结点,返回旧value；如果没找到返回nullreplace(K key, V oldValue, V newValue)
@Override
public boolean replace(K key, V oldValue, V newValue) {
NodegetNode方法通过比较key与value来找到需要替换的结点，将newValue赋给该结点,返回true,如果没找到返回false2.2.6 K 映射 compute方法
compute方法
Node(key,mappingFunction.apply(key,value)),并可能会重新排列部分数据结构;如果映射value结果为null,则会删除该结点@Override
public V compute(K key,
BiFunction super K, ? super V, ? extends V> remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
Node
old，如果找到了且value不为空,利用remappingFunction.apply(key, oldValue)进行映射操作，获得新的value v
否则：v为null,调用removeNode(hash, key, null, false, true)方法删除key,value对应结点
t.putTreeVal(this, tab, hash, key, v)实现作为新结点的插入HashMapcomputeIfAbsent方法
public V computeIfAbsent(K key,Function super K, ? extends V> mappingFunction) {...}
Node(key,mappingFunction.apply(key,value))到HashMap中,如果存在则不进行此操作,并返回null;如果映射value结果为null,则会删除该结点承接上处
hp.computeIfAbsent(2,(v)->"new value")//返回BA
hp ==> {1=A, 2=BA, 3=C}
jshell> hp.computeIfAbsent(4,(v)->"new value")//返回new value
hp ==> {1=A, 2=BA, 3=C, 4=new value}
computeIfPresent方法
public V computeIfPresent(K key,BiFunction super K, ? super V, ? extends V> remappingFunction) {...}
Node(key,mappingFunction.apply(key,value))到HashMap中,如果不存在则不进行此操作，并返回null;如果映射value结果为null,则会删除该结点承接上处
hp.computeIfPresent(5,(k,v)->"new value ：5")//返回null
hp.computeIfPresent(4,(k,v)->"new value ：4")//返回"new value ：4"
hp ==> {1=A, 2=BA, 3=C, 4=new value ：4}
2.2.7 K-V 映射 merge方法
key与value来寻找相应结点,找到则覆盖，找不到则插入新的结点Node(key,value)public V merge(K key, V value, BiFunction super V, ? super V, ? extends V> remappingFunction) {...与compute类似...}
HashMap2.2.8 遍历消费 forEach方法
forEach方法
public void forEach(BiConsumer super K, ? super V> action) {
Node2.2.9 清空 clear方法
public void clear() {
Node
2.3 获取HashMap中的信息
2.3.1 获取值 get方法分析
get方法
public V get(Object key) {
NodegetOrDefault方法
public V getOrDefault(Object key, V defaultValue) {
NodegetNode方法
/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node
tab表,头结点first,临时结点e,表长度n
first = tab[(n - 1) & hash]不为空，则：
getTreeNode(hash, key)寻找树种符合条件的结点，并返回结果
文章标题：Java中的数据结构-HashMap
文章链接：http://soscw.com/index.php/essay/57410.html