星空

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

0%

HashMap浅谈-基本原理

HashMap的组成

HashMap的内部实现是一个数组,但是它是一个特殊的数组。如下图所示:
HashMap数据结构

HashMap的内部结构

HashMap是一个特殊的数组实现,它的数据插入并不是按照顺序逐个写入的,而是按照一种特定算法来确定写入的位置,

然后将对象进行写入,它就是散列计算,就是计算出当前key的hash值,然后对hash值做一定的操作,再计算出当前的hash对应的是哪个桶,然后再将对应的输入写入到桶内(栗子:上图中的Node1节点)

当存在同hash值时,同一个桶内的数据会采用拉链法来使桶内的数据形成一个链表结构,这样同hash的值都会保存并且不会覆盖。

当链表长度达到一定的阈值时(阈值:8),为了提高它的性能,此时会将链表转化为红黑树进行存储(栗子:上图中的Node2节点)

HashMap的核心概念

  1. HashMap的存储结构

    HashMap的底层实现是一个数组,源码如下:

    1
    2
    3
    4
    5
    6
    7
    /**
    * The table, initialized on first use, and resized as
    * necessary. When allocated, length is always a power of two.
    * (We also tolerate length zero in some operations to allow
    * bootstrapping mechanics that are currently not needed.)
    */
    transient Node<K,V>[] table;
  2. HashMap的存储节点

  • HashMap在存储时是一个table,它在正常情况下的基础元素组成是一个Node

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /**
    * Basic hash bin node, used for most entries. (See below for
    * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
    */
    static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    }
  • table在链表长度达到8或者8以上时,会转化为红黑树,变成了一个TreeNode

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    /**
    * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
    * extends Node) so can be used as extension of either regular or
    * linked node.
    */
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent; // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev; // needed to unlink next upon deletion
    boolean red;
    }
  1. HashMap的容量
    HashMap的容量指的是它的table长度,也就是bin(桶)的数量,当桶的数量达到阈值时,它会扩充容量。

    容量值的初始化数值必须是2的幂次方,它的最大容量是2的30次方。当传入的容量值不为2的幂次方时,它会自动转化为大于当前数值的最近的2的幂次方。

    table长度定义:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /**
    * The next size value at which to resize (capacity * load factor).
    *
    * @serial
    */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

    负载因子定义:

    负载因子是一个系数,它与容量参数结合使用,一般不会进行改动,它的默认值是:

    1
    2
    3
    4
    /**
    * The load factor used when none specified in constructor.
    */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    阈值计算公式:

    1
    阈值 = threshold * DEFAULT_LOAD_FACTOR;

    如果当前的容量是1024,那么它的阈值就是1024*0.75=768,当当前HashMap的实际使用容量达到了768时,它会触发扩容操作,扩容的大小为当前容量的两倍大小:2048。

    扩容计算公式:

    容量 = 当前容量 * 2

    扩容原理:

    扩容时,会创建一个2当前容量2倍大数组,然后将原来的数组内容copy进新的数组中,将table替换为新的数组,此时就达到了扩容的目的。

  2. HashMap的元素个数

    在HaspMap中,它的容量不等同于元素个数,它的元素个数定义是:

    1
    2
    3
    4
    /**
    * The number of key-value mappings contained in this map.
    */
    transient int size;

注意的点

Java7之前和Java8之后的扩容机制是不一致的

Java7之前,扩容的因素需要满足两个条件:

1、当前的键值对数量大于当前阈值

2、新增加的键值对发送了hash碰撞

此时会出现两种情况(默认的容量为16)

1、当键值对数量在16时,才会触发扩容机制,此时的情况是前16个元素都没有发生hash碰撞,全部都放置在不同的桶中,到第17个元素插入时,才会完全满足以上两个条件,触发扩容

2、键值对可能在达到26个时,才会触发扩容机制,此时的情况是前11个元素全部发送了hash碰撞,存储在同一个桶中,后面的15个元素全部都没有发生hash碰撞,到第27个元素插入时才会满足以上两个条件,触发扩容

Java8之后,扩容的因素只需要满足一个条件

1、当前插入的元素为新值(不包括同键值,但是值不同的情况),并且已有键值对个数达到阈值时

Node的引入是在Java8之后

Java7之前的节点是Entry,它的结构桶结构除了单节点就是链表,没有红黑树

在Java8之后的节点发生了改变,使用Node节点,在Node节点数为8以下的形成链表,当到达8时,会转变成红黑树结构,提高查询效率

HashMap的查询效率

HashMap的查询效率是O(1),查询非常快