聊聊HashMap

HashMap是什么？

• HashMap 是一个散列桶（1.7是数组+链表，1.8是数组+链表+红黑树），它存储的内容是键值对 key-value 映射。
• HashMap 采用了数组和链表的数据结构，能在查询和修改方便继承了数组的线性查找和链表的寻址修改。
• HashMap 是非 synchronized，所以 HashMap 很快。
• HashMap 可以接受 null 键和值，而 Hashtable 则不能（原因就是 equlas() 方法需要对象，因为 HashMap 是后出的 API 经过处理才可以）。如果键为null，那么调用hash()方法得到的都将是0，所以键为 null 的元素都始终位于哈希表 table[0] 中。

HashMap在JDK1.7和1.8中的区别

1. 底层数据结构不一样，1.7是数组+链表，1.8则是数组+链表+红黑树结构（当链表长度大于8，转为红黑树）。

2. JDK1.7 用的是头插法，而JDK1.8及之后使用的都是尾插法，那么他们为什么要这样做呢？

   因为 JDK1.7 是用单链表进行的纵向延伸，当采用头插法时会容易出现逆序且环形链表死循环问题。但是在 JDK1.8 之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。

3. 1.8 rehash 时保证原链表的顺序，而1.7中 rehash 时有可能改变链表的顺序（头插法导致）。

4. 在扩容的时候：1.7在插入数据之前扩容，而1.8插入数据成功之后扩容。

5. 1.7计算 hash 运算多，1.8计算 hash 运算少 。

6. 1.7受 rehash 影响，1.8调整后是 (原位置) or (原位置+旧容量)。

HashMap工作原理

HashMap 是基于 hashing 的原理，通过 put(key, value) 存储对象到 HashMap 中，使用 get(key) 从 HashMap 中获取对象。当我们给 put() 方法传递键和值时，我们先对键调用 hashCode() 方法，计算并返回的 hashCode 是用于找到 Map 数组的 bucket 位置来储存 Node 对象。这里关键点在于，HashMap 是在 bucket 中储存键对象和值对象，作为Map.Node 。

具体 put 过程（JDK1.8）

1. 对 Key 求 Hash 值，然后再计算下标
2. 如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的 Hash 值相同，需要放到同一个 bucket 中）
3. 如果碰撞了，以链表的方式链接到后面
4. 如果链表长度超过阀值（TREEIFY THRESHOLD==8），就把链表转成红黑树，链表长度低于6，就把红黑树转回链表
5. 如果节点已经存在就替换旧值
6. 如果桶满了（容量16*加载因子0.75），就需要 resize（扩容2倍后重排）

具体 get 过程

考虑特殊情况：如果两个键的 hashcode 相同，你如何获取值对象？

当我们调用 get() 方法，HashMap 会使用键对象的 hashcode 找到 bucket 位置，找到 bucket 位置之后，会调用 keys.equals() 方法去找到链表中正确的节点，最终找到要找的值对象。

有什么方法可以减少碰撞？

扰动函数可以减少碰撞

原理是如果两个不相等的对象返回不同的 hashcode 的话，那么碰撞的几率就会小些。这就意味着链表结构减小，这样取值的话就不会频繁调用 equal 方法，从而提高 HashMap 的性能（扰动即 Hash 方法内部的算法实现，目的是让不同对象返回不同hashcode）。

使用不可变的、声明作 final 对象，并且采用合适的 equals() 和 hashCode() 方法，将会减少碰撞的发生

不可变性使得能够缓存不同键的 hashcode，这将提高整个获取对象的速度，使用 String、Integer 这样的 wrapper 类作为键是非常好的选择。

为什么 String、Integer 这样的 wrapper 类适合作为键？

因为 String 是 final，而且已经重写了 equals() 和 hashCode() 方法了。不可变性是必要的，因为为了要计算 hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的 hashcode 的话，那么就不能从 HashMap 中找到你想要的对象。

HashMap 中 hash 函数怎么是实现的?

在 hashmap 中要找到某个元素，需要根据 key 的 hash 值来求得对应数组中的位置。如何计算这个位置就是 hash 算法。我们一般对哈希表的散列很自然地会想到用 hash 值对 length 取模（即除法散列法），Hashtable 中也是这样实现的，这种方法基本能保证元素在哈希表中散列的比较均匀，但取模会用到除法运算，效率很低，HashMap 中则通过 h&(length-1) 的方法来代替取模，同样实现了均匀的散列，但效率要高很多，这也是 HashMap 对 Hashtable 的一个改进。这也是为什么哈希表的容量一定要是2的整数次幂，length 为2的整数次幂的话，h&(length-1) 就相当于对 length 取模，这样便保证了散列的均匀，同时也提升了效率。

拉链法导致的链表过深，为什么不用二叉查找树代替而选择红黑树？为什么不一直使用红黑树？

引入红黑树就是为了查找数据快，解决链表查询深度的问题。我们知道红黑树属于平衡二叉树，为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少。所以当长度大于8的时候，会使用红黑树；如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

红黑树

1. 每个节点非红即黑
2. 根节点总是黑色的
3. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
4. 每个叶子节点都是黑色的空节点（NIL节点）
5. 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

HashMap 与 HashTable 区别

• 默认容量不同，扩容不同(HashMap 默认16，扩容 2 倍；HashTable 默认11，扩容 2 倍 + 1)
• 线程安全性：HashTable 安全
• 效率不同：HashTable 要慢，因为加锁
• HashMap 可以接受为 null 的键值 (key) 和值 (value)，而 Hashtable 则不行
• HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的
• Hashtable 计算 hash 值，直接用 key 的 hashCode()，而 HashMap 重新计算了 key 的 hash 值(hash 函数)
• 迭代器：HashMap 的迭代器 (Iterator) 是 fail-fast 迭代器，而 Hashtable 的 enumerator 迭代器不是 fail-fast 的。所以当有其它线程改变了 HashMap 的结构（增加或者移除元素），将会抛出 ConcurrentModificationException，但迭代器本身的 remove() 方法移除元素则不会抛出 ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看 JVM。这条同样也是 Enumeration 和 Iterator 的区别。

CocurrentHashMap

JDK1.7

• CocurrentHashMap 是由 Segment 数组和 HashEntry 数组和链表组成
• Segment 是基于重入锁（ReentrantLock）：一个数据段竞争锁。每个 HashEntry 一个链表结构的元素，利用 Hash 算法得到索引确定归属的数据段，也就是对应到在修改时需要竞争获取的锁。ConcurrentHashMap 支持 CurrencyLevel（Segment 数组数量）的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment
• 核心数据如 value，以及链表都是 volatile 修饰的，保证了获取时的可见性
• 首先是通过 key 定位到 Segment，之后在对应的 Segment 中进行具体的 put 操作如下：
  • 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
  • 遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value
  • 不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容
  • 最后会解除在 1 中所获取当前 Segment 的锁。
• 虽然 HashEntry 中的 value 是用 volatile 关键词修饰的，但是并不能保证并发的原子性，所以 put 操作时仍然需要加锁处理

首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。

• 尝试自旋获取锁
• 如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。最后解除当前 Segment 的锁

JDK1.8

CocurrentHashMap 抛弃了原有的 Segment 分段锁，采用了 CAS + synchronized 来保证并发安全性。其中的 val next 都用了 volatile 修饰，保证了可见性。

最大特点是引入了 CAS

借助 Unsafe 来实现 native code。CAS有3个操作数，内存值 V、旧的预期值 A、要修改的新值 B。当且仅当预期值 A 和内存值 V 相同时，将内存值V修改为 B，否则什么都不做。Unsafe 借助 CPU 指令 cmpxchg 来实现。

CAS 使用实例

对 sizeCtl 的控制都是用 CAS 来实现的：

• -1 代表 table 正在初始化
• N 表示有 -N-1 个线程正在进行扩容操作
• 如果 table 未初始化，表示table需要初始化的大小
• 如果 table 初始化完成，表示table的容量，默认是table大小的0.75倍，用这个公式算 0.75（n – (n >>> 2)）

CAS 会出现的问题：ABA

解决：对变量增加一个版本号，每次修改，版本号加 1，比较的时候比较版本号。

put 过程

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

get 过程

• 根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值
• 如果是红黑树那就按照树的方式获取值
• 就不满足那就按照链表的方式遍历获取值

Addition

ConcurrentHashMap 在 Java 8 中存在一个 bug 会进入死循环，原因是递归创建 ConcurrentHashMap 对象，但是在 JDK 1.9 已经修复了。

public class ConcurrentHashMapDemo{
    private Map<Integer,Integer> cache =new ConcurrentHashMap<>(15);
 
    public static void main(String[]args){
        ConcurrentHashMapDemo ch =    new ConcurrentHashMapDemo();
        System.out.println(ch.fibonaacci(80));        
    }
 
    public int fibonaacci(Integer i){        
        if(i==0||i ==1) {                
            return i;        
        }
 
        return cache.computeIfAbsent(i,(key) -> {
            System.out.println("fibonaacci : "+key);
            return fibonaacci(key -1)+fibonaacci(key - 2);        
        });       
    }
}

TreeMap 和 HashMap 的比较

• TreeMap 是根据 key 进行排序的，它的排序和定位需要依赖比较器或覆写 Comparable 接口，也因此不需要 key 覆写 hashCode 方法和 equals 方法，就可以排除掉重复的 key，而 HashMap 的 key 则需要通过覆写 hashCode 方法和 equals 方法来确保没有重复的 key。
• TreeMap 的查询、插入、删除效率均没有 HashMap 高，一般只有要对 key 排序时才使用 TreeMap。
• TreeMap 的 key 不能为 null，而 HashMap 的 key 可以为 null。

LinkedHashMap 和 HashMap 的比较

LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比 HashMap 慢，不过有种情况例外，当 HashMap 容量很大，实际数据较少时，遍历起来可能会比 LinkedHashMap 慢，因为 LinkedHashMap 的遍历速度只和实际数据有关，和容量无关，而 HashMap 的遍历速度和他的容量有关。