北京东城区做网站的公司,网站备案到期了怎么办,WordPress文章 溢出,事业圈app哪家公司开发的在Java中
在Java中hash表的底层数据结构与扩容等已经是面试集合类问题中几乎必问的点了。网上有对源码的解析已经非常详细了我们这里还是说说其底层实现。
基础架构
public class HashMapK,V extends AbstractMapK,V implements MapK,V, Cloneable,…在Java中
在Java中hash表的底层数据结构与扩容等已经是面试集合类问题中几乎必问的点了。网上有对源码的解析已经非常详细了我们这里还是说说其底层实现。
基础架构
public class HashMapK,V extends AbstractMapK,V implements MapK,V, Cloneable, Serializable {private static final long serialVersionUID 362498820763181265L;// 默认的初始容量是16static final int DEFAULT_INITIAL_CAPACITY 1 4;// 最大容量static final int MAXIMUM_CAPACITY 1 30;// 默认的负载因子static final float DEFAULT_LOAD_FACTOR 0.75f;// 当桶(bucket)上的结点数大于等于这个值时会转成红黑树static final int TREEIFY_THRESHOLD 8;// 当桶(bucket)上的结点数小于等于这个值时树转链表static final int UNTREEIFY_THRESHOLD 6;// 桶中结构转化为红黑树对应的table的最小容量static final int MIN_TREEIFY_CAPACITY 64;// 存储元素的数组总是2的幂次倍transient Nodek,v[] table;// 一个包含了映射中所有键值对的集合视图transient Setmap.entryk,v entrySet;// 存放元素的个数注意这个不等于数组的长度。transient int size;// 每次扩容和更改map结构的计数器transient int modCount;// 阈值(容量*负载因子) 当实际大小超过阈值时会进行扩容int threshold;// 负载因子final float loadFactor;
}
本文所有Java代码均来自JavaGuideHashMap 源码分析 | JavaGuide这里主要就是定义一些必要的常量被用于哈希表的创建参数扩容参数等待。
然后就是hash表中的Node节点的数据结构我们的k-v键值对就存储在一个Node类里面。在jdk1.7前其实与redis中的字典Dictionary数据结构中的hash表十分类似即采用线性搜索和拉链法。在jdk1.8 及以后版本1中添加了树化即当节点数大于8就会将当前节点转化为红黑树这样做的目的主要是为了增加搜索效率红黑树的时间复杂度为O(log n)如果没有树化链表查询的时间复杂度为O(n) 。接下来就看看JavaGuide中给出的节点类
链表节点
// 继承自 Map.EntryK,V
static class NodeK,V implements Map.EntryK,V {final int hash;// 哈希值存放元素到hashmap中时用来与其他元素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; }// 重写hashCode()方法public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue value;value newValue;return oldValue;}// 重写 equals() 方法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;}
}
树节点
static final class TreeNodeK,V extends LinkedHashMap.EntryK,V {TreeNodeK,V parent; // 父TreeNodeK,V left; // 左TreeNodeK,V right; // 右TreeNodeK,V prev; // needed to unlink next upon deletionboolean red; // 判断颜色TreeNode(int hash, K key, V val, NodeK,V next) {super(hash, key, val, next);}// 返回根节点final TreeNodeK,V root() {for (TreeNodeK,V r this, p;;) {if ((p r.parent) null)return r;r p;}
resize()
然后我们来重点讲一讲resize()扩容这个方法。
final NodeK,V[] resize() {NodeK,V[] oldTab table;int oldCap (oldTab null) ? 0 : oldTab.length;int oldThr threshold;int newCap, newThr 0;if (oldCap 0) {// 超过最大值就不再扩充了就只好随你碰撞去吧if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;}// 没超过最大值就扩充为原来的2倍else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold}else if (oldThr 0) // initial capacity was placed in threshold// 创建对象时初始化容量大小放在threshold中此时只需要将其作为新的数组容量newCap oldThr;else {// signifies using defaults 无参构造函数创建的对象在这里计算容量和阈值newCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr 0) {// 创建时指定了初始化容量或者负载因子在这里进行阈值初始化// 或者扩容前的旧容量小于16在这里计算新的resize上限float ft (float)newCap * loadFactor;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);}threshold newThr;SuppressWarnings({rawtypes,unchecked})NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;if (oldTab ! null) {// 把每个bucket都移动到新的buckets中for (int j 0; j oldCap; j) {NodeK,V e;if ((e oldTab[j]) ! null) {oldTab[j] null;if (e.next null)// 只有一个节点直接计算元素新的位置即可newTab[e.hash (newCap - 1)] e;else if (e instanceof TreeNode)// 将红黑树拆分成2棵子树如果子树节点数小于等于 UNTREEIFY_THRESHOLD默认为 6则将子树转换为链表。// 如果子树节点数大于 UNTREEIFY_THRESHOLD则保持子树的树结构。((TreeNodeK,V)e).split(this, newTab, j, oldCap);else {NodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next;// 原索引if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}// 原索引oldCapelse {if (hiTail null)hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);// 原索引放到bucket里if (loTail ! null) {loTail.next null;newTab[j] loHead;}// 原索引oldCap放到bucket里if (hiTail ! null) {hiTail.next null;newTab[j oldCap] hiHead;}}}}}return newTab;
}
在Java的hashmap中在jdk1.8以后是通过负载因子的判断来选择是否进行resize()方法默认负载因子是0.75。如果存储数据与当前容量之比为0.75就会进行扩容。同时当我们存储数据过多时无论我们的hash算法做了什么样的优化一定还是会有hash冲突的存在所以为了解决冲突我们使用拉链法。在插入数据时我们采用的方式是将已存在hashmap中的键值对的值与插入的值进行比较如果二者相等就进行覆盖如果二者不相等就使用尾加法加载链表尾部在redis5中使用的是equals()进行比较因为redis存储的所有值都是String字符串。。我们将一个拉链称之为一个哈希桶。但是我们试想如果一个桶的节点过于多了那么我们查找时遍历起来是很花费时间的在hashtable中使用的是线性搜索法加拉链法来解决这个问题的但是如果我们一直盲目使用线性搜索法的话我们暂且将线性搜索法占据的hash表数组槽位与hash表当前容量的比值称为线性搜索负载因子当线性搜索负载因子过大时我们的hash表的查找效率会受到极大的影响。所有在jdk1.8后的树化则很好解决了这个问题即当拉链上的节点树大于8时会先对数组容量进行判断如果小于64先扩容(hashmap扩容都为2倍扩容)否则进行拉链法。(为什么先扩容呢因为hashmap的hash函数计算与容量有关所以扩容后会得到新的hash值避免了hash冲突相较于红黑树的遍历我们肯定更优先考虑的是这种做法)
在Golang中
基础架构
type hmap struct {count intflags uint8B uint8noverflow uint16hash0 uint32buckets unsafe.Pointeroldbuckets unsafe.Pointernevacuate uintptrextra *mapextra
}type mapextra struct {overflow *[]*bmapoldoverflow *[]*bmapnextOverflow *bmap
} count 表示当前hash表中的元素。 B 表示当前hash表持有的 buckets (即桶数组)数量由于hash表中桶数量都为2的倍数所以该字段会存储对数。这里和redis的hash表一样在redis的rehash过程中需要先创建一个2倍旧数组长度的新数组然后进行hash桶迁移。 oldbuckets是哈希表在扩容时用于保存之前buckets的字段它的大小是当前buckets的一半。
在go的hashmap中我们使用溢出桶来降低扩容频率本质上就是预先分配几个数组空间用于存储超出容量的k-v 扩容方法 开放寻址法 其实就是线性搜索法。简而言之就是依次探测和比较数组中的元素以判断目标键值对是否存在于哈希表当我们向当前哈希表写入新数据时如果发生了冲突就会将键值对写入下一个索引不为空的位置。开放寻址法中对性能影响最大的是装载因子它是数组中元素数量与数组大小的比值。随着装 载因子的增加线性探测的平均用时会逐渐增加这会影响哈希表的读写性能。当装载率超过70% 之后哈希表的性能就会急剧下降而一旦装载率达到100%,整个哈希表就会完全失效这时查找 和插入任意元素的时间复杂度都是O(n)我们需要遍历数组中的全部元素所以在实现哈希表时一 定要关注装载因子的变化。 拉链法 和jdk 1.7 一样就不做过多解释。
在go中的k-v添加我们需要注意的是当插入的k-v小于25时会以如下方式插入
hash : make(map[string]int, 3)
hash[1] 1
hash[2] 2
hash[3] 3
如若大于25个就会分别创建两个数组分别存储k 和 v然后以遍历形式插入。
言归正传在go的hashmap中扩容条件为装在因子超过6.5 || 哈希表使用太多溢出桶。
同时由于在go的hashmap的扩容不是原子性的所以需要判断以避免二次扩容这和redis也一样增删改查需要判断当前数据库的hash表是否在进行rehash。
扩容数据结构
说了这么多接下来我们就来重点介绍go的hashmap扩容的数据结构变化。runtime. evacuate会将一个旧桶中的数据分流到两个新桶所以它会创建两个用于保存分配 上下文的runtime.evacDst结构体这两个结构体分别指向了一个新桶。
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {b : (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))newbit : h.noldbuckets()if !evacuated(b) {var xy [2]evacDstx : xy[0]x.b (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))x.k add(unsafe.Pointer(x.b), dataOffset)x. v add(x.k, bucketCnt*uintptr(t.keysize))y xy[1Jy. b (*bmap)(add(h.buckets, (oldbucketnewbit)*uintptr(t.bucketsize)))y.k add(unsafe.Pointer(y.b), dataOffset)y.v add(y.k, bucketCnt*uintptr(t.keysize))
}
go中的hashamp扩容分为等量扩容和翻倍扩容如果是前者就只初始化一个桶如果是翻倍扩容就会初始化两个桶。会把一个链表数据分到新表两个位置将8个节点分流到两个桶中这里获取桶位置采用取模或者位运算来得到数据存储的桶位置然后将k的指针指向两个桶位置。 在数据查询时会先判断是否在进行分流如果在进行就先会从旧桶中读取数据。相较于Java的hashmap它不会一次性将所有的元素重新哈希而是在每次插入元素时都会将一部分元素移动到新的桶中。这样可以避免一次性的大量计算但可能会导致一段时间内的查询效率稍低。
