苏州市工业园区规划建设局网站,网站建设比较合理的流程,网站建设 技术 哪些方面,互联网公司办公室简介#xff1a;
是基于 哈希表 实现的#xff0c;存放 k-v 键值对#xff0c;非同步的方式#xff08;未加 synchronized #xff09;非线程安全的#xff0c;hashmap 无序的数据结构#xff1a; 数组 链表 数组 链表 红黑树「链表 和 链表 红黑树 都是为了解…简介
是基于 哈希表 实现的存放 k-v 键值对非同步的方式未加 synchronized 非线程安全的hashmap 无序的数据结构 数组 链表 数组 链表 红黑树「链表 和 链表 红黑树 都是为了解决 哈希冲突哈希冲突 两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同 ,区别是 链表 红黑树 在达到 阈值 8 数组长度 64 才会进行转为红黑树———原因 虽然红黑树会让结构更加复杂但是这时查询效率更高要是数组长度比较少的话应该尽量避免红黑树不然的话 红黑树需要进行左旋右旋变色这些操作来保持平衡 并且 数组的长度 64 的时候 搜索的时间是相对来说比较快的」
数据结构
存储说明 HashMapString,Integermap new HashMap();创建HashMap对象后 在jdk8前 : 底层创建了长度是16的一维数组 Entry[]table。 在jdk8以后并没有 在创建集合对象时创建数组而是在首次调用put()方法时底层创建长度为16的Node[] table数组 假设向哈希表中存储数据 key1-value1随后 根据 key1 调用String类中的hashCode()方法计算key1的哈希码值此哈希码值经过某种算法计算以后得到在Node 数组中的存放的位置如果比位置上的数据为空此时的 key1-value1添动加成功。例如计算的索引是2 面试题HashMap中hash函数是怎么实现的还有哪些hash函数的实现方式 对key的hashCode做hash操作结合数组的长度进行 无符号右移( ) 、按位异或 (^)、按位与( ) 运算。还有平方取中法除留余数法伪随机数法。其余三种方式效率都比较低。而无符号右移16位做异或运算效率是比较高的 假设向哈希表中存储 key2-value2根据键的key2计算出的 哈希值并结合数组长度计算出的索引那么一旦此时的索引位置有数据就会比较hash 值要是hash 值不一样那么就要在这个索引空间上新创建一个节点然后 将key2-value2 存放到这个节点中。 假设向哈希表中存储 key1-value3根据键的key1计算出的 哈希值此时的索引位置和之前肯定是一样的 此时就会比较后添加的数据的key和已经存在的哈希值是否相同 如果相同继续比较调用后添加的key1的所属类的equals()比较内容是否相等。 如果equals()返回false此时继续添加。如果equals()返回true:则后添加的 value3 替换之前的 value1 面试题当两个对象的hashCode相等时会怎么样 会产生哈希碰撞 进一步比较通过equals比较key 内容是否相同 相同则新的value覆盖之前的value不相同否则遍历链接到链表后面链表长度 8 且 数组长度 64 就转为红黑树存储
红黑树结构复杂为什么使用红黑树为什么阈值规定为 8
哈希函数取得再好也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时这个桶下有一条长长的链表这个时候 HashMap 就相当于一个单链表假如单链表有 n 个元素遍历的时间复杂度就是 O(n)完全失去了它的优势。针对这种情况JDK 1.8 中引入了 红黑树查找时间复杂度为 O(logn)来优化这个问题当链表长度很小的时候即使遍历速度也非常快但是当链表长度不断变长肯定会对查询性能有一定的影响所以才需要转成树。见源码 size表示 HashMap中K-V的实时数量 注意这个不等于数组的长度 。 threshold( 临界值) capacity(容量) * loadFactor( 加载因子 )。这个值是当前已占用数组长度的最大值。size超过这个临界值就重新resize(扩容)扩容后的 HashMap 容量是之前容量的两倍 。 源码分析
声明变量
// 默认初始容量 - 必须是 2 的幂
static final int DEFAULT_INITIAL_CAPACITY 1 4; // 16 创建的时候无参默认16// 默认 集合的最大容量。必须是 2 的幂 2 的 30 次方。
static final int MAXIMUM_CAPACITY 1 30;// 默认 使用的负载因子。static final float DEFAULT_LOAD_FACTOR 0.75f;// 树化的阈值
static final int TREEIFY_THRESHOLD 8;// 调整大小扩容时 取消树化转为链表 的阈值
static final int UNTREEIFY_THRESHOLD 6;// 可以被 树化的最小 数组 的容量 为了避免进行扩容、树形化选择的冲突这个值不能小于 4 * TREEIFY_THRESHOLD (8)
static final int MIN_TREEIFY_CAPACITY 64;// 存储元素的数组 初始化的大小一般是 2的 n 次幂
// jdk8之前数组类型是EntryK,V类型。从jdk1.8之后是NodeK,V类型。只是换了个名字都实现了一样的接口Map.EntryK,V。负责存储键值对数据的。
transient NodeK,V[] table;//存放具体的元素的集合 和 缓存
transient SetMap.EntryK,V entrySet;//table 数组的存储个数
transient int size;//记录 HashMap的修改次数,每次扩容和更改map结构的计数器
transient int modCount; //临界值 当实际大小( 数组长度(容量) * 负载因子)超过临界值时会进行扩容;可以 衡量数组是否需要扩增的一个标准。 扩容后的 HashMap 容量是之前容量的两倍.
int threshold;//加载因子
// 计算HashMap的实时加载因子的方法为size/capacity而不是占用桶的数量去除以capacity。capacity 是桶的数量也就是 table 的长度length。
final float loadFactor;链表节点
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;}
}树节点
static final class TreeNodeK,V extends LinkedHashMap.EntryK,V {TreeNodeK,V parent; // red-black tree linksTreeNodeK,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;}}/*** 确保给定的根是其 bin 的第一个节点。*/static K,V void moveRootToFront(NodeK,V[] tab, TreeNodeK,V root) {int n;if (root ! null tab ! null (n tab.length) 0) {int index (n - 1) root.hash;TreeNodeK,V first (TreeNodeK,V)tab[index];if (root ! first) {NodeK,V rn;tab[index] root;TreeNodeK,V rp root.prev;if ((rn root.next) ! null)((TreeNodeK,V)rn).prev rp;if (rp ! null)rp.next rn;if (first ! null)first.prev root;root.next first;root.prev null;}assert checkInvariants(root);}}/*** 使用给定的哈希值和密钥查找从根 p 开始的节点。 kc 参数在第一次使用比较键时缓存可比较的ClassFor(key)。*/final TreeNodeK,V find(int h, Object k, Class? kc) {TreeNodeK,V p this;do {int ph, dir; K pk;TreeNodeK,V pl p.left, pr p.right, q;if ((ph p.hash) h)p pl;else if (ph h)p pr;else if ((pk p.key) k || (k ! null k.equals(pk)))return p;else if (pl null)p pr;else if (pr null)p pl;else if ((kc ! null ||(kc comparableClassFor(k)) ! null) (dir compareComparables(kc, k, pk)) ! 0)p (dir 0) ? pl : pr;else if ((q pr.find(h, k, kc)) ! null)return q;elsep pl;} while (p ! null);return null;}/*** 调用 find 查找根节点。*/final TreeNodeK,V getTreeNode(int h, Object k) {return ((parent ! null) ? root() : this).find(h, k, null);}/*** 当 hashCode 相等且不可比较时用于排序插入的平局实用程序。我们不需要全序只需要一致的插入规则来维持重新平衡之间的等效性。超出必要范围的平局打破会稍微简化测试。*/static int tieBreakOrder(Object a, Object b) {int d;if (a null || b null ||(d a.getClass().getName().compareTo(b.getClass().getName())) 0)d (System.identityHashCode(a) System.identityHashCode(b) ?-1 : 1);return d;}/*** 形成从此节点链接的节点树。*/final void treeify(NodeK,V[] tab) {TreeNodeK,V root null;for (TreeNodeK,V x this, next; x ! null; x next) {next (TreeNodeK,V)x.next;x.left x.right null;if (root null) {x.parent null;x.red false;root x;}else {K k x.key;int h x.hash;Class? kc null;for (TreeNodeK,V p root;;) {int dir, ph;K pk p.key;if ((ph p.hash) h)dir -1;else if (ph h)dir 1;else if ((kc null (kc comparableClassFor(k)) null) ||(dir compareComparables(kc, k, pk)) 0)dir tieBreakOrder(k, pk);TreeNodeK,V xp p;if ((p (dir 0) ? p.left : p.right) null) {x.parent xp;if (dir 0)xp.left x;elsexp.right x;root balanceInsertion(root, x);break;}}}}moveRootToFront(tab, root);}/*** 返回替换从此节点链接的非 TreeNode 的列表。*/final NodeK,V untreeify(HashMapK,V map) {NodeK,V hd null, tl null;for (NodeK,V q this; q ! null; q q.next) {NodeK,V p map.replacementNode(q, null);if (tl null)hd p;elsetl.next p;tl p;}return hd;}/***putVal 的树版本。*/final TreeNodeK,V putTreeVal(HashMapK,V map, NodeK,V[] tab,int h, K k, V v) {Class? kc null;boolean searched false;TreeNodeK,V root (parent ! null) ? root() : this;for (TreeNodeK,V p root;;) {int dir, ph; K pk;if ((ph p.hash) h)dir -1;else if (ph h)dir 1;else if ((pk p.key) k || (k ! null k.equals(pk)))return p;else if ((kc null (kc comparableClassFor(k)) null) ||(dir compareComparables(kc, k, pk)) 0) {if (!searched) {TreeNodeK,V q, ch;searched true;if (((ch p.left) ! null (q ch.find(h, k, kc)) ! null) ||((ch p.right) ! null (q ch.find(h, k, kc)) ! null))return q;}dir tieBreakOrder(k, pk);}TreeNodeK,V xp p;if ((p (dir 0) ? p.left : p.right) null) {NodeK,V xpn xp.next;TreeNodeK,V x map.newTreeNode(h, k, v, xpn);if (dir 0)xp.left x;elsexp.right x;xp.next x;x.parent x.prev xp;if (xpn ! null)((TreeNodeK,V)xpn).prev x;moveRootToFront(tab, balanceInsertion(root, x));return null;}}}/**删除此调用之前必须存在的给定节点。这比典型的红黑删除代码更混乱因为我们无法将内部节点的内容与叶子后继者交换该叶子后继者由在遍历期间可独立访问的“下一个”指针固定。因此我们交换树的链接。如果当前树的节点太少则该 bin 会转换回普通 bin。 测试会在 2 到 6 个节点之间触发具体取决于树结构。*/final void removeTreeNode(HashMapK,V map, NodeK,V[] tab,boolean movable) {int n;if (tab null || (n tab.length) 0)return;int index (n - 1) hash;TreeNodeK,V first (TreeNodeK,V)tab[index], root first, rl;TreeNodeK,V succ (TreeNodeK,V)next, pred prev;if (pred null)tab[index] first succ;elsepred.next succ;if (succ ! null)succ.prev pred;if (first null)return;if (root.parent ! null)root root.root();if (root null|| (movable (root.right null|| (rl root.left) null|| rl.left null))) {tab[index] first.untreeify(map); // too smallreturn;}TreeNodeK,V p this, pl left, pr right, replacement;if (pl ! null pr ! null) {TreeNodeK,V s pr, sl;while ((sl s.left) ! null) // find successors sl;boolean c s.red; s.red p.red; p.red c; // swap colorsTreeNodeK,V sr s.right;TreeNodeK,V pp p.parent;if (s pr) { // p was ss direct parentp.parent s;s.right p;}else {TreeNodeK,V sp s.parent;if ((p.parent sp) ! null) {if (s sp.left)sp.left p;elsesp.right p;}if ((s.right pr) ! null)pr.parent s;}p.left null;if ((p.right sr) ! null)sr.parent p;if ((s.left pl) ! null)pl.parent s;if ((s.parent pp) null)root s;else if (p pp.left)pp.left s;elsepp.right s;if (sr ! null)replacement sr;elsereplacement p;}else if (pl ! null)replacement pl;else if (pr ! null)replacement pr;elsereplacement p;if (replacement ! p) {TreeNodeK,V pp replacement.parent p.parent;if (pp null)root replacement;else if (p pp.left)pp.left replacement;elsepp.right replacement;p.left p.right p.parent null;}TreeNodeK,V r p.red ? root : balanceDeletion(root, replacement);if (replacement p) { // detachTreeNodeK,V pp p.parent;p.parent null;if (pp ! null) {if (p pp.left)pp.left null;else if (p pp.right)pp.right null;}}if (movable)moveRootToFront(tab, r);}/*** 调整数组大小的时候调用 进行 取消树化 或者 增高 或者 减低 树的高度*/final void split(HashMapK,V map, NodeK,V[] tab, int index, int bit) {TreeNodeK,V b this;// Relink into lo and hi lists, preserving orderTreeNodeK,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;}}if (loHead ! null) {if (lc UNTREEIFY_THRESHOLD)tab[index] loHead.untreeify(map);else {tab[index] loHead;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);}}}/* ------------------------------------------------------------ */// 红黑树方法static K,V TreeNodeK,V rotateLeft(TreeNodeK,V root,TreeNodeK,V p) {TreeNodeK,V r, pp, rl;if (p ! null (r p.right) ! null) {if ((rl p.right r.left) ! null)rl.parent p;if ((pp r.parent p.parent) null)(root r).red false;else if (pp.left p)pp.left r;elsepp.right r;r.left p;p.parent r;}return root;}static K,V TreeNodeK,V rotateRight(TreeNodeK,V root,TreeNodeK,V p) {TreeNodeK,V l, pp, lr;if (p ! null (l p.left) ! null) {if ((lr p.left l.right) ! null)lr.parent p;if ((pp l.parent p.parent) null)(root l).red false;else if (pp.right p)pp.right l;elsepp.left l;l.right p;p.parent l;}return root;}static K,V TreeNodeK,V balanceInsertion(TreeNodeK,V root,TreeNodeK,V x) {x.red true;for (TreeNodeK,V xp, xpp, xppl, xppr;;) {if ((xp x.parent) null) {x.red false;return x;}else if (!xp.red || (xpp xp.parent) null)return root;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);}}}}}}static K,V TreeNodeK,V balanceDeletion(TreeNodeK,V root,TreeNodeK,V x) {for (TreeNodeK,V xp, xpl, xpr;;) {if (x null || x root)return root;else if ((xp x.parent) null) {x.red false;return x;}else if (x.red) {x.red false;return root;}else if ((xpl xp.left) x) {if ((xpr xp.right) ! null xpr.red) {xpr.red false;xp.red true;root rotateLeft(root, xp);xpr (xp x.parent) null ? null : xp.right;}if (xpr null)x xp;else {TreeNodeK,V sl xpr.left, sr xpr.right;if ((sr null || !sr.red) (sl null || !sl.red)) {xpr.red true;x xp;}else {if (sr null || !sr.red) {if (sl ! null)sl.red false;xpr.red true;root rotateRight(root, xpr);xpr (xp x.parent) null ?null : xp.right;}if (xpr ! null) {xpr.red (xp null) ? false : xp.red;if ((sr xpr.right) ! null)sr.red false;}if (xp ! null) {xp.red false;root rotateLeft(root, xp);}x root;}}}else { // symmetricif (xpl ! null xpl.red) {xpl.red false;xp.red true;root rotateRight(root, xp);xpl (xp x.parent) null ? null : xp.left;}if (xpl null)x xp;else {TreeNodeK,V sl xpl.left, sr xpl.right;if ((sl null || !sl.red) (sr null || !sr.red)) {xpl.red true;x xp;}else {if (sl null || !sl.red) {if (sr ! null)sr.red false;xpl.red true;root rotateLeft(root, xpl);xpl (xp x.parent) null ?null : xp.left;}if (xpl ! null) {xpl.red (xp null) ? false : xp.red;if ((sl xpl.left) ! null)sl.red false;}if (xp ! null) {xp.red false;root rotateRight(root, xp);}x root;}}}}}/*** Recursive invariant check*/static K,V boolean checkInvariants(TreeNodeK,V t) {TreeNodeK,V tp t.parent, tl t.left, tr t.right,tb t.prev, tn (TreeNodeK,V)t.next;if (tb ! null tb.next ! t)return false;if (tn ! null tn.prev ! t)return false;if (tp ! null t ! tp.left t ! tp.right)return false;if (tl ! null (tl.parent ! t || tl.hash t.hash))return false;if (tr ! null (tr.parent ! t || tr.hash t.hash))return false;if (t.red tl ! null tl.red tr ! null tr.red)return false;if (tl ! null !checkInvariants(tl))return false;if (tr ! null !checkInvariants(tr))return false;return true;}
}构造函数
/*** 构造一个具有指定初始容量和负载因子的空HashMap 。*/
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;// loadFactor 0 || loadFactor 是否是一个非 Float型的数值if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);this.loadFactor loadFactor;this.threshold tableSizeFor(initialCapacity);/**疑惑与解答 疑惑为什么不这么写 this.threshold tableSizeFor(initialCapacity) * this.loadFactor;解答在jdk8以后的构造方法中并没有对table这个成员变量进行初始化table的初始化被推迟到了put方法中在put方法中会对threshold重新计算具体见put()*/
}
// 返回给定目标容量的两倍大小的幂。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;}/*** 构造一个具有指定初始容量和默认负载因子 (0.75) 的空HashMap */
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}/*** 使用默认初始容量 (16) 和默认负载因子 (0.75) 构造一个空HashMap 。*/
public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted
}/*** 构造一个与指定Map具有相同映射的新HashMap 。 HashMap是使用默认负载因子 (0.75) 和足以容纳指定Map中的映射的初始容量创建的。*/
public HashMap(Map? extends K, ? extends V m) {this.loadFactor DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}// 实现 Map.putAll 和 Map 构造函数。
final void putMapEntries(Map? extends K, ? extends V m, boolean evict) {int s m.size();if (s 0) {if (table null) { // pre-size 数组值是null 初始化大小float ft ((float)s / loadFactor) 1.0F; int t ((ft (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);if (t threshold)threshold tableSizeFor(t);//取出 t 的最小 2的n次幂}else if (s threshold)resize(); //扩容for (Map.Entry? extends K, ? extends V e : m.entrySet()) {K key e.getKey();V value e.getValue();putVal(hash(key), key, value, false, evict); // 遍历调用 putVal 放值}}} tableSizeFor()方法 可以看到当在实例化HashMap实例时如果给定了initialCapacity(假设是10)由于HashMap的capacity必须都是2的幂因此这个方法用于找到大于等于initialCapacity(假设是10)的最小的2的幂initialCapacity如果就是2的幂则返回的还是这个数。 下面分析这个算法 1 、首先为什么要对cap做减1操作。int n cap - 1; 这是为了防止cap已经是2的幂。如果cap已经是2的幂 又没有执行这个减1操作则执行完后面的几条无符号右移操作之后返回的capacity将是这个cap的2倍。 2、如果n这时为0了经过了cap-1之后则经过后面的几次无符号右移依然是0最后返回的capacity是1最后有个n1的操作。这里只讨论n不等于0的情况。 3、注意|按位或运算运算规则相同的二进制数位上都是0的时候结果为0否则为1。
计算用例int n cap - 1;//cap10 n9
n | n 1;
第1次右移00000000 00000000 00000000 00001001 //9
| 00000000 00000000 00000000 00000100 //9右移之后变为4
-------------------------------------------------00000000 00000000 00000000 00001101 //按位异或之后是13
第2次右移
n | n 2;//n通过第一次右移变为了n1300000000 00000000 00000000 00001101 // 13
|00000000 00000000 00000000 00000011 //13右移之后变为3
-------------------------------------------------00000000 00000000 00000000 00001111 //按位异或之后是15
第3次右移
n | n 4;//n通过第一、二次右移变为了n1500000000 00000000 00000000 00001111 // 15
|00000000 00000000 00000000 00000000 //15右移之后变为0
-------------------------------------------------00000000 00000000 00000000 00001111 //按位异或之后是15
第4、5次右移 还是 15 把已经有的高位中的连续的4个1右移4位再做或操作这样n的二进制表示的高位中正常会有8个连续的1。如00001111 1111xxxxxx 。
以此类推
注意容量最大也就是32 位的正数因此最后n | n 16; 最多也就32个1但是这已经是负数了。在执行tableSizeFor之前对initialCapacity做了判断如果大于MAXIMUM_CAPACITY(2^30)则取MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY(2^30)会执行移位操作。所以这里面的移位操作之后最大30个1不会大于等于MAXIMUM_CAPACITY。30个1加1之后得2^30 。float ft ((float)s / loadFactor) 1.0F;此处 为什么 要加1.0F s/loadFactor的结果是小数加1.0F与(int)ft相当于是对小数做一个向上取整以尽可能的保证更大容量更大的容量能够减少resize的调用次数。所以 1.0F是为了获取更大的容量减少扩容次数提升性能 例如原来集合的元素个数是6个那么6/0.75是8是2的n次幂那么新的数组大小就是8了。然后原来数组的数据就会存储到长度是8的新的数组中了这样会导致在存储元素的时候容量不够还得继续扩容那么性能降低了而如果1呢数组长度直接变为16了这样可以减少数组的扩容。
put
1先通过hash值计算出key映射到哪个桶
2如果桶上没有碰撞冲突则直接插入
3如果出现碰撞冲突了则需要处理冲突
a. 如果该桶使用红黑树处理冲突则调用红黑树的方法插入数据
b.否则采用传统的链式方法插入。如果链的长度达到临界值则把链转变为红黑树
4如果桶中存在重复的键则为该键替换新值value
5如果size大于阈值threshold则进行扩容 // 将指定值与此映射中的指定键相关联。如果映射之前包含键的映射则旧值将被替换。public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}//计算 key.hashCode() 并将散列的高位扩展到低位异或。static final int hash(Object key) {int h;/*1如果key等于null 可以看到当key等于null的时候也是有哈希值的返回的是0.2如果key不等于null 首先计算出key的hashCode赋值给h,然后与h无符号右移16位后的二进制进行按位异或得到最后的hash值*/return (key null) ? 0 : (h key.hashCode()) ^ (h 16); //所以可以存 null/*(h key.hashCode()) ^ (h 16);计算规则就是:1.key.hashCode()返回散列值也就是hashcode。假设随便生成的一个值。2.n表示数组初始化的长度是163.按位与运算运算规则相同的二进制数位上都是1的时候结果为1否则为零。4.^按位异或运算运算规则相同的二进制数位上数字相同结果为0不同为1。*/}
//实现Map.put和相关方法。
/*
主要参数- hash key的hash值- key 原始Key- value 要存放的值- onlyIfAbsent 如果true代表不更改现有的值- evict 如果为false表示table为创建状态
*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i; //map 数组 无值 扩容if ((tab table) null || (n tab.length) 0)n (tab resize()).length;//i (n - 1) hash 规范化 数组长度为 2的n次幂if ((p tab[i (n - 1) hash]) null)/* i (n - 1) hash (n-1) (h key.hashCode()) ^ (h 16) 计算出索引总结简单来说就是高16 bit 不变低16 bit 和高16 bit 做了一个异或得到的 hashcode 转化为32位二进制前16位和后16位 低16bit和高16bit做了一个异或问题为什么要这样操作呢 充分利用高位和低位而不是只利用低位可以减少hash冲突即如果当n即数组长度很小假设是16的话那么n-1即为 15 ---1111 这样的值和hashCode()直接做按位与操作实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大低位变化很小这样就很容易造成哈希冲突了所以这里把高低位都利用起来从而解决了这个问题。其实就是将hashCode值作为数组索引那么如果下个高位hashCode不一致低位一致的话就会造成计算的索引还是10,从而造成了哈希冲突了。降低性能*/// 第一次存储为null ,创建新的节点并把下一个 节点 置为nulltab[i] newNode(hash, key, value, null);else {//走这里表示 该位置出现了 hash 冲突NodeK,V e; K k; // p 表示出现冲突的地方 已有的对象 和现在要 put 的对象的 hash 是不是相等 key 是不是一个key || key ! null key 的内容一样不一样if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p; // e 原来的值else if (p instanceof TreeNode) // 是不是树节点e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else { // 链表形式存储 for (int binCount 0; ; binCount) {// 遍历链表if ((e p.next) null) {//下一个节点是null // e p.next p.next newNode(hash, key, value, null); //尾插法在链表后面加上这个节点 if (binCount TREEIFY_THRESHOLD - 1) // 要是 8 bitcount 0表示第一个节点7表示第八个节点加上数组中的的一个元素所以总共的元素个数是9)treeifyBin(tab, hash);//树化 break; // 停止 for 循环}下一个节点不是 是null
// p 表示出现冲突的地方 已有的对象 和现在要 put 的对象的 hash 是不是相等 key 是不是一个key || key ! null key 的内容一样不一样if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break; // 停止 for 循环p e; // 链表指针 下移}}if (e ! null) { // existing mapping for key V oldValue e.value; // 获取旧的值if (!onlyIfAbsent || oldValue null)e.value value; // 新值对原来的值进行覆盖afterNodeAccess(e); // 回调的钩子函数return oldValue;}}modCount; //修改就 if (size threshold) //满足扩容resize();afterNodeInsertion(evict); // 回调的钩子函数return null;}// 树化
// 替换 bin 中给定哈希索引处的所有链接节点除非表太小在这种情况下会调整大小。final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) // 即使 链表 长度 8 但是 数组长度 64 仍然进行扩容resize();else if ((e tab[index (n - 1) hash]) ! null) { //数组长度 64 TreeNodeK,V hd null, tl null; // hd 头结点 , tl 尾节点//循环的操作就是 将 链表 变为一个 树 do {TreeNodeK,V p replacementTreeNode(e, null);/*TreeNodeK,V replacementTreeNode(NodeK,V p, NodeK,V next) {return new TreeNode(p.hash, p.key, p.value, next);}TreeNode(int hash, K key, V val, NodeK,V next) {super(hash, key, val, next);}*/if (tl null)hd p; // 将新创键的p节点赋值给红黑树的头结点else {/*p.prev tl; 将上一个节点 p 赋值给现在的 p 的前一个节点tl.next p; 将现在节点 p 作为树的尾结点的下一个节点*/p.prev tl;tl.next p;}tl p;/*e e.next 将当前节点的下一个节点赋值给e,如果下一个节点不等于null则回到上面继续取出链表中节点转换为红黑树*/} while ((e e.next) ! null);if ((tab[index] hd) ! null)hd.treeify(tab); // 进行(左旋 右旋 )旋转、平衡等操作转为链表 }}小结
1.根据哈希表中元素个数确定是扩容还是树形化
2.如果 是树形化就遍历桶中的元素创建相同个数的树形节点复制内容建立起联系
3.然后让桶中的第一个元素 指向 新创建的树根节点替换桶的链表内容为树化之后的内容resize
扩容机制 扩容时机 1、*HashMap中的元素个数 数组大小(数组长度)loadFactor(负载因子) 2、当HashMap中的其中一个链表的对象个数如果达到了8个此时如果数组长度没有达到64那么HashMap会先扩容解决如果已经达到了64那么这个链表会变成红黑树节点类型由Node变成TreeNode类型。当然如果映射关系被移除后下次执行resize方法时判断树的节点个数低于6也会再把树还原回链表。 HashMap的扩容是什么 原来的时候每次进行扩容都会伴随着一次 rehash,效率较低现在的话rehash 做了优化 如何优化 因为每次扩容都是翻倍与原来计算的 (n-1)hash的结果相比只是多了一个bit位所以节点要么就在原来的位置要么就被分配到原位置旧容量这个位置所以我们在扩充HashMap的时候不需要 rehash只需要看看原来的 hash 值新增的那个bit是1还是0就可以了是0的话索引没变是1的话索引变成“原索引oldCap(原位置旧容量)”。 好处: 正是因为这样巧妙的rehash方式既省去了重新计算hash值的时间而且同时由于新增的1bit是0还是1可以认为是随机的在resize的过程中保证了rehash之后每个桶上的节点数一定小于等于原来桶上的节点数保证了rehash之后不会出现更严重的hash冲突均匀的把之前的冲突的节点分散到新的桶中了。 final NodeK,V[] resize() {NodeK,V[] oldTab table; // 第一次的时候 旧的数组 null 非第一次oldTab 不是空的int oldCap (oldTab null) ? 0 : oldTab.length;int oldThr threshold; // 第一次的时候 threshold 0 非第一次 根据之前的计算int newCap, newThr 0; //新的数组容量新的边界值// 确定 newCap, newThrif (oldCap 0) {if (oldCap MAXIMUM_CAPACITY) { //2的30次方threshold Integer.MAX_VALUE;return oldTab;}// 新的容量 2 * oldCap 2的30次方 olacap 16else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)// 新的边界值 oldThr * 2newThr oldThr 1; // double threshold}else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY; // 第一次的时候 新的数组的容量默认值 16 newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 第一次的时候 新的边界值 12}if (newThr 0) {float ft (float)newCap * loadFactor;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);}threshold newThr; // threshold 边界值 12SuppressWarnings({rawtypes,unchecked})NodeK,V[] newTab (NodeK,V[])new Node[newCap]; //第一次的时候创建数组Node[16] 非第一次 根据之前的计算Node[newCap]table newTab; // 第一次的时候 table 原来 null ; 现在 newTab 非第一次 table 为 旧的数组if (oldTab ! null) {for (int j 0; j oldCap; j) { // 遍历旧的数组NodeK,V e;if ((e oldTab[j]) ! null) { //旧数据 给 e oldTab[j] null; // 旧数组的位置 置为 null if (e.next null)// 只有数组有元素链表没有元素newTab[e.hash (newCap - 1)] e; //重新计算 hash: e.hash (newCap - 1) 要么是原位置要么是原位置旧容量 将旧数据给新数组的对应位置else if (e instanceof TreeNode) // 是树((TreeNodeK,V)e).split(this, newTab, j, oldCap); // 拆分红黑树else { // preserve order // 是链表NodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next; // 指针下移//e.hash oldCap 计算高位是 1 还是 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);// 移动之后放在指定的位置 要么是原位置要么是原位置旧容量 if (loTail ! null) {loTail.next null;newTab[j] loHead;}if (hiTail ! null) {hiTail.next null;newTab[j oldCap] hiHead;}}}}}return newTab; //第一次的时候 默认16
}remove 首先先找到元素的位置如果是链表就遍历链表找到元素之后删除。如果是用红黑树就遍历树然后找到之后做删除树小于6的时候要转链表。 public V remove(Object key) {NodeK,V e;return (e removeNode(hash(key), key, null, false, true)) null ? null : e.value;
}final NodeK,V removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {NodeK,V[] tab; NodeK,V p; int n, index;// 数组存在 数组长度 0 指定的位置有元素if ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) {NodeK,V node null, e; K k; V v;if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) // 找到对应 key 的元素node p; // 找到的元素 赋值给 node // else if ((e p.next) ! null) { // e p.next e ! null if (p instanceof TreeNode) // 是树的节点就获取红黑树节点node ((TreeNodeK,V)p).getTreeNode(hash, key);else {// 是链表的话就遍历链表节点do {if (e.hash hash ((k e.key) key ||(key ! null key.equals(k)))) {node e;break;}p e; // p 设置为 e } while ((e e.next) ! null);}} // node ! null ( true (matchValue指定为 false) || node 的值是 传入的值 || (值是相等的) )if (node ! null (!matchValue || (v node.value) value || (value ! null value.equals(v)))) {if (node instanceof TreeNode) // 是树的节点就删除树的节点((TreeNodeK,V)node).removeTreeNode(this, tab, movable);else if (node p) // 是链表的节点就删除链表的节点tab[index] node.next;elsep.next node.next;modCount; //修改次数 --size; // 长度 --afterNodeRemoval(node); // 回调钩子函数return node;}}return null;}get get方法实现的步骤 通过hash值获取该key映射到的桶桶上的key就是要查找的key,则直接找到并返回桶上的key不是要找的key,则查看后续的节点 如果后续节点是红黑树节点通过调用红黑树的方法根据key获取value 查找红黑树由于之前添加时已经保证这个树是有序的了因此查找时基本就是折半查找效率更高。这里和插入时一样如果对比节点的哈希值和要查找的哈希值相等就会判断key是否相等相等就直接返回。不相等就从子树中递归查找。 如果后续节点是链表节点则循环遍历链表根据key获取value 若为树则在树中通过key.equals(k)查找O(logn) 若为链表则在链表中通过key.equals(k)查找O(n)。 public V get(Object key) {NodeK,V e;return (e getNode(hash(key), key)) null ? null : e.value;
}final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,V first, e; int n; K k;// tab 不是 null 长度 0 指定的位置有元素 if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {// 找到对应的hash if (first.hash hash ((k first.key) key || (key ! null key.equals(k))))//返回 指定位置的元素 return first;if ((e first.next) ! null) { // e first.next 链表下移if (first instanceof TreeNode) // 是树节点return ((TreeNodeK,V)first).getTreeNode(hash, key); //树的获取方法do { // 循环找到链表的节点if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}return null;}final TreeNodeK,V getTreeNode(int h, Object k) {return ((parent ! null) ? root() : this).find(h, k, null);}final TreeNodeK,V find(int h, Object k, Class? kc) {TreeNodeK,V p this;// 遍历 树节点折半查找do {int ph, dir; K pk;TreeNodeK,V pl p.left, pr p.right, q;if ((ph p.hash) h)p pl;else if (ph h)p pr;else if ((pk p.key) k || (k ! null k.equals(pk)))return p;else if (pl null)p pr;else if (pr null)p pl;else if ((kc ! null ||(kc comparableClassFor(k)) ! null) (dir compareComparables(kc, k, pk)) ! 0)p (dir 0) ? pl : pr;else if ((q pr.find(h, k, kc)) ! null) // 递归调用左右子树return q;elsep pl;} while (p ! null);return null;}
clear public void clear() {NodeK,V[] tab;//修改次数modCount;// 数组存在且有元素if ((tab table) ! null size 0) {//将数组 容量置为 0size 0;// 遍历所有元素全部设置为nullfor (int i 0; i tab.length; i)tab[i] null;}
}面试题 为什么必须是2的n次幂 当向HashMap中添加一个元素的时候需要根据key的hash值去确定其在数组中的具体位置。 HashMap为了存取高效要尽量较少碰撞就是要尽量把数据分配均匀每个链表长度大致相同这个实现就在把数据存到哪个链表中的算法。 这个算法实际就是取模hash%length。所以源码中做了性能优化使用 hash(length-1)而实际上hash%length等于hash(length-1)的前提是length是2的n次幂。 为什么这样能均匀分布减少碰撞呢 总结 是 为了数据的均匀分布减少hash冲突因为 hash冲突越大代表数组中一个链的长度越大这样的话会降低 hashmap 的性能 举例
说明
2的n次方实际就是1后面n个02的n次方-1 实际就是n个11000
- 1
---------------------111按位与运算相同的二进制数位上都是1的时候结果为1否则为零。hash (length-1)
3 (8 - 1) 3 00000011 3 hash00000111 7 length-1
---------------------00000011 3 数组下标
同理 2 (8 - 1) 2
从而减少碰撞如果输入值不是2的幂比如10会怎么样 HashMap通过一通位移运算和或运算得到的肯定是2的幂次数并且是离那个数最近的数字 为什么Map桶中节点个数超过8才转为红黑树 总结: 选择8因为符合泊松分布超过8的时候概率已经非常小了所以我们选择8这个数字。红黑树的平均查找长度是log(n)如果长度为8平均查找长度为log(8)3链表的平均查找长度为n/2当长度为8时平均查找长度为8/24这才有转换成树的必要链表长度如果是小于等于66/23而log(6)2.6虽然速度也很快的但是转化为树结构和生成树的时间并不会太短,而且树还有自旋、变色等操作本质 就是权衡空间和时间的权衡。 因为红黑树节点的大小 大约是链表节点的 两倍所以我们只在bin bin就是bucket(桶)包含足够的节点时才使用树节点。 当它们变得太小(由于删除或调整大小)时就会被转换回普通的桶。在使用分布良好的用户hashcode时很少使用树箱。理想情况下在随机哈希码下箱子中节点的频率服从泊松分布 默认调整阈值为0.75平均参数约为0.5尽管由于调整粒度的差异很大。忽略方差列表大小k的预期出现次数是(exp(-0.5)*pow(0.5, k)/factorial(k))。 第一个值是:0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten millionTreeNodes占用空间是普通Nodes的两倍所以只有当bin包含足够多的节点时才会转成TreeNodes而是否足够多就是由TREEIFY_THRESHOLD 8的值决定的。当bin中节点数变少时又会转成普通的bin。并且我们查看源码的时候发现链表长度达到8就转成红黑树当长度降到6就转成普通bin。
这样就解释了为什么不是一开始就将其转换为TreeNodes而是需要一定节点数才转为TreeNodes说白了就是权衡空间和时间的权衡。 这段内容还说到当hashCode离散性很好的时候树型bin用到的概率非常小因为数据均匀分布在每个bin中几乎不会有bin中链表长度会达到阈值。但是在随机hashCode下离散性可能会变差然而JDK又不能阻止用户实现这种不好的hash算法因此就可能导致不均匀的数据分布。不过理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布我们可以看到一个bin中链表长度达到8个元素的概率为0.00000006几乎是不可能事件。所以之所以选择8不是随便决定的而是根据概率统计决定的。由此可见发展将近30年的Java每一项改动和优化都是非常严谨和科学的。 为什么要选择 0.75 loadFactor 太大导致查找元素效率低虽然size 达到了 loadfactor 的值但是每个数组下挂载的链表个数有可能很多太小导致数组的利用率低存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值 loadFactor 越趋近于1那么 数组中存放的数据(entry)也就越多也就越密也就是会让链表的长度增加loadFactor越小也就是趋近于0数组中存放的数据(entry)也就越少也就越稀疏。 注意尽可能减少扩容次数因为 扩容这个过程涉及到 rehash、复制数据等操作非常消耗性能可以通过创建HashMap集合对象时指定初始容量来尽量避免 HashMap中容量的初始化的值的建议是多少 initialCapacity需要存储的元素个数/负载因子)1 【注意负载因子即loaderfactor)默认为0.75】 建议可以把默认容量的数字设置成**initialCapacity/ 0.75F 1.0F**
总结 1.8 之前直接创建 Entry 数组1.8之后 调用 put() 的 时候才会创建 Node 数组 put 的 时候 经过 hash 运算得到数组的索引下标此处是结合数组长度进行 ^要是对应的位置为空 直接插入。要是对应的位置有数据但是 hash不一样就创建一个链表节点存储到链表节点上。 hash 值一样【此时称为 hash冲突】调用key的 equals() 函数比较是不是一样的不一样继续添加链表/ 树一样进行覆盖。 使用红黑树的原因 提升查询效率 链表中的时间复杂度O(n),但是红黑树的时间复杂度O(log(n)) 为什么一定要是2 的幂次方源码中 解决 哈希冲突的做法 是将 计算的 hash 值与数组的长度-1进行与运算就是等价于 取模 数组长度的运算。但是进行与运算的效率更高所以一定要是2 的幂次方 与其说是扩容的条件不如说是 进行与运算的条件就是为了让数据分布均匀减少哈希冲突提升效率。 数组在初始化的时候给定了指定的值要是不是2的幂次方那么会自动扩容为最接近给定值的2 的幂次方 阈值为什么是8 1、源码上的解释是因为 符合 泊松分布概率统计的结果决定的 2、站在 效率的角度看log(n) 在n8 的时候树的效率更高 不进行树化的时候转为链表时的阈值为什么是6 还是从效率考虑虽然此时 链表和数的效率差不多但是 树会多了 自旋、变色等步骤 是会降低效率的而且一个树的节点 所占用的空间是链表节点的两倍。 所以上面的两个阈值这么设置的原因就是 效率。权衡时间和空间。 为什么加载因子是 0.75 过大会导致效率降低过小 会导致数组的利用率降低频繁造成扩容、复制的操作 hashMap 的容量的初始值建议设置为initialCapacity需要存储的元素个数/负载因子)1 此处的 1 的作用实际上是对计算出来的小数进行取整扩大容量防止处于临界状态的之后立刻扩容的现象发生。减少扩容的次数提升性能。反例要是不加1此时数组的实际长度是 6 此时应该的初始值是8但是很容易就会导致出现扩容的情况所以此时就需要进行1,之后的数组会扩容到16就可以减少初始化之后立马又扩容的状况了。 Hashmap 的扩容是怎么进行优化的因为扩容每次都是翻倍的所有再重新hash 计算 (n-1)hash的时候就会比原来多一个bit位所以节点要么就是原来的位置要么就是 原来的容量 原来的位置所以 在扩充HashMap的时候不需要 rehash只需要看看原来的 hash 值新增的那个bit是1还是0就可以了是0的话索引没变是1的话索引变成“原索引oldCap(原位置旧容量)”
