星空

人生不仅有眼前的苟且,还有诗和远方.

0%

HashMap浅谈-基本方法

HashMap的初始化过程

HashMap的初始化有两种方法:

  1. 直接使用HashMap的无参构造方法,此时初始化的容量为:DEFAULT_LOAD_FACTOR 也就是16

    1
    2
    3
    4
    5
    6
    7
    /**
    * Constructs an empty <tt>HashMap</tt> with the default initial capacity
    * (16) and the default load factor (0.75).
    */
    public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
  2. 传入容量参数的有参构造方法,此时的初始化容量需要进行计算

1
2
3
4
5
6
7
8
9
10
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

​ 上一文中提到,HashMap的容量必须为2的幂次方,但是不是所有的同学在创建Map的时候都会遵守这个规则,在这种情况下,HashMap也会对传入的参数进行校准,规则是将 参数值转换为最接近、且大于等于指定参数的 2 的 幂次方的值,它确保了HashMap不管是在初始化时,或者在扩容时,它的容量一直保持的是2的幂次方的值,具体方法可以参考:

1
2
3
4
5
6
7
8
9
10
11
12
/**
* Returns a power of two size for the given target capacity.
*/
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;
}

HashMap的基本方法及原理

put方法

put方法是HashMap的一个基本方法,它的算法也是非常的复杂的,涉及到了单个节点、链表节点、红黑树节点,容量达到阈值时的自动扩容等。

它的原理主要包括下面几个方面:

  • HashMap的扩容阈值,以及扩容过程

    扩容阈值 = 当前容量 * 扩容因子

    扩容基本上分为几步:

    1、创建一个为原来两倍大的数组

    2、复制原有数组的数据,该转化为链表的转化为链表,该转化为红黑树的转化为红黑树

  • 插入键值对时如何确定落在哪个桶中(它虽然是个数组,但不是纯粹的数组)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
      /**
    * Computes key.hashCode() and spreads (XORs) higher bits of hash
    * to lower. Because the table uses power-of-two masking, sets of
    * hashes that vary only in bits above the current mask will
    * always collide. (Among known examples are sets of Float keys
    * holding consecutive whole numbers in small tables.) So we
    * apply a transform that spreads the impact of higher bits
    * downward. There is a tradeoff between speed, utility, and
    * quality of bit-spreading. Because many common sets of hashes
    * are already reasonably distributed (so don't benefit from
    * spreading), and because we use trees to handle large sets of
    * collisions in bins, we just XOR some shifted bits in the
    * cheapest possible way to reduce systematic lossage, as well as
    * to incorporate impact of the highest bits that would otherwise
    * never be used in index calculations because of table bounds.
    */
    static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    ​ HashMap在计算hash值时,会将 hashCode 做一次16位右位移,然后将右移的结果和 hashCode 做异或运算,减少Hash碰撞的次数,然后将获取的值存储到对应的hash值的桶中

  • 键值的唯一性的保证机制

    1
    2
    if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))

    ​ 在java.util.HashMap#putVal中存在这样一段代码,当key的hash值相同并且key的内存位置相同或者key的值相同时,可以确认是同一个key,此时会根据条件来判断是直接将原来的key对应的value替换还是做其他的操作,以此来保证键值的唯一性。

    ​ 此处也有一定的坑,因为有一个 == 当传入的键值为引用对象时,如果没有重写引用对象的hashCode()方法,会导致同样参数的对象被认为是不同的键值,因为如果不重写hashCode()方法时,那么它就继承的是Object的hashCode()方法,Object的hashCode方法获取到的hashCode对每个对象来说都是唯一的, 可以查看下面的例子

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    static class HashKey {
    /**
    * Id
    */
    private Integer id;
    /**
    * hashKey
    */
    private String hashKey;
    ...
    }
    public static void main(String[] args) {
    Map<HashKey,String> map = new HashMap<>();
    HashKey a = new HashKey(1,"10086");
    HashKey b = new HashKey(1,"10086");
    map.put(a,"1");
    map.put(b,"1");
    System.out.println(JSON.toJSONString(map));
    }
    输出结果:{{"hashKey":"10086","id":1}:"1",{"hashKey":"10086","id":1}:"1"}

    所以,如果使用对象做键值对的键值的话,一定记得重写HashCode()方法

    1
    2
    3
    4
    5
    @Override
    public int hashCode() {
    return Objects.hash(id, hashKey);
    }
    输出结果:{{"hashKey":"10086","id":1}:"1"}
  • 发生hash碰撞(不同的键值hash值相同)时的处理机制

    虽然在hash值的计算上都是在极力避免出现hash碰撞的情况,但是hash碰撞还是有可能会发生,那么当hash值相同但是键值不同的键值对该如何存放呢,分为两种情况:

    1、在当前的hash对应的bin下面会创建成一个长度不超过8的链表

    2、当链表长度大于等于8的时候,会转化红黑树,因为红黑树的查询效率是非常高的,但是占用空间会比链表大,典型的使用空间换时间,但是换的物超所值

  • 单节点拉链法的实现过程

    1
    2
    3
    4
    5
    6
    static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    }

    ​ 代码中的next就是下一个节点,当最后一个节点next为null时,代表着这个链表结束了。

    值得注意的是在JDK7之前链表使用的是头插法(不是使用的Node),当两个线程在执行resize()方法的时候可能会产生环形链表,在调用get()方法会死循环,导致OOM

  • 链表转化为红黑树的方法过程

    ​ 当链表的长度达到8时,已经是一个相对比较长的结构了,这时候查询的效率会随着链表的数量增长而降低,此时为了追求性能最大化,就会将链表转化为红黑树,这时候会产生一个问题:红黑树既然查询效率足够的高,为什么不直接采用红黑树的结构而使用链表达到8时才转变呢?

    这个其实也是有原因的,在一定的范围内,用空间换取时间效率是可取的,当链表长度比较短时,转变成红黑树,空间结构变大了,但是此时查询效率并没有因此而提高,反而得不偿失了,所以当链表达到阈值时来使用红黑树是相对比较划算的一种方案。

get方法

​HashMap设计的最主要原因就是为了提高查询效率,get方法是使用的最频繁的一个方法之一,它主要就是靠hash算法获取的值来快速定位到索引,然后返回对应的索引对应值。

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
/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

​ get方法主要包含以下几个过程

​ 1、获取key的hash计算参数

​ 2、查找对应索引位置

​ 3、如果是单节点Node直接返回Node,如果是链表Node在链表中获取Node节点,如果是红黑树节点,那么调用红黑树的查询方法快速找到Node并且返回

remove方法
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
45
46
47
48
49
50
51
52
```java
/**
* Implements Map.remove and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
```

remove()方法也是个比较特殊的方法,它的作用和put()是完全相反的,基本也分为以下几个过程:

1、如果是单节点Node,那么直接将对应的Node设置为Null

2、如果是链表Node,那么将该Node删除的同时,将它前一个Node的next替换为后一个Node,保证链表的连续性

3、如果是红黑树Node,那么就需要调用红黑树的删除节点方法进行删除了,此时如果红黑树的Node值为2-6个时,会调方法转化为链表结构的Node

总结

HashMap是一个数组,但它是一个特殊的数组,包含了多种结构单元:单节点Node、Node链表、红黑树,根据实际情况互相转化,因为它的特殊性,造就了它超高的查询效率,O(1) 级别的查询效率,直接根据对应索引的位置找到对象并返回

HashMap的容量也是有规律的,为了结构的稳定性以及保障索引的散列计算更加均匀,它的容量必须是2的幂次方,即使是没有传正确的容量参数,也是会进行校准的

HashMap的扩容是达到一定阈值后会进行两倍放大,创建一个新的数组,将原来对象进行复制,并且会对单节点类型的元素重新计算他们的索引位置,如果是红黑树的话,会根据红黑树特有的方法进行扩容,在红黑树与链表之间进行动态转化

HashMap和List、Set等集合一样,不是线程安全的,它在多线程情况是不具备线程安全特性的,如果同时有多个put或者多个remove会对它的数据造成比较大的影响,多线程环境下不推荐使用HashMap,它在多线程环境的替代是ConcurrentHashMap,关于ConcurrentHashMap有时间的还可以深入了解一下。