Java中的HashMap原理简单了解

认识HashMap

首先了解一下HashMap
https://zhuanlan.zhihu.com/p/21673805

顺便附两个《小灰漫画》，感觉讲的不错：

• 什么是HashMap
• 多线程下的HashMap

Map接口四个常用实现类

Java为数据结构中的映射定义了一个接口java.util.Map，此接口主要有四个常用的实现类：

• HashMap
• Hashtable
• LinkedHashMap
• TreeMap

类继承关系如下图所示：

HashMap

根据键的 hashCode 存储数据。

访问很快，遍历顺序不确定。

键允许一个为null的，记录允许多个为null的。

==非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致==

如果需要满足线程安全，

• 可以用 Collections.synchronizedMap()方法使HashMap具有线程安全的能力
• 或者使用**ConcurrentHashMap**类

Hashtable

遗留类，不建议使用。

与HashMap类似，不过是继承的Dirctoinary类。

• 不需要线程安全的场合，用HashMap替代；
• 需要线程安全的场合，用ConcurrentHashMap替代

Hashtable是线程安全的，但是并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。

LinkedHashMap

HashMap的子类，带顺序的HashMap，保留了插入顺序。

Iterator遍历时候，先得到的记录肯定是先插入的。

TreeMap

实现了SortedMap接口，按key排序，默认按key的升序排序。

Iterator遍历时候，是按排过序的key遍历的。

HashMap原理

搞清楚HashMap，首先需要知道HashMap是什么，即它的存储结构-字段；其次弄明白它能干什么，即它的功能实现-方法。下面我们针对这两个方面详细展开讲解。

存储结构-字段

每一个下标位置被称为==桶==

• JDK1.8之前：数组 + 链表
• JDK1.8之后：数组 + 链表 + 红黑树
  • 链表长度大于8，转换为红黑树

哈希表解决冲突方法：

• 开放地址法
• 链地址法

JDK中就是用的链地址法。简单来说，就是数组加链表的结合。

功能实现-方法

一个Hash存储的 过程

map.put(“美团”,”小美”);

首先使用hashcode()方法，对key得到其HashCode值，然后Hash算法的后两步（高位运算和取模）定位该key对应的存储位置索引值。

可能定位到相同位置，就是发生了Hash碰撞。

• Hash算法越好，越不容易发生哈希碰撞。
• 当然如果Hash桶足够大，即使差的Hash算法也不容易碰撞。

所以说要在空间（Hash桶）和时间（Hash散列算法）成本之间进行衡量。

==要做到碰撞概率小且空间少，好的Hash算法和扩容机制。==

扩容

如何扩容：

int threshold;             // 所能容纳的key-value对极限 
final float loadFactor;    // 负载因子
int modCount;  	// hashmap内部结构变化的次数(不包含key对应value被覆盖的情况)
int size;	// 实际存储的数量

• Node[] table 的默认length为16
• loadFactor ，负载因子，默认为0.75（一般不要改）
  • 当空间不大，不要求时间的时候：loadFactor 可以增大，可以设为大于1
  • 当空间足够，要求时间效率高，loadFactor 可以适当减小
• threshold = length * Load factor
• 当超出threshold时候，就进行扩容

==Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算==

JDK1.7扩容

扩容机制使用JDK1.7版本的来解释一下，因为它比较简单：

这里是使用key % size，来确定放入哪个哈希桶的。比如第一个中，3%2=1，所以说放到索引为1的桶中。

这里假设LoadFactor = 1 , 那么当k-v的size大于桶的size的时候就扩容。所以说当k_v.size() = 3的时候，进行扩容，边为原来的两倍。

JDK1.7中扩容之后需要重新Hash，即1.2.3的过程。

JDK1.8扩容

JDK1.8改进了，不需要再ReHash。（下面这一块关于位运算的没能看太懂）

使用了位运算的特点：
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

HashMap.put()方法过程

小结

(1) 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。

(2) 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。

(3) HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。

(4) JDK1.8引入红黑树大程度优化了HashMap的性能。

(5) 还没升级JDK1.8的，现在开始升级吧。HashMap的性能提升仅仅是JDK1.8的冰山一角。

线程安全的ConcurrentHashMap

还不懂 ConcurrentHashMap ？这份源码分析了解一下 (qq.com)

HashMap？ConcurrentHashMap？相信看完这篇没人能难住你！_Java团长的博客-CSDN博客

前面提过的Hashtable和这里的ConcurrentHashMap，都是线程安全的。

怎么保证线程安全呢，答案就是==加锁==。

Hashtable中，直接使用了synchronized关键字来对put()和get()方法加锁。但是在竞争强烈的情况下，其效率非常低下。

而ConcurrenHashMap中，使用了一个“分段锁”的东西。

简单来说，JDK1.7使用Segment分段锁，结构是segemtn数组加HashEntiy；JDK8采用 synchronized 加 CAS锁的方式，结构是Node数组加链表/红黑树。

JDK1.7中的ConcurrentHashMap

如图所示，是由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表。

ConcurrentHashMap的核心成员变量，主要就是这里的segments数组：

/**
* Segment 数组，存放数据时首先需要定位到具体的 Segment 中。
*/
final Segment<K,V>[] segments;

transient Set<K> keySet;
transient Set<Map.Entry<K,V>> entrySet;

然后去看Segment对象，ConcurrentMap的内部类，主要是table数组：

static final class Segment<K,V> extends ReentrantLock implements Serializable {

private static final long serialVersionUID = 2249069246763182397L;

// 和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶
 transient volatile HashEntry<K,V>[] table;

transient int count;
transient int modCount;
transient int threshold;
final float loadFactor;

}

然后看一下HashEntry的组成：

HashEntry跟HashMap差不多的，但是不同点是，他使用 volatile 去修饰了他的数据 Value 还有下一个节点 next，保证了获取时的可见性。

构造函数

分为无参构造和有参构造，主要设置以下三个参数：

/**
 * 默认初始化容量
 */
static final int DEFAULT_INITIAL_CAPACITY = 16;

/**
 * 默认负载因子
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 默认并发级别
 */
static final int DEFAULT_CONCURRENCY_LEVEL = 16;

put方法

尝试获取锁，如果获取失败就表明有其他线程在竞争，利用自旋获取锁。自旋达到一定次数则阻塞。

get方法

直接将 key 进行hash之后，定位到Segment上，再Hash一次定位到具体元素上。

因为 value 是通过 volatile 修饰的，保证了内存的可见性，所以说每次获取都是新值。

JDK1.8中的ConcurrentHashMap

put方法

1. Hash：根据 key 计算出 hashcode 。
2. 判断是否需要进行初始化
3. 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
4. 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
5. 如果都不满足，则利用 synchronized 锁写入数据。如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

hashcode = Hash(Key);
for(遍历Node数组){
    if(Node数组为空){
        初始化(Node数组);
    }
    else if( key 对应的 Node[hashcode] 的 value 为空){
        if( CAS写入(Node[hashcode]) ) break;
        else 自旋；
    }
    else if( Node[hashcode] 不存在){
    	扩容；
    }
    else{
        synchronized锁写入;
        if(判断链表长度)
            是否要转换为红黑树;
    }
}