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

3. 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替换为新的数组，此时就达到了扩容的目的。
4. 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)，查询非常快