HashMap实现原理及常见问题

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

新老客户大回馈,云服务器低至5折

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方法,不可变可以防止键的改变,重写那两个方法可以减少碰撞的几率.

  

 


原文链接:https://www.cnblogs.com/zfinding/p/10306895.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Synchronize关键字 - 原理

下一篇:Java基础之IO技术(一)