四、手撕源码
底层原理剖析(超详细！！！) 一、散列表结构
散列表结构就是数组+链表的结构
二、什么是哈希？
Hash也称散列、哈希，对应的英文单词Hash，基本原理就是把任意长度的输入，通过Hash算法变成固定长度的输出
这个映射的规则就是对应的哈希算法，而原始数据映射后的二进制就是哈希值
不同的数据它对应的哈希码值是不一样的
哈希算法的效率非常高
三、原理讲解 3.1继承体系图
3.2Node数据结构分析
static class Node implements Map.Entry {final int hash;计算得到哈希值final K key;V value;Node next;}interface Entry {K getKey();V getValue();V setValue(V value);
3.3底层存储结构
当链表长度到达8时，升级成红黑树结构
3.4put数据原理分析
首先put进去一个key----value
根据key值会计算出一个hash值
经过扰动使数据更散列
构造出一个node对象
最后在通过路由算法得出一个对应的index
3.5什么是哈希碰撞？
当传入的数据key对应计算出的hash值的后四位和上一个一样时，这时候计算出的index就会一致，就会发生碰撞，导致数据变成链表
例如:
(16-1)------->0 1111
“张三”------->0 1011
“李四”-------->1 1011
此时，就会发现，张三和李四计算出的hash值转化为二进制的后四位一致，导致计算出index一致
3.6JDK8为什么引入红黑树？
哈希碰撞，会带来链化，效率会变低
引入红黑树会提高查找效率
3.7扩容机制
每次扩容为初始容量的2倍
eg：16------->32
为了防止数据过多，导致线性查询，效率变低，扩容使得桶数变多，每条链上数据变少，查询更快

文章插图
四、手撕源码 1.核心属性分析
树化阈值-----8和64
负载因子0.75
扩容阈值，当哈希表中的元素超过阈值时，触发扩容
负载因子0.75，去计算阈值 eg：16*0.75
size-------当前哈希表中元素个数
--------当前哈希表结构修改次数
2.构造方法分析
public HashMap(int initialCapacity, float loadFactor) {//校验 小于0报错if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);//capacity大于最大值取最大值if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;//负载因子不能小于等于0if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;//tableSizeFor方法this.threshold = tableSizeFor(initialCapacity);}---------------------------------------------------------//传入一个初始容量，默认负载因子0.75public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}---------------------------------------------------------//无参数，负载因子默认0.75public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}---------------------------------------------------------//传入一个map的对象public HashMap(Map m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}
3.put方法分析
public V put(K key, V value) {//返回putVal方法，给key进行了一次rehashreturn putVal(hash(key), key, value, false, true);}----------------------------------------------------------static final int hash(Object key) {//让key对应的hash值的高16位也参与运算int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}----------------------------------------------------------final V putVal(int hash, K key, V value, booleanonlyIfAbsent,boolean evict) {//tab：引用当前HashMap的散列表//p：表示当前散列表的元素//n：表示散列表数组的长度//i：表示路由寻址的结果Node

• 上一页
• 1
• 2
• 3
• 4
• 下一页

• 5. HashMap如何降低Hash冲突概率
• java--HashMap数据结构
• 200道大数据面试常考Leetcode算法题
• 2、HashMap中的常量
• 数组+链表+红黑树 HashMap底层数据结构
• 干货：10个超经典JavaIDE插件，建议收藏！
• WeakHashMapLinkedHashMap TreeMap Set（H
• WeakHashMap概念和原理以及简单案例
• 二、HashMap和WeakHashMap的区别
• WeakHashMap解析