HashMap笔记整理(JDK1.8)

发表于 | 分类于 |

什么是Hash？

 散列表(Hash table，也叫哈希表)，是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。(即：输入一个任意长度的m，输出一个固定长度的值n)

 一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名x到首字母F(x)的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则F()，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。(维基百科)

Hash碰撞

 输入一个任意长度的 M ，输出一个固定的长度的值 N。因为这个特性，根据输入值得到固定长度的输出值，必然会存在至少两个不同的输入值而得到相同的输出值；就是为什么会存在 Hash 碰撞。

util.Map 接口

 平时开发过程中，经常会遇到键值对 Key-Value这样的数据结构。HashMap通常能满足大多数场景，使用频率较高。常见的HashMap、LinkedHashMap、TreeMap、Hashtable，都实现了接口类util.Map。继承关系：

mf9OgS.png

HashMap

 HashMap：在JDK1.8中hashMap的底层实现增加了红黑树结构即：数组+链表+红黑树。JDK1.7中为数组+链表结构，通过对key值的hashCode进行hash运算得到的int值，也即对key进行二次hash作为数组的下标来达到存储的目的。由于hash存在碰撞冲突，而解决hash碰撞冲突，可以采用开放地址法与链地址法等。
 hashMap中是用的链地址法(数组加链表)解决冲突问题。数组元素对应链表，当key经过二次hash后得到数组下标，将数据放到对应的链表上；如果hash后得到了相同的int值，并且key不相等，则加入链表。链表中的第一个元素都是后面最新添加进来的那个,之前的则被next变量引用着，在每次put之前都会判断需不需要扩容，阀值为8，JDK1.8之后，当大于8时则改变为红黑树存储。同样的，删除操作时，则反之判断需不需要由红黑树改变为链表。相比较于JDK1.7中时间复杂度由O(n)提高到O(log(n))。

put(key,value)方法

1
2
3
4
5
6
第一次取hash(1.8)
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
高位运算主要从效率和性能开销上做了提升

第二次取hash则实现在put方法中，采用的是位运算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
            //第二次取hash
        if ((p = tab[i = (n - 1) & hash]) == null)

            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            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) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    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;
    }

在JDK1.7中的第二次取hash为：

1
2
3
4
5
static int indexFor(int h, int length) {
     return h & (length-1);
}
对比于：
if ((p = tab[i = (n - 1) & hash]) == null)

put方法的示意图，这里用的是美团技术团队的图，Java 8系列之重新认识HashMap，很棒的解析：
mf9vuQ.jpg

因为hashMap的底层数组长度总是为2的n次方，因此位运算 h&(length-1) 等价于取模运算，但&运算属于CPU级别，效率更高。(这里的length-1，因为length为2的n次方得到的是偶数，如果length为奇数，length-1则为偶数，执行位运算后最后一位必然为0，这样会导致存储空间不均匀，数据都被存储到了数组为偶数下标对应的链表上。也就解释了为什么Node<k,v>的长度设计为2的n次方，这也是设计的巧妙之处)

线程安全

 HashMap是线程不安全的，在多并发的环境下可能会出现死循环的情况，当多个线程同是添加数据，重新计算size扩容时则会发生数据指向错误造成死循环。如果在多线程环境下可以考虑用ConcurrentHashMap来代替。

参考

美团技术团队-Java 8系列之重新认识HashMap(解析的很透彻，学习了)

这个功能是摆设，看看就好～～～