抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

集合

发布于：2023年5月18日

HashMap

HashMap是什么？

HashMap是基于哈希表的 Map 接口的实现。HashMap是基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。

  • HashMap可以接受null键值和值，而HashTable则不能
  • HashMap是非synchronized
  • HashMap很快
  • HashMap储存的是键值对

jdk1.8相对于1.7底层实现发生了一些改变。 1.8主要优化减少了Hash冲突 ，提高哈希表的存、取效率。 底层数据结构不一样，1.7是数组+链表 ，1.8则是数组+链表+红黑树结构（当数组长度大于64且链表长度大于8时，转为红黑树），红黑树是为了优化 Hash 表链表过长导致时间复杂度增加的问题。

1、链表长度大于8时转换为红黑树，小于6时退化为链表，中间数是为了过度使用，防止链表与红黑树之间频繁的转换，造成效率低下。

2、hashMap并不是在链表元素个数大于8就一定会转换为红黑树，而是先考虑扩容，扩容达到默认限制后才转换。

3、hashMap的红黑树不一定小于6的时候才会转换为链表，而是只有在resize的时候才会根据 UNTREEIFY_THRESHOLD进行转换。

HashMap的工作原理

HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，先对Key调用hashCode方法，来计算hash值，返回的hash值用来找bucket对象，来放entry键值对。

下面是HashMap中最主要的两个方法，get(key)和put(key, value)

get(key)方法：

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
 public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

/** 实现 Map.get 和相关方法。
 * 形参:
 * hash – 键的哈希
 * key – 密钥
 * return:
 * 节点，如果没有，则为 null
 **/
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    	//该hash值所在的元素是保存在table[(tab.length-1)&hash]这个位置，所以需要确保在该位置上有Node
        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;
    }

如果key为null，则直接从哈希表的第一个位置table[0]对应的链表上查找。记住，key为null的键值对永远都放在以table[0]为头结点的链表中，当然不一定是存放在头结点table[0]中。如果key不为null，则先求的key的hash值，根据hash值找到在table中的索引，在该索引对应的单链表中查找是否有键值对的key与目标key相等，有就返回对应的value，没有则返回null。

put(key, value)方法：

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
53
54
55
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * Implements Map.put and related methods.
     * @param hash 键的哈希
     * @param key 密钥
     * @param value 要放置的值
     * @param onlyIfAbsent 如果为 true，则不更改现有值
     * @param evict 如果为 false，则表处于创建模式。
     * @return previous value, or null if none
     */
    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;
        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;
    }

如果key为null，则将其添加到table[0]对应的链表中，如果key不为null，则同样先求出key的hash值，根据hash值得出在table中的索引，而后遍历对应的单链表，如果单链表中存在与目标key相等的键值对，则将新的value覆盖旧的value，且将旧的value返回，如果找不到与目标key相等的键值对，或者该单链表为空，则将该键值对插入到单链表的头结点位置（每次新插入的节点都是放在头结点的位置）。

HashMap的hash算法

1
2
3
4
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

首先 h = key.hashCode()是key对象的一个hashCode，每个不同的对象其哈希值都不相同，其实底层是对象的内存地址的散列值，所以最开始的h是key对应的一个整数类型的哈希值。h >>> 16的意思是将h无符号右移16位，然后高位补0，然后再与(h = key.hashCode()) 异或运算得到最终的h值，

为什么是异或运算呢？

使用异或运算就能够得到更好散列性，减少哈希冲突。

运算的结果趋向于得到小的值，或运算的结果趋向于得到大的值，异或运算的结果大小值比较均匀分散，这就是我们想要的结果，这也解释了为什么要用异或运算，因为通过异或运算得到的h值会更加分散，进而 h & (length-1)得到的index也会更加分散，哈希冲突也就更少。

HashMap解决哈希冲突（哈希碰撞）

哈希冲突是由于哈希算法被计算的数据是无限的,而计算后的结果范围是有限的，所以总会存在不同的数据计算后得到的值是一样的,那将会存在同一个位置,就会出现哈希冲突。

1.开放地址法：也称线性探测法,就是从发生冲突的那个位置,按照一定次序从Hash表中找到一个空闲的位置, 把发生冲突的元素存入到这个位置。而在java种ThreadLocal就用到了线性探测法,来解决Hash冲突。

2.链式寻址法：通过单向链表的方式来解决哈希冲突，Hashmap就是用了这个方法。(但会存在链表过长增加遍历时间)

3.再哈希法：key通过某个哈希函数计算得到冲突的时候,再次使用哈希函数的方法对key哈希一直运算直到不产生冲突为止 （耗时间,性能会有影响）

4.建立公共溢出区:就是把Hash表分为基本表和溢出表两个部分，凡是存在冲突的元素，一律放到溢出表

HashMap底层是通过链式寻址法来解决hash冲突的。

哈希表是由数组+链表组成的，因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用LinkedList存储对象，这个Entry会存储在LinkedList中，这个存储的位置一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

两个键的hashcode相同，如何获取值对象？

HashMap会使用键对象的hashcode找到bucket位置，找到bucket位置之后，会调用keys.equals()方法去找到LinkedList中正确的节点，最终找到要找的值对象。从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

HashMap初始容量

HashMap的初始容量默认为16。

new HashMap()之后并不是16，真正创建一个16长度的数组是在第一次put的时候，做一次判断，如果长度为0或者为null的话，就做一次扩容，数组也是在这个时候初始化的。

负载因子

HashMap的负载因子默认为0.75。

1
static final float DEFAULT_LOAD_FACTOR = 0.75f;

在 HashMap 中，临界值（threshold） = 负载因子（loadFactor） * 容量（capacity）。

默认为0.75的原因（泊松分布）：

先看HashMap的底层数据结构

1、负载因子是1.0

数据一开始是保存在数组里，当发生了Hash碰撞的时候，就是在这个数据节点上，生出一个链表，当链表长度达到一定长度的时候，就会把链表转化为红黑树。

当负载因子是1.0时，也就意味着，只有当数组的8个值（这个图表示了8个）全部填充了，才会发生扩容。这就带来了很大的问题，因为Hash冲突时避免不了的。

后果：当负载因子是1.0的时候，意味着会出现大量的Hash的冲突，底层的红黑树变得异常复杂。对于查询效率极其不利。这种情况就是牺牲了时间来保证空间的利用率。

因此一句话总结就是负载因子过大，虽然空间利用率上去了，但是时间效率降低了。

2、负载因子是0.5

后果：负载因子是0.5的时候，这也就意味着，当数组中的元素达到了一半就开始扩容，既然填充的元素少了，Hash冲突也会减少，那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。

但是，此时空间利用率就会大大的降低，原本存储1M的数据，现在就意味着需要2M的空间。

总之，就是负载因子太小，虽然时间效率提升了，但是空间利用率降低了。

3、负载因子0.75

时间和空间的权衡，负载因子是0.75的时，空间利用率比较高，而且避免了相当多的Hash冲突，使得底层的链表或者是红黑树的高度比较低，提升了空间效率。

HashMap扩容机制

HashMap的容量是2的幂次方。

HashMap的初始容量是2的n次幂，扩容也是2倍的形式进行扩容，是因为容量是2的n次幂，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞，避免形成链表的结构，使得查询效率降低！

比如new HashMap<>(3)，给定HashMap一个初始容量3，HashMap在构造器初始化时会自动调用下面的tableSizeFor(int cap)方法将容量默认转为2的n次幂，也就是4，换言之，若初始容量给定为7，则容量会变为8。

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
/**
    * 返回给定目标容量的 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;
   }

/**
  * 使用指定的初始容量和负载因子构造一个空的哈希映射
  */
public HashMap(int initialCapacity, float loadFactor) {
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal initial capacity: " +
                                              initialCapacity);
       if (initialCapacity > MAXIMUM_CAPACITY)
           initialCapacity = MAXIMUM_CAPACITY;
       if (loadFactor <= 0 || Float.isNaN(loadFactor))
           throw new IllegalArgumentException("Illegal load factor: " +
                                              loadFactor);
       this.loadFactor = loadFactor;
       this.threshold = tableSizeFor(initialCapacity);
   }

扩容的时机：

前面提到的公式临界值（threshold） = 负载因子（loadFactor） 容量（capacity）。当HashMap中的数组长度大于临界值时便会发生扩容，例如HashMap的初始容量为16，数组长度就会在大于160.75（默认负载因子数）=12的时候进行扩容，也就是第13次put的时候发生扩容。

更新于：2023年5月19日

评论