JDK源码util包分析——HashMap源码(6)
2022/3/3 12:15:06
本文主要是介绍JDK源码util包分析——HashMap源码(6),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
HashMap源码分析
HashMap的结构图
HashMap原理介绍
数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为O(logn);对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n)
线性链表:对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂度为O(n)
二叉树:对一棵相对平衡的有序二叉树,对其进行插入,查找,删除等操作,平均复杂度均为O(logn)。
哈希表:相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下,仅需一次定位即可完成,时间复杂度为O(1),接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的,哈希表就是数组和链表组成的。
HashMap 是数组 + 链表 + 红黑树(JDK1.8 中新增的红黑树部分)实现的
HashMap的数据结构
链表
Node是HashMap的一个内部类,实现了Map.Entry接口,本质上是一个映射(键值对)
static class Node<K,V> implements Map.Entry<K,V> { final int hash;//存储hash值,用来定位数组索引位置 final K key;//存储key值 V value;//存储key值对应的value值 Node<K,V> next;//指向下一节点的指针 Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } //hash值为key的hash值的value的hash值的按位异或 public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this)//如果o为当前对象 return true; if (o instanceof Map.Entry) {//o为Map.Entry的类型或其子类 Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))//判断key和value是否完全相等 return true; } return false; } }
红黑树
下面只给处红黑树一部分代码。红黑树比链表多了四个变量,parent父节点、left左节点、right右节点、prev上一个同级节点。
//红黑树 static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> { TreeNode<k,v> parent; // 父节点 TreeNode<k,v> left; //左子树 TreeNode<k,v> right;//右子树 TreeNode<k,v> prev; // needed to unlink next upon deletion//删除后需要取消下一步链接 boolean red; //颜色属性 TreeNode(int hash, K key, V val, Node<k,v> next) { super(hash, key, val, next); } //返回当前节点的根节点 final TreeNode<k,v> root() { for (TreeNode<k,v> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } }
位桶
HashMap类中有一个非常重要的字段,就是 Node[] table,即哈希桶数组,明显它是一个Node的数组
transient Node<k,v>[] table;//存储(位桶)的数组
HashMap的底层实现
首先有一个每个元素都是链表的数组,当添加一个元素(key-value)时,就首先计算元素key的hash值,以此确定插入数组中的位置,但是可能存在同一hash值的元素已经被放在数组同一位置了,这时就添加到同一hash值的元素的后面,他们在数组的同一位置,但是形成了链表,所以说数组存放的是链表。而当链表长度太长时,链表就转换为红黑树,这样大大提高了查找的效率。
HashMap的静态实用程序
//得到key的hash值 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } //如果x的类的形式为“Class C implements Compariable<C>”,则返回x的类,否则返回null static Class<?> comparableClassFor(Object x) { if (x instanceof Comparable) { // 判断是否实现了Comparable接口 Class<?> c; Type[] ts, as; Type t; ParameterizedType p; if ((c = x.getClass()) == String.class) return c; // 如果是String类型,直接返回String.class if ((ts = c.getGenericInterfaces()) != null) { // 判断是否有直接实现的接口 for (int i = 0; i < ts.length; ++i) { // 遍历直接实现的接口 if (((t = ts[i]) instanceof ParameterizedType) && // 该接口实现了泛型 ((p = (ParameterizedType)t).getRawType() == // 获取接口不带参数部分的类型对象 Comparable.class) && // 该类型是Comparable (as = p.getActualTypeArguments()) != null && // 获取泛型参数数组 as.length == 1 && as[0] == c) // 只有一个泛型参数,且该实现类型是该类型本身 return c; // 返回该类型 } } } return null; }
HashMap的参数
// 序列号 private static final long serialVersionUID = 362498820763181265L; // 默认的初始容量是16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; // 默认的填充因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 当链表中的元素个数超过8,并且Node[] table数组长度没有超过MIN_TREEIFY_CAPACITY的值64时,进行数组扩容,否则链表结构转化成红黑树结构,进行结构优化 static final int TREEIFY_THRESHOLD = 8; // 当桶(bucket)上的结点数小于这个值时树转链表 static final int UNTREEIFY_THRESHOLD = 6; // 桶中结构转化为红黑树对应的table的最小大小 static final int MIN_TREEIFY_CAPACITY = 64; // 存储元素的数组,总是2的幂次倍 transient Node<k,v>[] table; // 存放具体元素的集 transient Set<map.entry<k,v>> entrySet; // size 是 HashMap 中实际存在的键值对的数量 transient int size; // 每次扩容和更改map结构的计数器 transient int modCount; // threshold 是 HashMap 所能容纳的最大的键值对的个数。临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容,扩容为原来两倍 int threshold; // 填充因子 final float loadFactor;
HashMap的构造函数
这篇关于JDK源码util包分析——HashMap源码(6)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门:从零开始的编程之旅
- 2024-11-23Java创业入门:新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门:初学者的简单教程
- 2024-11-23JAVA副业入门:初学者的实战指南