散列表-HashMap
JDK1.8的哈希冲突解决方案
image-20210624173249774
思考:这里为什么使用单链表?
- 每次都是从头节点开始遍历
- 单向链表比双向链表少一个指针，可以节省内存空间
哈希函数(Hash)
image-20210624173510720
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
// 先获取到key的hashCode，然后进行移位再进行异或运算，为什么这么复杂，不用想肯定是为了减少hash冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
image-20210624210952044
这个方法非常巧妙，它总是通过 h &(table.length -1) 来得到该对象的保存位置，而 HashMap 底层数组的长度总是 2 的 n 次方。当 length 总是 2 的倍数时，h & (length-1)
- 假设 h=5,length=16, 那么 h & length - 1 将得到 5；
- 假设 h=6,length=16, 那么 h & length - 1 将得到 6
良好的哈希函数
- 让哈希值更加均匀分布→减少哈希冲突次数→提升哈希表的性能
image-20210624175023006
在Java中，HashMap的key必须实现hashCode、 equals方法，也允许key为null
Integer的哈希值
@Override
public int hashCode() {
return Integer.hashCode(value);
}
/**
* Returns a hash code for a {@code int} value; compatible with
* {@code Integer.hashCode()}.
*
* @param value the value to hash
* @since 1.8
*
* @return a hash code value for a {@code int} value.
*/
public static int hashCode(int value) {
return value;
}
Float的哈希值
/**
* Returns a hash code for this {@code Float} object. The
* result is the integer bit representation, exactly as produced
* by the method {@link #floatToIntBits(float)}, of the primitive
* {@code float} value represented by this {@code Float}
* object.
*
* @return a hash code value for this object.
*/
@Override
public int hashCode() {
return Float.hashCode(value);
}
/**
* Returns a hash code for a {@code float} value; compatible with
* {@code Float.hashCode()}.
*
* @param value the value to hash
* @return a hash code value for a {@code float} value.
* @since 1.8
*/
public static int hashCode(float value) {
return floatToIntBits(value);
}
Long的哈希值
@Override
public int hashCode() {
return Long.hashCode(value);
}
/**
* Returns a hash code for a {@code long} value; compatible with
* {@code Long.hashCode()}.
*
* @param value the value to hash
* @return a hash code value for a {@code long} value.
* @since 1.8
*/
public static int hashCode(long value) {
return (int)(value ^ (value >>> 32));
}
Double的哈希值
@Override
public int hashCode() {
return Double.hashCode(value);
}
/**
* Returns a hash code for a {@code double} value; compatible with
* {@code Double.hashCode()}.
*
* @param value the value to hash
* @return a hash code value for a {@code double} value.
* @since 1.8
*/
public static int hashCode(double value) {
long bits = doubleToLongBits(value);
return (int)(bits ^ (bits >>> 32));
}
image-20210624180113532
字符串(String)的哈希值
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
image-20210624181045755
image-20210624181345366
JDK1.8版本-HashMap源码分析
属性默认值
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//序列号，序列化的时候使用
private static final long serialVersionUID = 362498820763181265L;
//默认容量，为2的4次方,即为16, 必须为 2 的 n 次方 (一定是合数)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量，为2的30次方。
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子，用于扩容使用。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表转成红黑树的阈值。即在哈希表扩容时，当链表的长度(桶中元素个数)超过这个值的时候，进行链表到红黑树的转变
static final int TREEIFY_THRESHOLD = 8;
//红黑树转为链表的阈值。即在哈希表扩容时，如果发现链表长度(桶中元素个数)小于 6，则会由红黑树重新退化为链表
static final int UNTREEIFY_THRESHOLD = 6;
//当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。
//HashMap 的最小树形化容量。这个值的意义是：位桶（bin）处的数
//据要采用红黑树结构进行存储时，整个Table的最小容量（存储方式由
//链表转成红黑树的容量的最小阈值） 当哈希表中的容量大于这个值
//时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，而不是
// 树形化为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 *
// TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
}
属性参数
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
transient Node<K,V>[] table;
//将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。
transient Set<Map.Entry<K,V>> entrySet;
//元素数量
transient int size;
//统计该map修改的次数，用来记录 HashMap 内部结构发生变化的次数，主要用于迭代的快速失败机制
transient int modCount;
//HashMap 的门限阀值/扩容阈值，所能容纳的 key-value 键值对极 //
// 限，当size>=threshold时，就会扩容，计算方法：容量capacity * 负载因子load factor 。
int threshold;
//加载因子
final float loadFactor;
}
Node[] table：的初始化长度 length(默认值是 16)，loadFactor 为负载因子 (默认值 DEFAULT_LOAD_FACTOR 是 0.75)，threshold 是 HashMap 所能容纳的最大数据量的 Node(键值对) 个数。
threshold = length * loadFactor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
这里我们需要加载因子 (load_factor)，加载因子默认为 0.75，当 HashMap 中存储的元素的数量大于 (容量 × 加载因子)，也就是默认大于 16*0.75=12 时，HashMap 会进行扩容的操作。
size：这个字段其实很好理解，就是HashMap中实际存在的键值对数量。注意和 table 的长度 length、容纳最大键值对数量 threshold 的区别。
modCount：字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化。
put新键值对，某个key对应的value值被覆盖不属于结构变化。
HashMap构造函数
HashMap的构造方法有4种，主要涉及到的参数有，指定初始容量，指定填充比和用来初始化的Map
//构造函数1(带有初始容量和加载因子的有参构造函数)
public HashMap(int initialCapacity, float loadFactor) {
//指定的初始容量非负
if (initialCapacity < 0)
throw new IllegalArgumentException(Illegal initial capacity: +
initialCapacity);
//如果指定的初始容量大于最大容量,置为最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//填充比为正
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException(Illegal load factor: +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);//新的扩容临界值
}
//构造函数2(只带有初始容量的构造函数)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造函数3(无参构造函数)
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//构造函数4(用m的元素初始化散列映射)
public HashMap(Map<!--? extends K, ? extends V--> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
添加元素
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table为空或者length=0时，以默认大小扩容，n为table的长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算index，并对null做处理，table[i]==null
if ((p = tab[i = (n - 1) & hash]) == null)
// (n-1)&hash 与Java7中indexFor方法的实现相同，若i位置上的值为空，则新建一个Node，table[i]指向该Node。
// 直接插入
tab[i] = newNode(hash, key, value, null);
else {
// 若i位置上的值不为空，判断当前位置上的Node p 是否与要插入的key的hash和key相同
Node<K,V> e; K k;
// 若节点key存在，直接覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判断table[i]该链是否是红黑树，如果是红黑树，则直接在树中插入键值对
else if (p instanceof TreeNode)
// 不同，且当前位置上的的node p已经是TreeNode的实例，则再该树上插入新的node
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// table[i]该链是普通链表，进行链表的插入操作
else {
// 在i位置上的链表中找到p.next为null的位置，binCount计算出当前链表的长度，如果继续将冲突的节点插入到该链表中，会使链表的长度大于tree化的阈值，则将链表转换成tree。
for (int binCount = 0; ; ++binCount) {
// 如果遍历到了最后一个节点，说明没有匹配的key，则创建一个新的节点并添加到最后
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表长度大于8转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 遍历过程中若发现 key 已经存在直接覆盖 value 并跳出循环即可
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 已经存在该key的情况时，将对应的节点的value设置为新的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold，如果超过，进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
红黑树结构的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;
}
}
}
总结 put()方法大致的思路为：
- 对key的hashCode()做hash，然后再计算 index;
- 如果没碰撞直接放到 bucket里；
- 如果碰撞了，以链表的形式存在 buckets 后；
- 如果碰撞导致链表过长 (大于等于 TREEIFY_THRESHOLD=8)，就把链表转换成红黑树；
- 如果节点已经存在就替换 old value(保证 key 的唯一性)
- 如果 bucket 满了 (超过 load factor*current capacity)，就要 resize。
JDK1.8使用红黑树的改进
在java jdk8中对HashMap的源码进行了优化。在jdk8中，HashMap处理“碰撞”增加了红黑树这种数据结构，当碰撞结点较少时，采用链表存储，当较大时（>8个），采用红黑树。
我们都知道，链表的时间复杂度是O(n)，红黑树的时间复杂度O(logn)，很显然，红黑树的复杂度是优于链表的。
那为什么hashmap不直接使用红黑树呢？
从时间复杂度来分析，红黑树的平均查找长度是log(n)，如果长度为8，平均查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，而log(6)=2.6，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 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
从具体源码中来分析：源码中的注释写的很清楚，因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树，说白了就是trade-off，空间和时间的权衡。
HasMap的扩容机制resize();
前面多次提到的负载因子：源码中有个公式为threshold = loadFactor * 容量。HashMap和HashSet都允许你指定负载因子的构造器，表示当负载情况达到负载因子水平的时候，容器会自动扩容，HashMap默认使用的负载因子值为0.75f（当容量达到四分之三进行再散列（扩容））。当负载因子越大的时候能够容纳的键值对就越多但是查找的代价也会越高。所以如果你知道将要在HashMap中存储多少数据，那么你可以创建一个具有恰当大小的初始容量这可以减少扩容时候的开销。但是大多数情况下0.75在时间跟空间代价上达到了平衡所以不建议修改。
resize() 函数会在两种情况下被调用：
(1) HashMap new 出来后还没有 put 元素进去，没有真正分配存储空间被初始化，调用 resize() 函数进行初始化；
(2) 原 table 中的元素个数达到了 capacity * loadFactor 这个上限，需要扩容。此时调用 resize()，new 一个两倍长度的新 Node 数组，进行rehash，并将容器指针（table）指向新数组。
边也可以引申到一个问题HashMap是先插入还是先扩容：HashMap初始化后首次插入数据时，先发生resize扩容再插入数据，之后每当插入的数据个数达到threshold时就会发生resize，此时是先插入数据再resize。
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,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;
}
/*把新表的长度设置为旧表长度的两倍，newCap=2*oldCap*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
/*把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/
newThr = oldThr << 1; // double threshold
}
/*如果旧表的长度的是0，就是说第一次初始化表*/
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;//新表长度乘以加载因子
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
/*下面开始构造新表，初始化表中的数据*/
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;//把新表赋值给table
if (oldTab != null) {//原表不是空要把原表中数据移动到新表中
/*遍历原来的旧表*/
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
/*如果e后边有链表,到这里表示e后面带着个单链表，需要遍历单链表，将每个结点重*/
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为偶数一队，e.hash&oldCap为奇数一对
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) {//lo队不为null，放在新表原位置
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {//hi队不为null，放在新表j+oldCap位置
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
网友评论