商城微信网站开发,网站做seo必要的结构,北京市网站备案查询,设计家官网视频HashMap解析 HashMap源码解析_jdk1.8#xff08;一#xff09;哈希常用数据结构查找/插入/删除性能比较。哈希冲突 HashMap的数据结构HashMap相关变量size和capacity HashMap源码解析_jdk1.8#xff08;一#xff09;
哈希
Hash#xff0c;一般翻译做“散列”#xff0… HashMap解析 HashMap源码解析_jdk1.8一哈希常用数据结构查找/插入/删除性能比较。哈希冲突 HashMap的数据结构HashMap相关变量size和capacity HashMap源码解析_jdk1.8一
哈希
Hash一般翻译做“散列”也有直接音译为“哈希”的就是把任意长度的输入通过散列算法变换成固定长度的输出该输出就是散列值。这种转换是一种压缩映射也就是散列值的空间通常远小于输入的空间不同的输入可能会散列成相同的输出所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
常用数据结构查找/插入/删除性能比较。 数组 采用一段连续的存储单元来存储数据。 查找时间复杂度O(1) 插入删除时间复杂度O(n)插入删除操作涉及到数组元素的移动。 线性链表 查找时间复杂度O(n)需要遍历链表。 插入删除时间复杂度O(1)仅需处理链表指针的指向。 二叉树 对一棵相对平衡的有序二叉树对其进行插入查找删除等操作平均复杂度均为O(logn)。 哈希表 在哈希表中进行添加删除查找等操作性能十分之高不考虑哈希冲突的情况下仅需一次定位即可完成时间复杂度为O(1)。 哈希表的主干就是数组。 比如我们要新增或查找某个元素我们通过把当前元素的关键字通过某个函数映射到数组中的某个位置通过数组下标一次定位就可完成操作。 映射函数存储位置 f(关键字) 其中这个函数f一般称为哈希函数这个函数的设计好坏会直接影响到哈希表的优劣。查找操作同理先通过哈希函数计算出实际存储地址然后从数组中对应地址取出即可。
哈希冲突
哈希是通过对数据进行再压缩提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的而数据可能比较多导致经过哈希函数处理后仍然有不同的数据对应相同的值。这时候就产生了哈希冲突哈希碰撞。
解决哈希冲突的方法 开放地址方法 1). 线性探测冲突发生时顺序查看表中下一单元直到找出一个空单元或查遍全表。 2). 再平方探测: 冲突发生时在表的左右进行跳跃式探测在原来值的基础上先加1的平方个单位若仍然存在则减1的平方个单位。随之是2的平方3的平方等等。直至不发生哈希冲突。 3). 伪随机探测: 冲突发生时通过随机函数随机生成一个数直至不发生哈希冲突。 链式地址法HashMap的哈希冲突解决方法 将所有哈希地址为i的元素构成一个单链表并将单链表的头指针存在哈希表的第i个单元中因而查找、插入和删除主要在链表中进行。 再哈希法 对于冲突的哈希值再次进行哈希处理直至没有哈希冲突。 建立公共溢出区 将哈希表分为基本表和溢出表两部分凡是和基本表发生冲突的元素一律填入溢出表。
HashMap的数据结构
HashMap的底层主要是基于数组链表红黑树JDK1.8增加了红黑树部分实现的。 从上图看到左边是个数组数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针用于元素间的链接。
JDK1.7中HashMap的数据结构数组链表 JDK1.8中HashMap的数据结构数组链表红黑树只有在链表的长度不小于8而且数组的长度不小于64的时候才会将链表转化为红黑树。 HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元每一个Entry包含一个key-value键值对。Entry是HashMap中的一个静态内部类。代码如下
static class NodeK,V implements Map.EntryK,V {final int hash;final K key;V value;NodeK,V next;Node(int hash, K key, V value, NodeK,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; }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)return true;if (o instanceof Map.Entry) {Map.Entry?,? e (Map.Entry?,?)o;if (Objects.equals(key, e.getKey()) Objects.equals(value, e.getValue()))return true;}return false;}
}HashMap相关变量
HashMap类中有以下主要成员变量 /*** 默认初始容量 - 必须是2的幕数.*/
static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16/*** node数组最大容量2^301073741824.* MUST be a power of two 130.*/
static final int MAXIMUM_CAPACITY 1 30;/*** 默认的负载因子用来衡量HashMap满的程度。*/
static final float DEFAULT_LOAD_FACTOR 0.75f;/*** 将链表转换为树的阈值。当链表长度超过8时链表就转换为红黑树。*/
static final int TREEIFY_THRESHOLD 8;/*** 树转链表阀值小于等于6tranfer时lc、hc0两个计数器分别记录原bin、新binTreeNode数量UNTREEIFY_THRESHOLD 则untreeify(lo)*/
static final int UNTREEIFY_THRESHOLD 6;/*** The smallest table capacity for which bins may be treeified.* (Otherwise the table is resized if too many nodes in a bin.)* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts* between resizing and treeification thresholds.*/
static final int MIN_TREEIFY_CAPACITY 64;/* ---------------- Fields -------------- *//*** 存放node的数组分配长度后长度始终为2的幂*/
transient NodeK,V[] table;/*** Holds cached entrySet(). Note that AbstractMap fields are used* for keySet() and values().*/
transient SetMap.EntryK,V entrySet;/*** 记录了Map中Key-Value对的个数*/
transient int size;/**
* 记录当前集合被修改(添加删除)的次数
*
* 当我们使用迭代器或foreach遍历时如果你在foreach遍历时自动调用迭代器的迭代方法* 此时在遍历过程中调用了集合的add,remove方法时modCount就会改变* 而迭代器记录的modCount是开始迭代之前的如果两个不一致就会报异常* 说明有两个线路线程同时操作集合。这种操作有风险为了保证结果的正确性* 避免这样的情况发生一旦发现modCount与expectedModCount不一致立即保错。
*
* This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;/*** 下一个要调整大小的大小值当实际KV个数超过threshold时HashMap会将容量扩容thresholdcapacity * load factor.*/
int threshold;/*** The load factor for the hash table.*/
final float loadFactor;size和capacity
HashMap就像一个“桶”那么capacity就是这个桶“当前”最多可以装多少元素而size表示这个桶已经装了多少元素。 HashMapInteger, Integer map new HashMap();map.put(1, 1);try {Class? mapClass map.getClass();Method capacity mapClass.getDeclaredMethod(capacity);capacity.setAccessible(true);System.out.println(capacity: capacity.invoke(map));Field size mapClass.getDeclaredField(size);size.setAccessible(true);System.out.println(size: size.get(map));} catch (NoSuchMethodException | IllegalAccessException | InvocationTargetException | NoSuchFieldException e) {e.printStackTrace();}
}capacity: 16
size: 1我们定义了一个新的HashMap向其中put了一个元素然后通过反射的方式打印capacity和size。输出结果为capacity : 16、size : 1
默认情况下HashMap的容量是16但是如果用户通过构造函数指定了一个数字作为容量那么Hash会选择大于该数字的第一个2的幂作为容量。(1-1、7-8、9-16)
/*** Returns a power of two size for the given target capacity.*/
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;
}public static void main(String[] args) {HashMapInteger, Integer map1 new HashMap(1);HashMapInteger, Integer map2 new HashMap(7);HashMapInteger, Integer map3 new HashMap(9);demoCapacity(map1);demoCapacity(map2);demoCapacity(map3);
}private static void demoCapacity(HashMapInteger, Integer map) {try {Class? mapClass map.getClass();Method capacity mapClass.getDeclaredMethod(capacity);capacity.setAccessible(true);System.out.println(capacity: capacity.invoke(map));} catch (NoSuchMethodException | IllegalAccessException | InvocationTargetException e) {e.printStackTrace();}
}
capacity: 1
capacity: 8
capacity: 16参考 https://zhuanlan.zhihu.com/p/79219960 https://www.cnblogs.com/theRhyme/p/9404082.html#_lab2_1_1
