福建建设建设厅官方网站,网站建设属于软件开发吗,Wordpress修改主页网址,黄页网络的推广网站有哪些类型HashMap线程不安全#xff0c;底层数组链表红黑树 面试重点是put方法#xff0c;扩容
总结
put方法
HashMap的put方法#xff0c;首先通过key去生成一个hash值#xff0c;第一次进来是null#xff0c;此时初始化大小为16#xff0c;i (n - 1) hash计算下标值底层数组链表红黑树 面试重点是put方法扩容
总结
put方法
HashMap的put方法首先通过key去生成一个hash值第一次进来是null此时初始化大小为16i (n - 1) hash计算下标值第一次获取是null直接放入一个Node节点如果不是null分成下面三种情况 1如果发现hash和key相等将原来的覆盖 2不相等就要用到链表通过尾插法插入到尾部。超过8转成红黑树 3如果是TreeNode插入即可
扩容
首先上面put方法每次都会计算大小 如果超过16*0.75即12就会r调用resize方法 这里主要是老数组上面元素转到新数组上面去的逻辑 遍历如果老数组上面元素不是null 这里又是几种情况 1如果next下标是null 说明只有一个元素直接重新计算下标放入新数组 2判断是否是TreeNode 对TreeNode树进行拆分转到新数组不一定在一起。拆分后不一定还是树这里各种情况看节点对应的是高位还是低位。判断低位个数如果不超过6转成链表TreeNode转成Node。高位也一样。否则重新生成红黑树根据是否有高地位判断是否需要重新生成红黑树 3否则说明是个链表 将链表转到新数组上面去扩容后重新计算hash后下标不一定还是相同的所以不能直接转到新数组但是扩容后下标是有规律的。扩容后只有两种情况低位和高位。 哪些节点是在低位链表上面哪些节点是在高位链表上面。然后放到新数组即可。
源码如下
/*** 默认的初始容量-必须是二的幂。2的4次方16*/
static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16/*** 如果隐式指定了更高的值则使用最大容量由带有参数的构造函数中的任何一个执行。必须是二次方130。*/
static final int MAXIMUM_CAPACITY 1 30;/*** 在构造函数中未指定时使用的负载系数。*/
static final float DEFAULT_LOAD_FACTOR 0.75f;/*** 使用树而不是列表作为存储箱的存储箱计数阈值。当向至少有这么多节点的bin添加元素时bin会转换为树。该值必须大于2并且应至少为8以符合树木移除中关于收缩后转换回普通垃圾箱的假设。*/
static final int TREEIFY_THRESHOLD 8;/*** 在调整大小操作期间取消尝试拆分垃圾箱的垃圾箱计数阈值。应小于TREEIFY_THRESHOLD并且最多6个以便在去除时进行收缩检测。*/
static final int UNTREEIFY_THRESHOLD 6;/*** 可以将垃圾箱树化的最小桌子容量。否则如果一个bin中的节点太多则会调整表的大小。应至少为4*TREEIFY_THRESHOLD以避免调整大小阈值和树化阈值之间的冲突。*/
static final int MIN_TREEIFY_CAPACITY 64;/*** 基本hash bin节点用于大多数条目。TreeNode子类见下文Entry子类见LinkedHashMap。*/
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;}
}
new HashMap默认无参构造负载因子0.75
public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // 这个是0.75f}/*** The number of times this HashMap has been structurally modified* Structural modifications are those that change the number of mappings in* the HashMap or otherwise modify its internal structure (e.g.,* rehash). This field is used to make iterators on Collection-views of* the HashMap fail-fast. (See ConcurrentModificationException).*/transient int modCount;//记录修改次数put方法
//put方法
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}
/*** 计算key.hashCode并将哈希的高位扩展XOR到低位。因为该表使用了两个掩码的幂所以仅在当前掩码之上以位为单位变化的哈希集总是会发生冲突。已知的例子包括在小表中保存连续整数的浮点键集。因此我们应用了一种变换将高位的影响向下扩展。比特扩展的速度、效用和质量之间存在权衡。由于许多常见的哈希集已经合理分布因此不会从扩展中受益并且因为我们使用树来处理箱中的大型冲突集所以我们只需以最便宜的方式对一些移位的比特进行异或以减少系统损失并将最高比特的影响纳入其中否则由于表绑定这些比特将永远不会用于索引计算*/
static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}首先通过hash方法传入key计算出一个int类型的hash值。
这里为什么不直接用key.hashCode()的值呢
key.hashCode()计算出一个hash值然后赋值给hh右移16位然后两个做异或运算 计算的值右移16位右移之前和右移之后的值进行异或^运算得到最终的hashcode这个最终的值时通过低位和高位一起异或运算算出来的。这样高位也参加到了计算中高位都是0.
下面还有计算数组下标的 i (n - 1) hash第一次n16做运算何为运算即都为1则为1。 比方15的二进制时是 0000 1111 而上面计算得到的hash值和这个做运算值在0-15之间。这样(n - 1) hash计算是为了使均匀分布。0-15出现频率都差不多。hash值比较均匀最后计算的i就比较均匀。为啥要n-1如果16的话做运算得到结果就两种
然后调用putVal方法入参事key的hash值keyvaluefalsetrue
这里是put的核心方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//定义tabpni初始化一些变量NodeK,V[] tab; NodeK,V p; int n, i;//这里为啥不直接用table性能问题我们自己初始化变量是属于栈中而table是堆中不用每次从堆中去拿table。//第一次进来是nullif ((tab table) null || (n tab.length) 0)//这里调用resize初始化及扩容第一次返回16n (tab resize()).length;//那16//下面这个i是如何来的i (n - 1) hash算出数组下标如果没有值是null就放到这里。if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);//如果这个位置不是null这里就涉及到链表else {//如果这个位置上不是null说明这个位置有东西NodeK,V e; K k;//如果发现hash和key相等if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))//直接赋值到e下面不会走了e p;//如果这个位置上的是TreeNode类型else if (p instanceof TreeNode)//进行红黑树的插入e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {//不相等就要用到链表这里for循环//如何加通过Node对象的next属性for (int binCount 0; ; binCount) {//binCount0有一个节点所以下面要8-17binCount8//尾插法找到尾节点尾节点的nextnullif ((e p.next) null) {//将新的节点给到next属性完成链表插入p.next newNode(hash, key, value, null);//如果bincount的大小8-17binCount7链表有8个节点但是你自己上面newNode还新增了一个其实现在有9个节点//为啥超过8个转红黑树这个和红黑树的性能有关if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//如果发现链表中有相等的也是无需做什么了直接覆盖值if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}//如果e不是nullif (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)更新valuee.value value;afterNodeAccess(e);//将原来老的value返回return oldValue;}}modCount;//统计sizehashmap大小和域值threshold16*0.75比较//不停往集合put如果大于12threshold个就会调用resize扩容if (size threshold)resize();afterNodeInsertion(evict);return null;}/*** 初始化或加倍表大小。如果为null则根据字段阈值中的初始容量目标进行分配。否则因为我们使用的是二次幂展开所以每个bin中的元素必须保持在同一索引或者在新表中以二次幂偏移量移动。** return the table*/transient NodeK,V[] table;int threshold;final NodeK,V[] resize() {NodeK,V[] oldTab table;//一开始时nullint 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;}else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)//左移1位翻倍newThr oldThr 1; // double threshold}else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;else { // zero initial threshold signifies using defaults//一开始0走到这里执行newCap DEFAULT_INITIAL_CAPACITY;//默认1614newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//16*0.7512这个和扩容有关系扩容的一个域值}if (newThr 0) {float ft (float)newCap * loadFactor;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold newThr;//第一次将12赋值给thresholdSuppressWarnings({rawtypes,unchecked})//这里开始创建Node第一次newCap16这里创建出一个16大小的node数组NodeK,V[] newTab (NodeK,V[])new Node[newCap];//将16给到tabletable16table newTab;//老数组上面元素转到新数组上面去if (oldTab ! null) {//遍历老数组for (int j 0; j oldCap; j) {NodeK,V e;//如果老数组这个元素不是nullif ((e oldTab[j]) ! null) {oldTab[j] null;//如果为null说明只有一个元素if (e.next null)//重新计算放到新数组中newTab[e.hash (newCap - 1)] e;//判断是不是TreeNodeelse if (e instanceof TreeNode)//对TreeNode树进行拆分转到新数组不一定在一起。拆分后不一定还是树这里各种情况看节点对应的是高位还是低位。判断低位个数如果不超过6转成链表TreeNode转成Node。否则还是TreeNode然后判断高位低位如果低位不用动如果有高位说明树进行了拆分重新生成红黑树。((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // preserve order//是个链表将链表转到新数组上面去扩容后重新计算hash后下标不一定还是相同的所以不能直接转到新数组但是扩容后下标是有规律的。只有两种情况低位和高位//哪些节点是在低位链表上面哪些节点是在高位链表上面NodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next;//e.hash oldCap0判断在低位还是高位等于0在低位if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);//低位链表放到newTabif (loTail ! null) {loTail.next null;newTab[j] loHead;}//高位链表放到newTabif (hiTail ! null) {hiTail.next null;newTab[j oldCap] hiHead;}}}}}return newTab;//第一次调用的最后返回16}转红黑树的方法
final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;//MIN_TREEIFY_CAPACITY64判断数组长度是否小于64if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY)resize();else if ((e tab[index (n - 1) hash]) ! null) {TreeNodeK,V hd null, tl null;do {//将这个链表上面的Node节点遍历变成TreeNode节点完成转换TreeNodeK,V p replacementTreeNode(e, null);if (tl null)hd p;else {//将prev也赋值改成双向链表方便去拿前一个节点p.prev tl;tl.next p;}tl p;} while ((e e.next) ! null);if ((tab[index] hd) ! null)//将TreeNode节点转成红黑树hd.treeify(tab);}}红黑树查询删除等时间复杂度都是logn要快一点提升查询性能 并不是超过8就一定转成红黑树而是还要判断数组长度64比较小于64扩容 为啥要判断数组长度和扩容有关resize扩容将链表拆分成两个短链表。
扩容两个地方进行扩容 一个是计算hashmap大小大于12进行扩容 一个是链表长度大于8不一定转成红黑树而是通过判断数组长度是否小于64进行扩容
扩容先生成新数组再把老数组上面元素放到新数组位置上
扩容如果是TreeNode情况
final void split(HashMapK,V map, NodeK,V[] tab, int index, int bit) {TreeNodeK,V b this;// Relink into lo and hi lists, preserving order//低位TreeNodeK,V loHead null, loTail null;//高位TreeNodeK,V hiHead null, hiTail null;int lc 0, hc 0;//低位和高位数量for (TreeNodeK,V e b, next; e ! null; e next) {next (TreeNodeK,V)e.next;e.next null;if ((e.hash bit) 0) {if ((e.prev loTail) null)loHead e;elseloTail.next e;loTail e;lc;}else {if ((e.prev hiTail) null)hiHead e;elsehiTail.next e;hiTail e;hc;}}
//如果低位不是nullif (loHead ! null) {//如果低位数量不超过6if (lc UNTREEIFY_THRESHOLD)//将TreeNode转成Node转成了链表tab[index] loHead.untreeify(map);else {//如果超过说明要用红黑树tab[index] loHead;//如果高位不是null说明有高位此时需要重新生成红黑树如果没有高位就不用走到treeify方法用之前的就行。不需要重新再生成红黑树。if (hiHead ! null) // (else is already treeified)loHead.treeify(tab);}}if (hiHead ! null) {if (hc UNTREEIFY_THRESHOLD)tab[index bit] hiHead.untreeify(map);else {tab[index bit] hiHead;if (loHead ! null)hiHead.treeify(tab);}}}红黑树 根节点是黑色的 每个叶子节点都是黑色的空节点NIL也就是说叶子节点不存储数据 任何相邻的节点都不能同时为红色红色节点是被黑色节点隔开的 每个节点从该节点到达其可达叶子节点的所有路径都包含相同数目的黑色节点
static K,V TreeNodeK,V balanceInsertion(TreeNodeK,V root,TreeNodeK,V x) {x.red true;for (TreeNodeK,V xp, xpp, xppl, xppr;;) {//如果是null父节点返回if ((xp x.parent) null) {x.red false;return x;}//如果父节点是黑色不用调整返回rootelse if (!xp.red || (xpp xp.parent) null)return root;//父节点是红色的情况//父节点正好是xpp的左节点if (xp (xppl xpp.left)) {//开始变色if ((xppr xpp.right) ! null xppr.red) {//父节点和叔叔节点变黑祖父节点变红xppr.red false;xp.red false;xpp.red true;//最上面节点颜色变化再次递归继续进行调整x xpp;}else {if (x xp.right) {root rotateLeft(root, x xp);xpp (xp x.parent) null ? null : xp.parent;}if (xp ! null) {xp.red false;if (xpp ! null) {xpp.red true;root rotateRight(root, xpp);}}}}else {if (xppl ! null xppl.red) {xppl.red false;xp.red false;xpp.red true;x xpp;}else {if (x xp.left) {root rotateRight(root, x xp);xpp (xp x.parent) null ? null : xp.parent;}if (xp ! null) {xp.red false;if (xpp ! null) {xpp.red true;root rotateLeft(root, xpp);}}}}}}HashMap为什么用红黑树
R-B Tree。它是一种不严格的平衡二叉查找树 引入RB-Tree是功能、性能、空间开销的折中结果。 红黑是用非严格的平衡来换取增删节点时候旋转次数的降低任何不平衡都会在三次旋转之内解决而AVL是严格平衡树因此在增加或者删除节点的时候根据不同情况旋转的次数比红黑树要多。 就插入节点导致树失衡的情况AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance旋转的量级是O(1) 删除节点导致失衡AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡旋转的量级为O(logN)而RB-Tree最多只需要旋转3次实现复衡只需O(1)所以说RB-Tree删除节点的rebalance的效率更高开销更小
hashmap使用红黑树的原因是这样可以利用链表对内存的使用率以及红黑树的高效检索是一种很有效率的数据结构。AVL树是一种高度平衡的二叉树所以查找的效率非常高但是有利就有弊AVL树为了维持这种高度的平衡就要付出更多代价。每次插入、删除都要做调整复杂、耗时。对于有频繁的插入、删除操作的数据集合使用AVL树的代价就有点高了。而且红黑树只是做到了近似平衡并不严格的平衡所以在维护的成本上要比AVL树要低。所以hashmap用红黑树。
红黑树相比avl树在检索的时候效率其实差不多都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡他允许局部很少的不完全平衡这样对于效率影响不大但省去了很多没有必要的调平衡操作avl树调平衡有时候代价较大所以效率不如红黑树在现在很多地方都是底层都是红黑树的天下啦。
java8不是用红黑树来管理hashmap而是在hash值相同的情况下且重复数量大于8用红黑树来管理数据。 红黑树相当于排序数据可以自动的使用二分法进行定位性能较高。一般情况下hash值做的比较好的话基本上用不到红黑树。
AVL树用于自平衡的计算牺牲了插入删除性能但是因为最多只有一层的高度差查询效率会高一些。红黑树的高度只比高度平衡的AVL树的高度log2n仅仅大了一倍在性能上却好很多。
HashMap为什么要转成树为什么阈值是8
当链表长度不断变长肯定会对查询性能有一定的影响所以才需要转成树。 选择8是根据概率统计决定。
HashMap源码里有一段注解大概意思是 理想情况下使用随机的哈希码容器中节点分布在hash桶中的频率遵循泊松分布(具体可以查看http://en.wikipedia.org/wiki/Poisson_distribution)按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表可以看到链表中元素个数为8时的概率已经非常小再多的就更少了所以原作者在选择链表元素个数时选择了8是根据概率统计而选择的。 这里看到8的时候概率小的可怜了。
空间和时间的权衡 TreeNodes占用空间是普通Nodes的两倍所以只有当bin包含足够多的节点时才会转成TreeNodes而是否足够多就是由TREEIFY_THRESHOLD的值决定的。当bin中节点数变少时又会转成普通的bin。并且我们查看源码的时候发现链表长度达到8就转成红黑树当长度降到6就转成普通bin。
为什么不用BTree
B树在数据库中被应用的原因是其“矮胖”的特点B树的非叶子结点不存储数据所以每个结点能存储的关键字更多。所以B树更能应对大量数据的情况。Mysql就是用的BTree。 jdk1.7中的HashMap本来是数组链表的形式链表由于其查找慢的特点所以需要被查找效率更高的树结构来替换。如果用B树的话在数据量不是很多的情况下数据都会“挤在”一个结点里面。这个时候遍历效率就退化成了链表。
结论b树不属于二叉树因为二叉查找树的查找效率是最高的,如果内存能装下完整的树,最好使用二叉查找树b树是退而求其次的方式。
所以就是根据数据量去选择HashMap数据量不大没有必要用BTree。
