关于HashMap,这些你了解吗

逃离我推掉我的手 2023-06-27 05:59 83阅读 0赞

### 关于HashMap,这些你了解吗 ###

*  前言
 *  关于数据结构
 *  关于源码
 *   *  成员变量
     *  节点类
     *   *  hashCode与equals
     *  hash方法
     *  HashMap的初始化
     *   *  tableSizeFor方法
     *  HashMap的put操作
 *  后记

# 前言 #

在面试中，只要涉及了Java基础，HashMap几乎是逃不过的，关于HashMap能考的东西有很多，那么你都了解了吗，本文中就将带大家认识什么是HashMap。

# 关于数据结构 #

最基础的问题，什么是HashMap，它的数据结构又是怎样的？首先所有的Map都是由key-value的键值对组成的，这样的键值对在Java1.7之前的HashMap中是Entry，在Java1.8之后是Node。我们可以理解为一个个的节点，HashMap就是由一个个这样的节点组成的链表数组。不是链表，也不是数组，而是元素是链表的数组。

> 为什么要使用链表和数组组合作为HashMap的数据结构？

采用数组的原因我们都知道是因为特性可以帮助快速定位元素，那么为什么还要使用链表呢？我们在有限容量的数组中使用hash插入元素时，必然可能出现两个元素的hash值相同的情况，这就是所谓的哈希冲突，HashMap中的链表最初就是解决哈希冲突的。

> 使用链表数组的话当链表长度很大时查询效率不是很低吗？

没有错，当链表长度很长时查询效率的确会受到影响，所以在Java1.8中对HashMap的结构做了优化，当链表长度达到阈值8的时候，链表结构会转为红黑树，提升查询时的效率将查询的时间复杂度从O(n)降低到了O(logn)，关于红黑树的介绍就不在这里过多赘述。

# 关于源码 #

> 在Java中是如何实现HashMap的呢？

在Java中1.7前和1.8后HashMap的源码是有较大不同的原因是在1.8对HashMap做了多个方面的优化。我们来看看1.8中HashMap的源码。  
  首先来看看HashMap的成员变量

## 成员变量 ##

//默认初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //树化阈值
    static final int TREEIFY_THRESHOLD = 8;
    //解除树化阈值
    static final int UNTREEIFY_THRESHOLD = 6;
    //最小树化容量
    static final int MIN_TREEIFY_CAPACITY = 64;

DEFAULT\_INITIAL\_CAPACITY 源码中用的是位运算1 << 4，实际上就是16。那么为什么要用位运算呢？  
主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。

> 为什么默认初始容量是16而不是其他的数？

这就不得不提到源码中index的计算方式

index = (n - 1) & hash

这里的n其实就取自容量，当容量为2的整数次幂时，容量减一的二进制表示的所有位都是1，所以只要hash值本身是均匀的，节点排列的index就是均匀的，容量为2的整数次幂实际上是为了实现均匀分布。

> 什么是负载因子，为什么是0.75？

为了减少冲突概率，当HashMap的数组长度达到一个临界值就会触发扩容，把所有元素rehash再放回容器中，这是一个非常耗时的操作，而这个临界值由负载因子和当前的容量大小来决定。  
在源码中有这样一段注释

/* * nodes in bins follows a Poisson distribution * (http://en.wikipedia.org/wiki/Poisson_distribution) with a * parameter of about 0.5 on average for the default resizing * threshold of 0.75, although with a large variance because of * resizing granularity. Ignoring variance, the expected * occurrences of list size k are (exp(-0.5) * pow(0.5, k) / * factorial(k)). The first values are: * * 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 * more: less than 1 in ten million * /

在理想情况下，使用随机哈希码，节点出现的频率在hash桶中遵循泊松分布，同时给出了桶中元素的个数和概率的对照表。  
  从上表可以看出当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为负载因子，每个碰撞位置的链表长度超过8个是几乎不可能的。HashMap负载因子为0.75是空间和时间成本的一种折中。

## 节点类 ##

我们都知道了HashMap的数据结构是由链表数组构成，实际上在源码中就是以节点为单位的链表数组，在Java1.7之前用Entry表示，1.8后改为Node，Node也是实现自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; }
    
            public final int hashCode() { 
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
    
            public final V setValue(V newValue) { 
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            public final boolean equals(Object o) { 
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) { 
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }

我们可以看到在节点类中除了键值对key和value以外还有两个成员变量，一个是当前节点的哈希值hash，还有下一个节点的引用next。眼尖的朋友可能看到了，节点类中是没有key的set方法的，因为键值对中的key是不允许形成节点之后再做改动的。除了get，set方法之外，还可以看到equals和hashCode方法，都重写自Object类。

### hashCode与equals ###

> 为什么要重写equals方法和hashCode方法？

因为在Object类中equals的默认实现是

return (a == b) || (a != null && a.equals(b));

即只有当两个对象引用指向同一地址时才被判断为相等，所以当我们需要用对象中的一些属性的值来作为哦判断对象相等的依据时需要重写equals方法，又因为在HashSet，HashMap等集合中，判断元素相等用到了元素的hashCode方法，所以为了避免hashCode与equals判断对象是否相等时产生不一致的情况，同样需要重写hashCode方法。

## hash方法 ##

HashMap中的hash方法通过对key的hashCode做二次处理来获取hash值。

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

当key为null时直接返回0，当key不为null时，将key的hashCode无符号右移16位后与本身异或。  
在Object类中的hashCode()方法返回值是31位的，右移16位恰好是一半，右移时高位补0。

## HashMap的初始化 ##

HashMap的构造方法一共有四个

/** * 无参构造函数(没有传入任何参数，只将默认负载因子赋值) */
        public HashMap() { 
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
        /** * 传入初始化容量，这里实际上调用了另一个构造函数 */
        public HashMap(int initialCapacity) { 
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
        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赋了值，赋值过程中用到了tableSizeFor(initialCapacity)方法。

### tableSizeFor方法 ###

/** * 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;
        }

那么这个用了很多位运算看起来很复杂的方法实际上做了什么呢，实际上就是初始化了容量，我们传入的初始化容量并不会被直接接受，而是经过这个方法后返回一个大于等于该容量且是2的整数次幂的的最小值。  
  那么是怎么做到的呢，首先下面这一步，将容量减一的值右移一位在与原值进行或操作，取出最高位的1，假定原值为01XXXX…，那么这一次操作后原值变为011XXXX…

n |= n >>> 1;

经过

n |= n >>> 2;
      n |= n >>> 4;
      n |= n >>> 8;
      n |= n >>> 16;

最高一位的1后所有的位都变为1，将这样的值加1，恰好是2的整数次幂。

> 那为什么在操作前要先将cap-1呢？

因为如果cap本身就是2的整数次幂且不减一，经过上面的操作后，产生的容量就是原来的二倍大小，不是最小的了。

## HashMap的put操作 ##

当我们调用put方法时实际上调用了另一个方法putVal，方法中除了传入key，value和key的hash值之外还传了两个布尔类型的参数，onlyIfAbsent为true是只在当前key对应的原value为null或不存在时做覆盖或插入操作，为false时则可以覆盖原有value值；evict在HashMap中无作用，用到这个参数的方法void afterNodeInsertion(boolean evict) \{ \}在LinkedHashMap实现，这里不做介绍。  
  我们可以看到HashMap中的put方法默认是会覆盖相同key的原值的，如果我们不希望覆盖，可以调用HashMap中提供的另一个方法，同样是调用putVal方法只是onlyIfAbsent值改成了true。

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

从添加元素调用的putVal方法我们可以发现，在添加元素的过程中调用了resize()方法调整容量，在HashMap中容量的初始化并不是在构造方法中执行的，而是到第一次添加元素的时候才初始化容量。  
  添加元素时需要判断是否需要扩容，当前元素应该放在哪个桶，是否已存在相同的key，是否是树节点等。  
  我们可以看到

p.next = newNode(hash, key, value, null);

新添加的节点被添加在链表尾部，这也是1.8的改动之一，在1.7和之前的版本中，新的节点都是添加在链表头的，因为新节点被认为被访问的概率更大。

> 那为什么1.8又要改成尾部插入呢？

这是因为当插入元素达到扩容的条件时，扩容的过程并不是简单的复制一遍，而是所有元素会有一个rehash操作，此时使用头插法如果有多个线程同时操作有可能出现链表中某两个节点形成环，为了避免链表成环，1.8之后都采用尾插法。

# 后记 #

关于HashMap的知识点其实还有很多，比如和HashTable，HashSet等集合的对比，并发问题的处理，JUC下的ConcurrentHashMap，源码中提到的红黑树，泊松分布，布隆过滤器等等，篇幅原因不在本篇介绍，感兴趣的朋友可以在评论中评论您感兴趣的知识点，您的评论就是我的素材，您的支持就是我的动力，点关注，不迷路！