HashMap 实现原理

HashMap 概述

• HashMap 是基于哈希表的 Map 接口非同步实现，允许使用 null 值和 null 键，不保证映射顺序，特别是不保证该顺序恒久不变
• HashMap 数据结构是基于数组与引用，是一个“链表散列”的数据结构，HashMap 底层也是一个数组结构，数组中的每一项又是一个链表 Entry 对象

HashMap结构

• Entry 对象是一个静态类，包含了 key、value 键值对对象，还包含了一个 next 的引用指向下一个 Entry 对象

HashMap 核心方法解读

put 方法

• 如果 key 已存在，新的 value 就会替换旧的 value，并返回旧的 value，如果 key 不存在，返回 null
• 当 put 元素的时候，先根据 key 的 hashCode 计算 hash 值，得到元素在数组中的下标，如果该数组位置上已有元素，那么这个位置上的元素以链表形式存放，新加入的在链头，后加入的在链尾，若该数组位置上没元素，则直接放置到该位置上
• 当 HashMap 存储 key-value 时，完全没有考虑 Entry 中的 value ，仅仅根据 key 来计算并决定每个 Entry 存储位置，而 value 保存在哪里都可以

get 方法

• 当在 HashMap 中要找到某个元素时，需要根据 key 的 hash 值来求得对应数组中的位置，如何计算这个位置就是 hash 算法，我们希望这个 HashMap 里的元素位置尽量分布的均匀些，尽量每个位置上的元素只有一个，当我们用 hash 算法求得位置时马上就能获取到元素，优化了查询效率
• 对于任意堆对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(int h) 方法计算的 hash 码值总是相同的，但 HashMap 针对此现象有进行优化

HashMap 归纳

• HashMap 是一个“链表散列”结构，保存 Entry 对象，Entry 对象是一个 key-value 键值对类型，并包含了一个 next 引用指向下一个 Entry 对象
• 当调用 put 方法时会根据通过 hash 算法计算 key 来决定其在数组中的存储位置在根据 equals 方法决定其在链表中存储的位置
• 当调用 get 取出一个 Entry 时，也会根据 hash 算法计算 key 找到其在数组中的存储位置，再通过 equals 从该链表中取出 Entry

HashMap 的 resize

• 当 HashMap 元素越来越多时，hash 冲突的几率也越来越高，因为数组长度是固定的，为了提高效率就要对数组进行扩容，但扩容十分消耗性能，原数组中的数据必须重新计算其在数组中的位置
• 当 HashMap 中的元素个数超过（数组大小*loadFactor） 时会进行扩容，默认数组初始容量为16，加载因子为0.75
• 数组扩容是一个非常消耗性能的操作，如果我们已经预先知道 HashMap 中元素大小，那么预设个数就能提高性能，加载因子越高代表对空间利用更充分，但查询效率低，加载因子太小，数据过于稀疏，浪费了空间资源

Fail - Fast机制

• HashMap 不是线程安全的，如果在使用迭代器过程中有其它线程修改了 Map 那么会抛出 ConcurrentModificationException，这就是所谓的 fail-fast 策略

HashSet 实现原理

• HashSet 底层是基于 HashMap 实现的
• 由于 HashMap 的 put() 方法添加 key-value 对时，当新放入 HashMap 的 Entry 中 key 与集合中原有 Entry 的 key 相同（hashCode()返回值相等，通过 equals 比较也返回 true），新添加的 Entry 的 value 会将覆盖原来 Entry 的 value（HashSet 中的 value 都是PRESENT），但 key 不会有任何改变，因此如果向 HashSet 中添加一个已经存在的元素时，新添加的集合元素将不会被放入 HashMap中，原来的元素也不会有任何改变，这也就满足了 Set 中元素不重复的特性
• 如果添加的是在 HashSet 中不存在的，则返回 true；如果添加的元素已经存在，返回 false

HashTable 实现原理

• HashTable 与 HashMap 一样，也是链表散列，存储键值对，但 HashTable 继承了 Dictionary 类，实现了 Map、Clonable、Serializable 接口
• Hashtable 与 HashMap 简单比较：
  • Hashtable 基于 Dictionary 类，而 HashMap 基于 AbstractMap，实现方式不同
  • HashMap 的 key-value 允许为 null，Hashtable 的 key-value 都不许为 null，会报 NullPointerException
  • Hashtable 方法是同步的，几乎所有 public 方法都为 synchronized 的，适合多线程同步，HashMap 非线程安全，但在 Collections 类中存在一个静态方法：synchronizedMap()，该方法可以创建了一个线程安全的 Map 对象

LinkedHashMap 实现原理

• HashMap 是无序的，LinkedHashMap 实现了有序的 HashMap，它是 HashMap 的一个子类，也是非线程安全的
• 与 HashMap 不同的是，LinkedHashMap 维护着一个双重链接列表，默认按照插入顺序排序，也可以按照访问顺序，此时当调用 get 方法访问链表时，会将这次访问的元素移动至链表尾部，不断访问会形成新的排序方式
• LinkedHashMap的实现：
  • LinkedHashMap 重新定义了 Entry 对象，该 Entry 对象除了存放 key-value 外，还保存了上一个元素 before 和下一个元素 after 引用，从而构成双向链表
  • LinkedHashMap 使用 HashMap 构造方法进行初始化，但多了个 accessOrder 对象，默认为 false 代表按照插入顺序进行迭代，设置为 true 代表以访问顺序进行迭代
  • 使用 LinkedHashMap 可以实现 LRUcache（最近最少使用缓存），因为 LinkedHashMap 可以按照访问顺序排序