当前位置： 移动技术网 > IT编程>开发语言>Java > HashMap实现原理及常见问题

HashMap实现原理及常见问题

2019年01月23日  | 移动技术网IT编程  | 我要评论

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进行取模运算，即(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的次幂的原因。

　　经过两次计算，得到了最后的哈希码，为便于描述，在这里数组称为table，重复上述：使用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方法,不可变可以防止键的改变,重写那两个方法可以减少碰撞的几率.

　　

 

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网