Hash碰撞的解决方式
- 提起存储键值对,首先想到的是Map集合,但是对于hash算法导致的hash碰撞,一般有两种解决方式: 链表法跟开放地址法, 对于Android应用开发来说,正好对应着HashMap跟ArrayMap的解决方式
ArrayMap: 开放地址法
- 笔者在使用Retrofit请求网络时由于需要将数据封装成map集合发送给后端,但是一般都是提交数据量很小的内容,因此使用ArrayMap替换HashMap已节约内存空间.这里通过源码分析两者之间的差别
- 首先查看构造函数
1 | ini复制代码 public ArrayMap() { |
- 搞懂几个数据含义
- ArrayMap是由两个数组构成的 mHashes 和 mArray
- mHashes : 由键的Hash值根据大小有序的数组 mHashes [key1.hash , key2.hash , ….],(key1.hash跟key2.hash完全可以相等,这个没关系的)
- mArray: 键值对依次排列的数组 mArray[key1, value1, key2, value2 ….]
- 查看 put()方法
1 | scss复制代码 @Override |
- 初始化数组函数 allocArrays(capacity)用于数组的初始化及缓存数据
- 看这个缓存函数需要搞懂一个数组扩容大小改变关系(在put函数中BASE_SIZE = 4)
1 | ini复制代码final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1)) |
- 默认值为 4 ,第一次扩容为 4 * 2 = 8 , 以后每次扩容为增加当前值得 1/2 倍.即下次为 12 ->18 …
1 | ini复制代码 private void allocArrays(final int size) { |
- 对于查找indexOf(key,hash)
1 | arduino复制代码 |
- remove 方法:
- 在某种条件下，会重新分配内存，保证分配给ArrayMap的内存在合理区间，减少对内存的占用。但是如果每次remove都重新分配空间，会浪费大量的时间。
- 因此在此处，Android使用的是用空间换时间的方式，以避免效率低下。无论从任何角度，频繁的分配回收内存一定会耗费时间的。
1 | ini复制代码public V removeAt(int index) { |
- 重点关注缓存 freeArrays(final int[] hashes, final Object[] array, final int size) , 结合 allocArrays(int size)同看
- 注意参数的内容 : hashes 跟 array的长度关系是 1/ 2 , 切记切记啊
1 | ini复制代码 private static void freeArrays(final int[] hashes, final Object[] array, final int size) { |
- 再次查看 allocArrays
1 | ini复制代码 |
- 缓存数据图如下
- 特别解释,为何最大缓存数据是10层:
- 没有注意几个数据情况 :几个缓存数据及他们的长度均是静态成员变量,也就是他们是跟类一致而跟对象无关,所以是所有的ArrayMap对象共用的,不管你创建多少ArrayMap都将共用这最多10个缓存池,相当于线程池一样儿的
1 | dart复制代码static Object[] mBaseCache; |
SparseArray
- 同ArrayMap一样是由两个数组构成的,不同的是他并不是map集合
1 | java复制代码//成员变量分析 |
- 存储put
1 | ini复制代码public void put(int key, E value) { |
- put步骤:
- 如果当前i位置根据二分查找找到了,则替换原来值为value新值
- 如果当前i不存在,则找到第一个大于i的位置标示插入位置,此时有两种情况,1该位置设置为Deleted则直接插入即可,否则判断是否已满且有被标记Deleted的位置,通过GC移动数组,将deleted位置处删除则可正常的插入了
- 如果数组满了,且没有Deleted标志,则需要2倍的扩容数组后在插入啦!
- 这里的gc比较有意思,可以看一下,使用双指针移动删除数组中被标记为Deleted
1 | ini复制代码private void gc() { |
- get和delete函数都很简单,这里只贴出来,标记为Deleted即可,不用真正的去移动数组,提高效率
1 | ini复制代码public E get(int key, E valueIfKeyNotFound) { |
HashMap
- 对于大数据量的存储还是推荐使用HashMap,因为ArrayMap如果大量数据插入时需要时间复杂度O(n),而使用hashMap最坏时间复杂度O(logn,都在一个红黑树下),平均时间复杂度O(1),主要看数据量来换算是否已时间换取空间对于很多算法选择无非就是时间跟空间两者的平衡
- 数据结构为:HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体;
* 根据使用场景设置初始容量及负载因子
* hashMap实现了Map接口,使用键值对进行映射,map中不允许出现重复的键(key)
* Map接口分为两类:TreeMap跟HashMap
+ TreeMap保存了对象的排列次序,hashMap不能
+ HashMap可以有空的键值对(null-null),是非线程安全的,但是可以调用collections的静态方法synchronizeMap()实现
* HashMap中使用键对象来计算hashcode值
* HashMap比较快，因为是使用唯一的键来获取对象- 源码解析:
1 | ini复制代码final V putVal(int hash, K key, V value, boolean onlyIfAbsent, |
1. 通过源码我们可以得出:
1. 当我们往HashMap中put元素的时候,先根据key的hashCode重新计算hash值,根据hash值得到元素在数组中的下标,(hash值计算 = 32位hash的 hash值 ^ 高16位后再 & 上 length -1 )
1. 如果数组该位置已经存放有其他元素,则在这个位置上以链表的形式存放,新加入的放在链头,最后加入的放在链尾,如果链表中有相应的key则替换value值为最新的并返回旧值;
2. 如果该位置上没有其他元素,就直接将该位置放在此数组中的该位置上;
3. 我们希望HashMap里面的元素位置尽量的分布均匀写,使得每个位置上的元素只有一个,这样当使用hash算法得到这个位置的时候,马上就可以知道对应位置的元素就是我们要的,不用再遍历链表,这样就大大优化了查询效率;
4. 计算hash值的方法hash(int h),理论上是对数组长度取模运算 % ,但是消耗比较大,源代码调用为:
1
2
3
4
5
6
7
8
9
10
11
12
13
arduino复制代码 /**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1); //HashMap底层数组长度总是2的n次方,每次扩容为2倍
}
//Map数组初始化取值:
//当 length 总是 2 的 n 次方时，h& (length-1)运算等价于对 length 取模，也就是 h%length，但是 & 比 % 具有更高的效率。
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1; //每次增加2倍,所以总长度一定为2的次方
1. 为何hash码初始化为2的次方数探讨:
分析:
1. 当它们和 15-1（1110）“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8 和 9 会被放到数组中的同一个位置上形成链表，那么查询的时候就需要遍历这个链 表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为 15 的时候，hash 值会与 15-1（1110）进行“与”，那么最后一位永远是 0，而 0001，0011，0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！
2. 而当数组长度为16时，即为2的n次方时，2n-1 得到的二进制数的每个位上的值都为 1，这使得在低位上&时，得到的和原 hash 的低位相同，加之 hash(int h)方法对 key 的 hashCode 的进一步优化，加入了高位计算，就使得只有相同的 hash 值的两个值才会被放到数组中的同一个位置上形成链表。
3. 当数组长度为 2 的 n 次幂的时候，不同的 key 算得得 index 相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了
* **总结:** 根据上面 put 方法的源代码可以看出，当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。
2. HashMap的扩容机制
1. 什么时候扩容: 达到阈值,数组大小 \* 加载因子默认16\* 0.75 = 12个
2. JDK 1.7没有引入红黑树,使用数组加上链表,JDK1.8引入红黑树,使用数组+链表+红黑树存储,当链表值大于等于8转化为红黑树,当remove时红黑树大小小于等于6时会转化为链表,设置一个过渡值7防止不停地put,remove导致不听转化而使得效率低下;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
scss复制代码if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD) //6
tab[index] = loHead.untreeify(map); //将红黑树转化成链表
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
```#### 归纳HashMap
1. **简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据 hash 算法来决定其在数组中的存储位置，在根据 equals 方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry 时，也会根据 hash 算法找到其在数组中的存储位置，再根据 equals 方法从该位置上的链表中取出该Entry。**
2. 初始化HashMap默认值为16, 初始化时可以指定initial capacity，若不是2的次方，HashMap将选取第一个大于initial capacity 的2n次方值作为其初始长度 ;
3. 初始化负载因子为0.75,如果超过16 \* 0.75 = 12个数据就会将数组扩容为2倍 长度为32 , 并后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作,如果我们已经预知 HashMap 中元素的个数，那么预设元素的个数能够有效的提高 HashMap 的性能。 如果负载印在越大,对空间利用越充分,但是会降低查询效率,如果负载因子越小,则散列表过于稀疏,对空间造成浪费(时间<-> 空间转换: 0.75最佳)
4. 多线程中的检测机制:Fail-Fast,通过标记modCount(使用volatile修饰,保证线程间修改的可见性) 域 修改次数,在迭代初始化时候赋值,以后每次next的时候都会判断是否相等
scss复制代码HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
1
2
3
4
5
6
7
5. 建议使用concurrent HashMap在多线程中
6. Map的遍历,
1. 使用entrySet获取键值对的Entry集合,只需要遍历一次
2. 使用keySet先遍历所有的键,在根据键调取get(key),需要遍历两次
3. JDK1,8以上新增forEach()遍历,先遍历hash表,如果是链表结构遍历后再遍历下一个hash值的链表
ini复制代码public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
// Android-changed: Detect changes to modCount early.
for (int i = 0; (i < tab.length && modCount == mc); ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
Map map = new HashMap();
iter 1
2
3
4
5
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
复制代码
1 |
|
ini复制代码void transfer(Entry[] newTable) {
Entry[] src = table; //旧的hash表
int newCapacity = newTable.length;
//下面这段代码的意思是：
// 从OldTable里摘一个元素出来，然后放到NewTable中
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next; //注意添加顺序,是由头部开始添加,这个地方会导致循环的产生,加入线程A执行完毕挂起了,此时e = 3 , next = 7 , 3.next = 7的
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
1 |
|
ini复制代码public synchronized V put(K key, V value) {
// Make sure the value is not null确保value不为null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
//确保key不在hashtable中
//首先，通过hash方法计算key的哈希值，并计算得出index值，确定其在table[]中的位置
//其次，迭代index索引位置的链表，如果该位置处的链表存在相同的key，则替换value，返回旧的value
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
//如果超过阀值，就进行rehash操作
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
//将值插入，返回的为null
Entry<K,V> e = tab[index];
// 创建新的Entry节点，并将新的Entry插入Hashtable的index位置，并设置e为新的Entry的下一个元素
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}1 |
|
ini复制代码 private void deleteEntry(TreeMapEntry<K,V> p) {
modCount++;
size–;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) { //对应第一种情况,左,右子树均不为Nul
TreeMapEntry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // 没有返回,将第一种情况转化成了 2,3,4 种情况
// Start fixup at replacement node, if it exists.
TreeMapEntry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) { //对应于2,3中情况,左,右子树有一个为Nul
// Link replacement to parent
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // 第四种情况,左右子树均为Nul
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}}
* 以上可以至源码中查看算法实现细节，如有不当之处，欢迎给予评论指正！
**本文转载自:** [掘金](https://juejin.cn/post/6971252098369323022)
*[开发者博客 – 和开发相关的 这里全都有](https://dev.newban.cn/)*