JAVA HashMap原理

HashMap概述

Hash，又称散列。哈希表是一种以键-值(key-value) 存储数据的，和数组、链表、二叉树等同样典型的一种数据结构。Java中用HashMap来实现了哈希表这种数据结构。

内部实现

前言 - hashCode()和equals(obj)方法
java.lang.Object中的方法定义

/** JNI，调用底层其它语言实现 */  
public native int hashCode();  
  
/** 默认同==，直接比较对象 */  
public boolean equals(Object obj) {  
    return (this == obj);  
}  

hashCode是Object类中的方法，因此所有Java对象都有hashCode方法。当类的对象用作HashMap这类哈希结构的key值时，它的返回值用来支撑Hash算法的计算。其它时候，hashCode并没有什么作用。所以很多情况下我们都不需要重写hashCode方法，而Object类中将它定义为native方法。

equals也是Object类中的方法，默认情况下equals比较的是两个对象的引用是否相同，如果要将类的对象用作HashMap的key值，我们一般会重写equals方法。Integer, String等基本类型都已经重写了equals方法，所以我们可以很方便的将它们用作hash的key。

• 底层结构

transient Entry<K,V>[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

HashMap底层是以数组+链表+红黑树（jdk1.8增加了红黑树，这里暂时讨论1.7以前版本）来存储K/V数据的。Entry[] 就是一个K/V键值对数组，通常也叫bucket（散列桶）数组，数组中的每一个Entry又是一个链表，next用于存储链表中的下一个条目。

HashMap底层结构.png

• 存储k/v操作 put(key,value)

1、判断key是否是null，如果是，hash值直接置为0，散列位置为bucket数组中第一个位置，index＝0。直接到步骤3。
2、如果key不为null，根据key的hashcode值计算hash值(h = hash(k.hashcode))，根据哈希值h找到key被散列到bucket数组中的位置index( index = h&(length-1) )。
3、找到bucket数组对应位置 table[index] 的链表。如果链表为空，那么新建一个entry，k/v/hash值存储于entry中，next指向null，table[index]=entry。 如果链表非空，遍历，判断当前key是否和链表中某个entry的key值equals，如果equals，用value替换掉之前旧的value，然后方法立即返回。如果遍历完没有找到，那么创建一个新的entry，将新的entry置于链头，next指向之前的链头entry。 添加entry之前判断是否需要扩容，如果需要，以2的倍数扩容

HashMap put图解.png

观察元素put的过程，我们发现在根据key寻找存储地址时，先比较了key的hashCode，如果hashCode相同，再比较了equals，那么两个key equals的前提是hashCode相等。所以就可以理解我们在初学java时，都熟记的一条原则：重写equals方法，必须重写hashCode方法。equals相等，hashCode一定相同。hashCode相同，不一定equals。

• 根据k值获取v操作 get(key)

1、判断key是否是null，如果是，hash值直接置为0，散列地址为bucket数组中第一个位置，index＝0。找到bucket数组对应位置 table[0] 的链表。如果链表为空，那么返回null；如果不为空，遍历找到key＝null的entry，返回entry的value值。
2、如果key不为null，根据key的hashcode值计算hash值(h = hash(k.hashcode))，根据哈希值h找到key被散列到bucket数组中的位置index( index = h&(length-1) )。
3、找到bucket数组对应位置 table[index] 的链表。如果链表为空，那么返回null；如果不为空，遍历entry，判断当前k的hash值等于entry的hash值，且key值和entry的key值equals的entry条目，返回entry的value值。

进阶分析

1. hash碰撞
   ［什么是hash碰撞？］
   对不同的key可能得到同一散列地址，即key1≠key2，而hash(key1)=hash(key2)，这种现象称碰撞。比如上面的例子中“张三”和“张三的弟弟”两个key在进行hash的时候，得到的hash值都为8，index计算都为0，那么就产生了hash碰撞。

［为什么会有hash碰撞？］
产生上述hash碰撞的原因是由于我们的hashCode方法实现不合理，两个同姓不同名的person，我们在定义Person类的时候不能简单地用“姓氏”一个属性来计算hashCode，应该综合姓氏、姓名、年龄等所有属性计算hashCode。通常我们在Eclipse等IDE自动生成hashCode方法时，编译器会默认帮我们生成合理的hashCode算法就是这个道理。

［hash碰撞会带来什么问题？］
我们知道，数组的优势是随机存取速度快，链表的优势是插入删除速度快。假设所有存入HashMap的entry的key都不会产生hash碰撞，那么所有bucketIndex位置就只会存储一个entry，整个hash表就类似是一个entry数组，存取速度会非常快。反之，如果key的hash碰撞概率非常高的话，那么有可能产生某个bucketIndex位置存储的entry非常之多，链表非常长。极端情况下就是整个entry数组，只有某个index位置有数据存储，整个hash表几乎就变成了一个链表，那么这个hash表的存取速度会非常慢。

［如何避免hash碰撞？］
hash值是根据对象的hashCode计算而来的，如果我们的hashCode算法比较优秀，可以保证重复率低，那么hash碰撞的概率就会降低。但是想做到完全避免，是非常困难的。而且，就算hashCode计算结果不一样，在计算bucketIndex的时候，也可能得到相同的结果。比如，“张三”的hashCode＝8，“张三的弟弟”的hashCode＝16，bucket数组长度为8，那么 index = h & (length-1)，二者得到的结果都是0，仍然会发生碰撞。
那么可能大家会有这样的想法，我们把bucket数组长度调大，翻倍变成16，二者index计算的结果就不会相同了，就没有碰撞了。但是，我们很难合理设计数组的长度，如果设计很长固然可以一定程度上减少hash碰撞，提高存取效率，但是同时也牺牲了内存空间，所以在考虑平衡空间和时间的情况下，我们只能在初始情况下定义一个较小的数组长度，当发现哈希表中存储的数据较多，达到一定阈值时，再对数组长度进行扩容。

2. resize扩容
   ［什么是扩容？如何扩容？］
   hashmap的初始容量为16，即table数组的长度为16。默认加载因子为0.75，即阈值为16*0.75=12。当hash表中存储的entry数量达到12时，hashmap会进行扩容。扩容就是table数组长度翻倍变成32，当达到下一次阈值时，继续扩容长度达到64，依此类推，hashmap每次扩容后容量大小都是2的指数。

［为什么要扩容？］
前面提到，如果数组长度比较小，就会很容易产生hash碰撞，导致entry以链表的形式集中存储在某一个或多个bucketIndex上，降低存取效率。所以为了尽量保证hashmap的存取效率，需要在适当的时候进行扩容。

［扩容会带来什么问题？］
扩容后，会创建一个新的entry数组，将旧的entry数组数据拷贝到新的数组中。并且，这个拷贝不是简单的范围拷贝。扩容后，因为hash的算法和数组length相关联，最后一步是 h & (length - 1)，当length发生变化时，entry的bucketIndex可能发生改变。即以前同时存储在index＝0位置上的“张三”和“张三的弟弟”可能需要分散到index＝0，index＝8的2个不同位置上。所以，扩容会带来rehash，整个hash表中的entry的存储位置需要重新计算，这个操作是很影响效率的。

［如何避免rehash？］
为了减少初始时内存空间的占用，我们只能定义容量较小的hash表。所以rehash肯定会产生，除非我们在创建hashmap之前，提前预知存储entry所需要的容量，然后根据可传入capacity的构造方法构造一个hashmap。

多线程下的使用

HashMap是非线程安全的，在多线程环境下，我们可以使用concurrent包下的ConcurrentHashMap。（Hashtable虽然可以替代HashMap，并且是线程安全的，但是是通过在方法上加synchrionize实现，效率没有ConcurrentHashMap的分段锁高）

总结

1. HashMap底层是以数组+链表的结构存储键值对。
2. 当某一个类的对象想用作HashMap的key值时，需要重写hashCode和equals方法。hashCode的实现要降低重复概率，推荐使用IDE默认的hashCode实现。
3. HashMap在给key寻找存储位置时，先比较hashCode，再比较equals。
4. HashMap扩容导致rehash会造成性能问题，大批量数据存储应尽量在构造hashmap之前设置好容量，避免递增式的rehash。
5. HashMap非线程安全，多线程下推荐使用ConcurrentHashMap。