基于hashing原理,通过put(key,value)
和get(key)
方法存储和获取对象
当我们存储对象的时候,把键值对传给put(key,value)
方法时,它调用键对象key的hashCode()方法来计算hashCode,然后找到bucket位置,来存储值对象value。
当获取对象时,也是先计算key的hashCode,找到数组中对应位置的bucket位置,然后通过key的equals()方法找到正确的键值对key-value,然后返回值对象value。
HashMap里有hash碰撞(冲突),HashMap使用链表来解决碰撞问题,当发生了碰撞,对象将会存储在链表的下一个节点中。
HashMap的每个链表中存储的是key-value对象,当两个不同的键对象key的hashCode相同时,那就发生了碰撞(冲突),那它会存储在同一个bucket的位置,bucket的位置存不下这两个点,那么就通过链表来存储。(在jdk8里,链表长度大于8的话就会变成红黑树)
取数据可通过键对象key的equals()方法用来找到正确的键值对key-value。
JDK8中HashMap的底层数据结构:用**数组+链表+红黑树的结构来优化,链表长度大于8同时满足HashMap中元素个数大于64则 变红黑树**,长度小于6变回链表
H(key1) == H(key2)
Node[] table
这个Node类型的数组存储了HashMap的真正数据 static class Node<K,V> implements Map.Entry<K,V>
。为什么链表长度为8转为红黑树?
为什么链表长度为6,红黑树就转为链表呢?
JDK1.7中HashMap插入的过程:— put操作
public V put(K key, V value) {
// 步骤1
if (table == EMPTY_TABLE) { //判断如果表空进行初始化
inflateTable(threshold);
}
// 步骤2
if (key == null) //判断是否键为空
return putForNullKey(value); //遍历table[0]是否存在 e.key == null
// 步骤3
int hash = hash(key); //计算hash值
int i = indexFor(hash, table.length); //计算bucket的位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) { //遍历链表
Object k;
// hash相同 equals比较是真 则替换 返回旧值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i); //添加数据 这里包含hash冲突的处理。
return null;
}
jdk7 中的hash函数处理
final int hash(Object k) {
/**
获取哈希干扰因子,该因子会跟根据HashMap的容量进行变更
变更情况根据上一步的“final boolean initHashSeedAsNeeded(int capacity)
”方法动态变更
**/
int h = hashSeed;
//如果为干扰因子不为0,且传入的key类型为String,则使用特定的算法(sun.misc.Hashing.stringHash32((String) k))对该key进行hash计算。并返回
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
//如果哈希干扰因子为0 或者 k的类型不为String则使用异或操作变更key的hashcode
h ^= k.hashCode();
//为了减少Hash冲突出现次数进行必要的位干扰,默认负载因子是8.
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
扰动实现复杂,一共九次扰动: 5次异或 加上4次位运算
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
//当size大小大于或等于阈值的时候,将会进行扩容操作,将数据元素重新计算位置后放入newTable中,Hash位置会重新计算
resize(2 * table.length); //2倍扩容
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex); //创建Entry的时候会有hash冲突的代码
}
不小于threshold阈值直接2倍扩容,Hash位置会重新计算。
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//根据头节点构建----头插法的实现
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
哈希冲突时链表插入数据使用头插(JDK1.7)
JDK7中获取数据的过程—get操作
//获取key值为key的元素值
public V get(Object key) {
if (key == null)//如果Key值为空,则获取对应的值,这里也可以看到,HashMap允许null的key,其内部针对null的key有特殊的逻辑
return getForNullKey();
Entry<K,V> entry = getEntry(key);//获取实体
return null == entry ? null : entry.getValue();//判断是否为空,不为空,则获取对应的值
}
//获取key为null的实体
private V getForNullKey() {
if (size == 0) {//如果元素个数为0,则直接返回null
return null;
}
//key为null的元素存储在table的第0个位置
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)//判断是否为null
return e.value;//返回其值
}
return null;
}
get方法通过key值返回对应value,如果key为null,直接去table[0]处检索。
//获取键值为key的元素
final Entry<K,V> getEntry(Object key) {
if (size == 0) {//元素个数为0
return null;//直接返回null
}
int hash = (key == null) ? 0 : hash(key);//获取key的Hash值
for (Entry<K,V> e = table[indexFor(hash, table.length)];//根据key和表的长度,定位到Hash桶
e != null;
e = e.next) {//进行遍历
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))//判断Hash值和对应的key,合适则返回值
return e;
}
return null;
}
JDK8中HashMap源码插入的过程:
==
返回True,或者equals判断相同,执行替换操作(图中的直接覆盖value)static final int hash(Object key) { // 计算key的hash值
int h;
// 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//进行异或
}
将key的hashCode与该hashCode的无符号右移16位,异或起来得到的。
扰动实现简单 一共2次扰动 1次是异或 加上1次位运算
jdk8中hashmap put方法源码:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1.校验table是否为空或者length等于0,如果是则调用resize方法进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2.通过hash值计算索引位置,将该索引位置的头节点赋值给p,如果p为空则直接在该索引位置新增一个节点即可
if ((p = tab[i = (n - 1) & hash]) == null) //头节点是否为空
tab[i] = newNode(hash, key, value, null);
else {
// table表该索引位置不为空,则进行查找
Node<K,V> e; K k;
// 3.判断p节点的key和hash值是否跟传入的相等,如果相等, 则p节点即为要查找的目标节点,将p节点赋值给e节点
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 4.判断p节点是否为TreeNode, 如果是则调用红黑树的putTreeVal方法查找目标节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 5.走到这代表p节点为普通链表节点,则调用普通的链表方法进行查找,使用binCount统计链表的节点数
for (int binCount = 0; ; ++binCount) {
// 6.如果p的next节点为空时,则代表找不到目标节点,则新增一个节点并插入链表尾部
if ((e = p.next) == null) { //一直遍历到链表的尾部,因为链表的尾部是null
p.next = newNode(hash, key, value, null);
// 7.校验节点数是否超过8个,如果超过则调用treeifyBin方法将链表节点转为红黑树节点,
// 减一是因为循环是从p节点的下一个节点开始的
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 8.如果e节点存在hash值和key值都与传入的相同,则e节点即为目标节点,跳出循环
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // 将p指向下一个节点
}
}
// 9.如果e节点不为空,则代表目标节点存在,使用传入的value覆盖该节点的value,并返回oldValue
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 用于LinkedHashMap
return oldValue;
}
}
++modCount;
// 10.如果插入节点后节点数超过阈值,则调用resize方法进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict); // 用于LinkedHashMap
return null;
}
JDK8 hashmap中的get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value; //计算hash值
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1.对table进行校验:table不为空 && table长度大于0 &&
// table索引位置(使用table.length - 1和hash值进行位与运算)的节点不为空
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {//判断头节点是否为null
// 2.检查first节点的hash值和key是否和入参的一样,如果一样则first即为目标节点,直接返回first节点
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))// always check first node
return first;
// 3.如果first不是目标节点,并且first的next节点不为空则继续遍历
if ((e = first.next) != null) {
if (first instanceof TreeNode)
// 4.如果是红黑树节点,则调用红黑树的查找目标节点方法getTreeNode
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 5.执行链表节点的查找,向下遍历链表, 直至找到节点的key和入参的key相等时,返回该节点
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 6.找不到符合的返回空
return null;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁