简介：
- 是基于 哈希表 实现的，存放 k-v 键值对，非同步的方式（未加 synchronized ）非线程安全的，hashmap 无序的
- 数据结构： 数组 + 链表 ====> 数组 +链表 + 红黑树「链表 和 链表 + 红黑树 都是为了解决 哈希冲突
- 哈希冲突： 两个对象调用的
hashCode方法计算的哈希码值一致导致计算的数组索引值相同 ,区别是： 链表 + 红黑树 在达到 ： 阈值> 8 && 数组长度 > 64 才会进行转为红黑树———>原因： 虽然红黑树会让结构更加复杂，但是这时查询效率更高，要是数组长度比较少的话，应该尽量避免红黑树，不然的话红黑树需要进行左旋，右旋，变色这些操作来保持平衡并且 数组的长度 < 64 的时候 搜索的时间是相对来说比较快的」
数据结构：
存储说明：
-
HashMap<String,Integer>map = 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位做异或运算效率是比较高的
- 面试题：HashMap中
-
假设向哈希表中存储
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 ，就转为红黑树存储
- 进一步比较通过equals比较
- 会产生哈希碰撞
-
红黑树结构复杂，为什么使用红黑树？为什么阈值规定为 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之前数组类型是Entry<K,V>类型。从jdk1.8之后是Node<K,V>类型。只是换了个名字，都实现了一样的接口：Map.Entry<K,V>。负责存储键值对数据的。
transient Node<K,V>[] table;
//存放具体的元素的集合 和 缓存
transient Set<Map.Entry<K,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 Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,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 TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* 返回包含此节点的树的根。
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
/**
* 确保给定的根是其 bin 的第一个节点。
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,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 TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,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;
else
p = pl;
} while (p != null);
return null;
}
/**
* 调用 find 查找根节点。
*/
final TreeNode<K,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(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,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 (TreeNode<K,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);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
/**
* 返回替换从此节点链接的非 TreeNode 的列表。
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
/**
*putVal 的树版本。
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,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) {
TreeNode<K,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);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
/**
删除此调用之前必须存在的给定节点。
这比典型的红黑删除代码更混乱，因为我们无法将内部节点的内容与叶子后继者交换，该叶子后继者由在遍历期间可独立访问的“下一个”指针固定。
因此，我们交换树的链接。如果当前树的节点太少，则该 bin 会转换回普通 bin。 （测试会在 2 到 6 个节点之间触发，具体取决于树结构）。
*/
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null)
tab[index] = first = succ;
else
pred.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 small
return;
}
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
while ((sl = s.left) != null) // find successor
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.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;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
TreeNode<K,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(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.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> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,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;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,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;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,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> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
for (TreeNode<K,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 {
TreeNode<K,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 { // symmetric
if (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 {
TreeNode<K,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(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,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（最后有个n+1的操作）。这里只讨论n不等于0的情况。
3）、注意：|（按位或运算）：运算规则：相同的二进制数位上，都是0的时候，结果为0，否则为1。
计算用例：
int n = cap - 1;//cap=10 n=9
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通过第一次右移变为了：n=13
00000000 00000000 00000000 00001101 // 13
|
00000000 00000000 00000000 00000011 //13右移之后变为3
-------------------------------------------------
00000000 00000000 00000000 00001111 //按位异或之后是15
第3次右移
n |= n >>> 4;//n通过第一、二次右移变为了：n=15
00000000 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.0Fs/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表示数组初始化的长度是16
3.&（按位与运算）：运算规则：相同的二进制数位上，都是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) {
Node<K,V>[] tab; Node<K,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 ,创建新的节点，并把下一个 节点 置为null
tab[i] = newNode(hash, key, value, null);
else {
//走这里表示 该位置出现了 hash 冲突
Node<K,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 = ((TreeNode<K,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(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // 即使 链表 长度 > 8 但是 数组长度 < 64 仍然进行扩容
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) { //数组长度 >= 64
TreeNode<K,V> hd = null, tl = null; // hd 头结点 , tl = 尾节点
//循环的操作就是 将 链表 变为一个 树
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
/*
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
TreeNode(int hash, K key, V val, Node<K,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 Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 第一次的时候 旧的数组 = null 非第一次，oldTab 不是空的
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold; // 第一次的时候 threshold = 0 非第一次， 根据之前的计算
int newCap, newThr = 0; //新的数组容量，新的边界值
// 确定 newCap, newThr
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { //2的30次方
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新的容量 2 * oldCap < 2的30次方 && olacap >= 16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新的边界值 = oldThr * 2
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = 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 边界值 12
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //第一次的时候创建数组Node[16] 非第一次， 根据之前的计算Node[newCap]
table = newTab; // 第一次的时候 table 原来 null ; 现在 newTab 非第一次， table 为 旧的数组
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { // 遍历旧的数组
Node<K,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) // 是树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 拆分红黑树
else { // preserve order // 是链表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next; // 指针下移
//e.hash & oldCap 计算高位是 1 还是 0 ，
if ((e.hash & oldCap) == 0) {
//进行移动操作
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//进行移动操作
else {
if (hiTail == null)
hiHead = e;
else
hiTail.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) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 数组存在 数组长度 > 0 指定的位置有元素
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
Node<K,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 = ((TreeNode<K,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) // 是树的节点，就删除树的节点
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) // 是链表的节点，就删除链表的节点
tab[index] = node.next;
else
p.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) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,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 ((TreeNode<K,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 TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
// 遍历 树节点，折半查找
do {
int ph, dir; K pk;
TreeNode<K,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;
else
p = pl;
} while (p != null);
return null;
}
clear
public void clear() {
Node<K,V>[] tab;
//修改次数++
modCount++;
// 数组存在且有元素
if ((tab = table) != null && size > 0) {
//将数组 容量置为 0
size = 0;
// 遍历所有元素，全部设置为null
for (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个0，2的n次方-1 实际就是n个1； 1000 - 1 --------------------- 111 按位与运算：相同的二进制数位上，都是1的时候，结果为1，否则为零。 hash & (length-1) 3 & (8 - 1) = 3 00000011 3 hash & 00000111 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/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，而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 million
TreeNodes占用空间是普通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) 在n>8 的时候树的效率更高
不进行树化的时候，转为链表时的阈值为什么是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(原位置+旧容量)”
扩展— HashSet
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
...
// 构造器
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
...
public boolean contains(Object o) {
return map.containsKey(o);
}
}
可以看到，在HashSet中底层主要用的还是 HashMap 中的方法，其中主要的细节变化是：
1.只是在add(E e)的时候会调用map.put(),此map的put的键值对分别是：k:e；V:PRESENT（private static final Object PRESENT = new Object();）
2.同样的删除方法remove(Object o):会调用map.remove(o),随后判断删除之后返回的结果和PRESENT是不是相等来决定是不是删除成功
add(E e)
如果指定元素尚不存在，则将其添加到该集合中。更正式地说，如果该集合不包含满足(e==null ? e2==null : e.equals(e2)) 的元素e2 ，则将指定元素e添加到该集合中。如果该集合已包含该元素，则调用将保持该集合不变并返回false 。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
remove(Object o)
从此集合中删除指定元素（如果存在）。更正式地说，如果该集合包含这样的元素，则删除(o==null ? e==null : o.equals(e))的元素 e 。如果此集合包含该元素（或者等效地，如果此集合因调用而发生更改），则返回true 。 （一旦调用返回，该集合将不再包含该元素。）
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
去重逻辑的体现
因为 map 的key 是唯一的，HashSet 在添加元素add 的时候只需要参数key（存储的元素）,所以遇到重复的元素就直接覆盖，从而导致HashSet中的元素是唯一的
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/180227.html
