HashMap源码

2018-12-03  本文已影响0人  Ary_zz

java.util.HashMap

image.png 
public class HashMap<K, V> extends AbstractMap implements Map<K, V>, Cloneable, Serializable

本质是一个Entry[]数组（哈希桶数组），用Key的哈希值对桶数组size取模可得到数组下标。若数组下标碰撞，进化为链表或红黑树。

使用

构造函数

    HashMap map = new HashMap();

常用方法

    HashMap<String, Integer> map = new HashMap();
    map.put("ary", 1);
    map.get("ary");
    Set<Map.Entry<String, Integer>> entrySet = map.entrySet();

Lambda用法

    map.merge("ary", 1, (oldValue, newValue) -> oldValue + newValue);
    map.compute("ary", (k, v) -> v + 1);

摘要

  1. HashMap 是一个关联数组、哈希表，线程不安全的，遍历时无序。
  2. 其底层数据结构是数组称之为哈希桶，每个桶里面放的是链表，链表中的每个节点，就是哈希表中的每个元素。
  3. 在JDK8中，当链表长度达到8，会转化成红黑树，以提升它的查询、插入效率，它实现了Map<K,V>, Cloneable, Serializable接口。

因其底层哈希桶的数据结构是数组，所以也会涉及到扩容的问题。
当HashMap的容量达到threshold域值时，就会触发扩容。扩容前后，哈希桶的长度一定会是2的次方。
这样在根据key的hash值寻找对应的哈希桶时，可以用位运算替代取余操作，更加高效。
在扩容中只用判断原来的 hash 值与左移动的一位（newtable 的值）按位与操作是 0 或 1 就行，0 的话索引就不变，1 的话索引变成原索引加上扩容前数组

而key的hash值，并不仅仅只是key对象的hashCode()方法的返回值，还会经过扰动函数的扰动，以使hash值更加均衡。
因为hashCode()是int类型，取值范围是40多亿，只要哈希函数映射的比较均匀松散，碰撞几率是很小的。
但就算原本的hashCode()取得很好，每个key的hashCode()不同，但是由于HashMap的哈希桶的长度远比hash取值范围小，默认是16，所以当对hash值以桶的长度取余，以找到存放该key的桶的下标时，由于取余是通过与操作完成的，会忽略hash值的高位。因此只有hashCode()的低位参加运算，发生不同的hash值，但是得到的index相同的情况的几率会大大增加，这种情况称之为hash碰撞。 即，碰撞率会增大。

哈希表的容量一定要是2的整数次幂。

首先，length为2的整数次幂的话，h&(length-1)就相当于对length取模，这样便保证了散列的均匀，同时也提升了效率；

其次，length为2的整数次幂为偶数，这样length-1为奇数，奇数的最后一位是1，这样便保证了h&(length-1)的最后一位可能为0，也可能为1(这取决于h的值)，即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性。

而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了一半的空间。

因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列

由于存在链表和红黑树互换机制，搜索时间呈对数 O(log(n))级增长，而非线性O(n)增长

扰动函数

扰动函数就是为了解决hash碰撞的。它会综合hash值高位和低位的特征，并存放在低位，因此在与运算时，相当于高低位一起参与了运算，以减少hash碰撞的概率。（在JDK8之前，扰动函数会扰动四次，JDK8简化了这个操作）

扩容操作时，会new一个新的Node数组作为哈希桶，然后将原哈希表中的所有数据(Node节点)移动到新的哈希桶中，相当于对原哈希表中所有的数据重新做了一个put操作。所以性能消耗很大，可想而知，在哈希表的容量越大时，性能消耗越明显。

扩容时，如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置。
因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位， 或者扩容后的下标，即high位。 high位= low位+原哈希桶容量

运算

static int indexFor(int h, int length) { //根据hash值和数组长度算出索引值  
    return h & (length-1);  //这里不能随便算取，用 hash&(length-1) 是有原因的，这样可以确保算出来的索引是在数组大小范围内，不会超出  
}

除法效率低，与运算效率高

hash & (table.length-1)
hash % (table.length) 

if ((e.hash & oldCap) == 0)

参考链接

https://baiqiantao.github.io/Java/%E9%9B%86%E5%90%88/3AFbAb/#HashMap%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84

根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：

如果这两个 Entry 的 key 的 hashCode() 相同，那它们的存储位置相同。

loadFactor的默认值为0.75

fail-fast 策略

HashMap 不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了 map，那么将抛出 ConcurrentModificationException。

这一策略在源码中是通过 modCount 域实现的，modCount 就是修改次数，对 HashMap 内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount

issues

HashMap特性？
HashMap存储键值对，实现快速存取数据；允许null键/值；非同步；不保证有序(比如插入的顺序)，实现map接口。

HashMap的原理，内部数据结构？

讲一下 HashMap 中 put 方法过程？

get()方法的工作原理？

HashMap中hash函数怎么是是实现的？

还有哪些 hash 的实现方式？
还有数字分析法、平方取中法、分段叠加法、 除留余数法、 伪随机数法。

HashMap 怎样解决冲突？
HashMap中处理冲突的方法实际就是链地址法，内部数据结构是数组+单链表。

当两个键的hashcode相同会发生什么？

抛开 HashMap，hash 冲突有那些解决办法？
开放定址法、链地址法、再哈希法。

如果两个键的hashcode相同，你如何获取值对象？

针对 HashMap 中某个 Entry 链太长，查找的时间复杂度可能达到 O(n)，怎么优化？

如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
扩容。这个过程也叫作rehashing，大致分两步：

补充：

为什么String, Interger这样的类适合作为键？

HashMap与HashTable区别

Hashtable可以看做是线程安全版的HashMap，两者几乎“等价”（当然还是有很多不同）。
Hashtable几乎在每个方法上都加上synchronized（同步锁），实现线程安全。
HashMap可以通过 Collections.synchronizeMap(hashMap) 进行同步。

区别

阈值为８

TreeNodes占用空间是普通Nodes的两倍
理想情况下使用随机的哈希码，容器中节点分布在hash桶中的频率遵循泊松分布，按照泊松分布的计算公式计算出了桶中元素个数和频率的对照表，可以看到链表中元素个数为8时的概率已经非常非常小，所以根据概率统计选择了8。

理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布，我们可以看到，一个bin中链表长度达到8个元素的概率为0.00000006

元素个数小于8，查询成本高，新增成本低。

元素个数大于8，查询成本低，新增成本高。

线程不安全

https://blog.csdn.net/mydreamongo/article/details/8960667

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
 
        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
 
        return e;
    }

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
 
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }
上一篇下一篇

猜你喜欢

热点阅读