理解HashMap（ｊｄｋ８）

3 月，跳不动了？>>>

HashMap 数据结构

 图中的 "table" 在 HashMap 中是一个 Node<K,V> 数组 。HashMap 内部数据结构是由数组、链表、树形结构组合而成的。

 

什么是hash？

 百度百科：hash 一般被翻译为 “散列”， 也有直接音译为“哈希”的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

wikipedia : 

哈希函数 :　哈希函数就是能将任意长度的数据映射为固定长度的数据的函数。哈希函数返回的值被叫做哈希值、哈希码、散列，或者直接叫做哈希。一个使用场景就是哈希表，哈希表被广泛用于快速搜索数据。

哈希表：哈希表是一种能实现关联数组的抽象数据结构，能把很多「键」映射到很多「值」上。哈希表使用哈希函数来计算索引，一个索引对应一个值。

 

HashMap 初始化

// initialCapacity 初始化容量大小
// loadFactor 负载因子
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        // threshold 是HashMap是否要进行扩容的标记量
        this.threshold = tableSizeFor(initialCapacity);
    }

initialCapacity ， loadFactor  这两个参数都影响着HashMap的性能。initialCapacity 决定了下一次 resize 后的容量（capacity << 1） ,  loadFactor  决定了 resize 发生的条件 （size > (capacity * loadFactor )） （一般情况下 ， 极端情况下是 size > Integer.MAX_VALUE） 。如果初始化时不指定这两个参数，会使用默认值 ， capacity  = 16 ， loadFactor  = 0.75 。对于 16 的容量空间，如果不能充分利用的话会造成空间资源的浪费。（个人认为高手之所以高都体现在细节之中）

 

散列过程

散列的过程就是将存入的元素均匀的分布到HashMap内部Node数据的过程。均匀分布指的是 ， 数组中的每个位置尽量都存储了一个Node节点，并且该位置上的链表只有一个元素。散列分布的越均匀进行碰撞检测的次数就越少，查询性能就越高。

这就是一个散列较为均匀的 ， 查询时最好情况下可以直接定位 ， 最坏情况下需要进行一次碰撞检测。

 

这是一个散列的不均匀的，查询时会进行多次碰撞检测造成效率较低。

 

碰撞检测

((capacity - 1) & hash) 会计算出 key 存储在 Node 数组中的那个位置上 （得到的值始终会落在 Node数组的长度范围内 ， 等同于 hash % capacity  ， 不过位运算的效率更高）， 如果发现该位置上已经存在Node 了，会将新存入的数据作为链表的尾节点。这样存储和查询时都会进行碰撞检测。碰撞检测其实就是比较传入的 key 的 hash 与同一 bucket 上所有的 key 的 hash 是否一致的过程。 jdk8 在这方面做了优化，加入了树型结构来弥补链表线性结构性能较低的不足。

提高碰撞检测的性能 ， 从代码中也能看出来  ， 该运算的最理想情况（hash 相等情况下）是执行两步 ， 比较 hash ， 比较 key 。 最坏情况是执行 4 步 ， 只要取最好情况就达到了提高性能的目的 。以此类推 key 就可以用一些 String ， Enum 这之类的数据类型。

if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))) {
  // .......
}

 

reszie

rezise 是一个较为消耗性能的过程 ， 在首次向HashMap中存入元素的时候会进行首次resize ,  在之后每当产生新节点（这里的节点指的是Node） ， 同时 size > threshold 的时候会进行 resize ，resize 的过程也是 rehash 的过程。本篇尽量不分析源码只是做整体的，概念上的了解。

 

并发安全

HashMap 是不支持并发的 ， 在并发修改时它采用 fail-fast 的策略 ， 抛出 ConcurrentModificationException 。 多线程环境下操作HashMap有可能会造成死循环 ， 在 resize 的过程当中。不要在多线程场景下使用HashMap 。