HashMap实现原理及常见问题

2019-01-23 07:40:28来源：博客园阅读 ()

1.简介

　　HashMap是基于哈希表的Map接口的实现，用来存放键值对（Entry<Key，Value>），并提供可选的映射操作。使用put(Key,Value)存储对象到HashMap中,使用get(Key)从hashMap中获取对象。

2.底层结构

　　HashMap的底层是由数组加链表实现的，因为在链表头部添加删除结点，为栈式链表，所以也称为栈式链结构。链表由 Entry<Key，Value>对象作为结点，我们把存储该链表的数组位置称之为桶，那么桶数量就等于数组的长度。存放数据时时通过key的hashCode来计算hash，得到的hash作为数组的索引（也就是桶位置）存放对象，当hashCode相同时，则称之为哈希冲突，也可称为“碰撞”。此时通过“拉链法”解决冲突。关于拉链法会在下面详细介绍。

//Entry源码
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; }

补充：在jdk1.8版本之后，在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

3.原理分析

　　下面由存取数据的过程进行原理分析：

在使用put方法传递 Entry<Key，Value>时,会对Key调用HashCode()方法,接着会对得到的哈希值再次进行计算，以jdk1.8版本为例，源代码如下。

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
　　从这里我们可以看出hash方法对Key调用HashCode()方法，将得到的哈希值高16位不变，高16位与低16位进行异或运算。这样的目的是通过对哈希值的扰动，尽可能减少碰撞的发生。
　　此时的哈希值还不能作为数组的索引来存放数据，最后还会对扰动后的hash与（数组长度-1）进行取模运算，即(n - 1) & hash 这里n为数组长度，假设n为16 那么(n-1)的二进制为1111，将之与hash进行与位运算，1111截取hash后四位，并保证只是截取操作，截取后的hash与截取前的hash后四位相同，这就保证最后得到的hash能作为索引使数据在数组长度内尽可能均匀分布，减少碰撞，这种方式和hash%n取余的结果差不多又不太一样，通俗点将，取模操作要求n-1的二进制是111...都是1这种形式，也就必须要求n的值必须为2的次幂，这也解释了为什么HashMap规定数组的长度必须是2的次幂的原因。
　　重复上述：使用put方法传递 Entry<Key，Value>时,会对Key计算hash索引，先判断数组table[hash]是否为null，若为null 则入 Entry<Key，Value>，若不为空，就说明发生了碰撞，此时要存入的Entry对象的Key和桶中的Entry对象的Key的hash相同，但是它们可能并不相等，所以会调用equals方法将要存入的Key与桶中的Key一一比对，若均不相等，则存入 Entry(头插入法)，如果相等,会覆盖原来的Entry.这种解决碰撞的方式就是前面说过的“拉链法”。
　　通过对存储过程的原理分析，那获取数据就简单了，在调用get(Key)方法时，同样计算Key的hash，通过计算好的hash找到桶位置，然后遍历链表通过key.equals方法直到找到Value。
常见问题　（1）关于扩容：
　　loadfactor： 默认0.75f,代表桶填充程度，loadFactor越趋近于1，那么数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，导致查找元素效率低，loadFactor越趋近于0，数组的利用率越低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。
　　capacity: 数组长度，必须为2的次幂，默认为16。hashMap构造中可指定初始长度，会通过一个算法转化成2的次幂
　　threshold： threshold = capacity * loadFactor，当entry的数量>=threshold的时候，那么就要考虑对数组的扩容了，这个的意思就是 衡量数组是否需要扩增的一个标准,扩容后,会重新对所有数据进行重新计算,重新存放,这个过程叫做rehash。
　　　　　　

//HashMap保证数组长度为2的次幂的算法
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;
}
　　（2）HashMap与HashTable主要区别为不支持同步和允许null作为key和value，所以如果你想要保证线程安全，可以使用ConcurrentHashMap代替而不是线程安全的HashTable，因为HashTable基本已经被淘汰。
　　（3）如果两个线程都发现HashMap需要调整大小,它们会同时尝试调整大小,在这个过程中,存储在链表中的元素次序会反过来,因为移动到新的桶位置的时候,
hashMap并不会将元素放在尾部,而是放在头部,这是为了避免尾部遍历,如果条件竞争发生,会发生死循环.注意：jdk1.8已经解决了死循环的问题。
（4）key多用String的原因:String是final的,并且重写了hashMap和equals方法,不可变可以防止键的改变,重写那两个方法可以减少碰撞的几率.
　　