HashMap的特点
- HashMap是基于哈希表的Map接口实现。
- HashMap底层采用的是Entry数组和链表实现。
- HashMap是采用key-value形式存储，其中key是可以允许为null但是只能是一个，并且key不允许重复(如果重复则新值覆盖旧值)。
- HashMap是线程不安全的。
- HashMap存入的顺序和遍历的顺序有可能是不一致的。
- HashMap保存数据的时候通过计算key的hash值来去决定存储的位置。
HashMap的宏观结构
数组和链表是两种最基本的线性数据结构，在java中的代表就是java数组和引用变量，HashMap就是用数组和链表来存储数据的，HashMap中默认有一个长度为16的数组，数组的每个元素中存储一个链表的头结点。
当执行Map map=new HashMap(); 时，map实例中初始化一个类型为Entry的空数组。
HashMap中一些重要的常量和变量
/*** The default initial capacity - MUST be a power of two.*///默认长度static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//默认加载因子/*** The load factor used when none specified in constructor.*/static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认数组最大长度/*** The maximum capacity, used if a higher value is implicitly specified* by either of the constructors with arguments.* MUST be a power of two <= 1<<30.*/static final int MAXIMUM_CAPACITY = 1 << 30;//扩容临界值private int threshold；（threshold=capcity*loadFactor）//HashMap数组transient Entry[] table
Entry是HashMap的每个节点
class Entry<K,V> implements Map.Entry<K,V> {
final K key;//key
V value;//value
Entry<K,V> next;//指向下一个节点
int hash;//该key的hashCode
……
}
源码分析
HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。（其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合）
//HashMap的主干数组，可以看到就是一个Entry数组，初始值为空数组{}，主干数组的长度一定是2的次幂。
//至于为什么这么做，后面会有详细分析。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
Entry是HashMap中的一个静态内部类。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
重要字段
/**实际存储的key-value键值对的个数*/
transient int size;
/**阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，
threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到*/
int threshold;
/**负载因子，代表了table的填充度有多少，默认是0.75
加载因子存在的原因，还是因为减缓哈希冲突，如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。
所以加载因子默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32。
*/
final float loadFactor;
/**HashMap被改变的次数，由于HashMap非线程安全，在对HashMap进行迭代时，
如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），
需要抛出异常ConcurrentModificationException*/
transient int modCount;
HashMap有4个构造方法
public HashMap() {……}
public HashMap(int initialCapacity){……}
public HashMap(int initialCapacity, float loadFactor){……}
public HashMap(Map<? extends K, ? extends V> m){……}
第一种和第二种方式最终都会调用第三个构造方法，第一种以默认的数组长度（DEFAULT_INITIAL_CAPACITY）和默认的加载因子（DEFAULT_LOAD_FACTOR）来调用第三种，第二种以自定义长度和自定义的加载因子来调用第三种构造方法。第三种构造方法的代码如下，前面在检查定义的数组长度和加载因子的合法性，接下来对加载因子进行赋值，在这里看到把数组长度initialCapacity赋值给扩容临界值threshold时可能会有所不理解，下面在put方法种就会找到原因。整个初始化过程并没有改变数组（table）的长度，所以其实new完Hashmap之后，table仍然是一个空数组。
public HashMap(int initialCapacity, float loadFactor) {
//如果数组长度小于0，抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果数组长度大于2^30，设置长度为2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//如果数组长度不大于0，或者为非数值型，抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//设置加载因子、扩容临界值
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
HashMap的put操作（put null、hash、扩容）
执行的操作主要有检查table是否为空、检查key是否为null、计算key的hash、根据hash计算数组下标、存储元素
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
当table为空时，就调用inflateTable方法扩大table的容量，inflateTable的源码如下，入参是要把table的扩大的容量大小，但由于table的容量只能是2的幂次方（原因稍后会解释），所以为了保证存储需求且最节省空间，需要先计算出大于等于且最接近2的幂次方，然后实例化table，数组容量为新计算出的长度capacity。
private void inflateTable(int toSize) {
// 返回大于等于且最接近2的幂次方的值
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
如下面putForNullKey()方法源码所示，当put的元素key值为null时，会把该元素存储到HashMap的数组下标为0的链表上，先遍历该链表，找到key是null的节点，用新的value替换旧的value；如果没有找到key是null的节点，就直接在数组下标为0的链表上添加该元素（键值对）。
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
计算key的hash，根据hash计算数组下表。
hash(key)方法是根据key值计算并返回一个整型的数，在Java7中，如果key为String，主要以sun.misc.Hashing.stringHash32((String) k)的方式计算，否则对hashSeed和key的hashCode进行异或运算，再进行无符号右移、异或计算。
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
在Java8中，直接(h = key.hashCode()) ^ (h >>> 16)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
计算出hash值后，需要根据hash值来计算数组的下标
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
addEntry的实现
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
通过以上代码能够得知，当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。
为何HashMap的数组长度一定是2的次幂？
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1),index也可能会发生变化，需要重新计算index，我们先来看看transfer这个方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
这个方法将老数组中的数据逐个链表地遍历，扔到新的扩容后的数组中，我们的数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后，再通过和 length-1进行位运算得到最终数组索引位置。
HashMap的数组长度一定保持2的次幂，比如16的二进制表示为 10000，那么length-1就是15，二进制为01111，同理扩容后的数组长度为32，二进制表示为100000，length-1为31，二进制表示为011111。从下图可以我们也能看到这样会保证低位全为1，而扩容后只有一位差异，也就是多出了最左位的1，这样在通过 h&(length-1)的时候，只要h对应的最左边的那一个差异位为0，就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换)。
数组长度保持2的次幂，length-1的低位都为1，会使得获得的数组索引index更加均匀。
上面的&运算，高位是不会对结果产生影响的（hash函数采用各种位运算可能也是为了使得低位更加散列），我们只关注低位bit，如果低位全部为1，那么对于h低位部分来说，任何一位的变化都会对结果产生影响，也就是说，要得到index=21这个存储位置，h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。
如果不是2的次幂，也就是低位不是全为1此时，要使得index=21，h的低位部分不再具有唯一性了，哈希冲突的几率会变的更大，同时，index对应的这个bit位无论如何不会等于1了，而对应的那些数组位置也就被白白浪费了。
get方法
public V get(Object key) {
//如果key为null,则直接去table[0]处去检索即可。
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
get方法通过key值返回对应value，如果key为null，直接去table[0]处检索。我们再看一下getEntry这个方法。
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//通过key的hashcode值计算hash值
int hash = (key == null) ? 0 : hash(key);
//indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
get方法的实现相对简单，key(hashcode)–>hash–>indexFor–>最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。要注意的是，有人觉得上面在定位到数组位置之后然后遍历链表的时候，e.hash == hash这个判断没必要，仅通过equals判断就可以。其实不然，试想一下，如果传入的key对象重写了equals方法却没有重写hashCode，而恰巧此对象定位到这个数组位置，如果仅仅用equals判断可能是相等的，但其hashCode和当前对象不一致，这种情况，根据Object的hashCode的约定，不能返回当前对象，而应该返回null。
JDK1.8中HashMap的性能优化
假如一个数组槽位上链上数据过多（即拉链过长的情况）导致性能下降该怎么办？
JDK1.8在JDK1.7的基础上针对增加了红黑树来进行优化。即当链表超过8时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。
其它
性能问题
HashMap性能的体现主要在扩容操作上，通过上文就可以了解到，当HashMap中的元素个数size大于等于数组容量和加载因子的乘积时，就会把数组容量扩大至原来的2倍，扩容时，要遍历HashMap中原来的数组中的元素并重新计算每个元素key的hash值和新数组的位置，相对来说是非常耗时的。
//解决方案
因此影响HashMap性能的主要因素有两个：初始容量capacity和加载因子loadFactor，capacity是指HashMap初始化时数组的长度，loadFactor是指HashMap在扩容之前数组空间利用率的一种尺度，理想状态下，HashMap中数组的每个位置都只存储一个元素（数组存满，且没有链表）时，查找效率和存储利用率是最高的，因为通过计算key的hash就可以直接定位到数组中的位置，不需要遍历链表，但这只是理想状态，现实操作中一旦出现hash碰撞就会产生链表，所以在初始化HashMap时，可以预估HashMap中会存储多少个元素，来设置HashMap的初始容量和加载因子的值，尽量避免HashMap扩容操作。
Hash碰撞攻击：可以通过构造大量key值hashcode相同的键值对来发起攻击，会使以hash表为主的结构退化成以链表为主的结构，数据量大时，对某一元素的定位时间复杂度由O(1)降为O(n)。
线程安全
（1）赋值不安全：如果两个线程同时想HashMap中存储键值对，假如这两个key值对应的数组下标一样，当两个线程同时执行到createEntry（）方法中时，优先执行赋值操作的线程锁存储的键值对可能会被另外一个线程存储的键值对覆盖。
（2）多线程环境下对HashMap扩容的时候，每个线程都会执行扩容（resize方法）的代码，最后只有一个线程生成的新数组会赋值给table，其他线程的操作都会丢失；当某个线程已经完成扩容，其他线程刚开始扩容，可能会直接使用已经完成扩容的数组作为原始数组；大量线程对同一个HashMap进行put操作，在扩容的环节可能产生环装链表，导致get元素的时候出现死循环。
方案：
（1）在外部包装HashMap，实现同步机制
（2）使用Map map = Collections.synchronizedMap(new HashMap(…));实现同步（官方参考方案，但不建议使用，使用迭代器遍历的时候修改映射结构容易出错，对每一个方法增加了synchronized ,但并不保证put/get/contain之间的同步)）
（3）使用java.util.HashTable，效率最低（同步锁整个table数组 ,效率较低，几乎被淘汰了）
（4）使用java.util.concurrent.ConcurrentHashMap，相对安全，效率高（同步锁每次只锁一个bucket（数组table的单个元素） ,可以多线程同时读写不同bucket ,也保证了put/get同一个桶的同步，建议使用）
有网友测试过，JDK1.8HashMap的性能要高于JDK1.7 15%以上，在某些size的区域上，甚至高于100%。随着size的变大，JDK1.7的花费时间是增长的趋势，而JDK1.8是明显的降低趋势，并且呈现对数增长稳定。当一个链表长度大于8的时候，HashMap会动态的将它替换成一个红黑树（JDK1.8引入红黑树大程度优化了HashMap的性能），这会将时间复杂度从O(n)降为O(logn)，
最后有一个比较冷门的知识点，hashmap1.7版本链表使用的是节点的头插法，扩容时转移链表仍然使用头插法，这样的结果就是扩容后链表会倒置，而hashmap.1.8在插入时使用尾插法，扩容时使用头插法，这样可以保证顺序不变。
CHM
concurrenthashmap也稍微提一下把，chm1.7使用分段锁来控制并发，每个segment对应一个segmentmask，通过key的hash值相与这个segmentmask得到segment位置，然后在找到具体的entry数组下标。
所以chm需要维护多个segment，每个segment对应一段数组。分段锁使用的是reetreetlock可重入锁实现，查询时不加锁。
若有收获，就点个赞吧
0 人点赞
