目录
一.简介
二.数据结构
三.具体使用
四.基础知识
五.源码分析
六.源码总结
七.与jdk1.8的区别
八.额外补充：关于HashMap的其他问题
九.总结
一 简介
• 类定义
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
主要介绍
• HashMap的实现在JDK1.7和JDK1.8差别较大
二 数据结构
• 具体描述
HashMap 采用的数据结构 : 数组(主) + 单链表(副)
该数据结构方式也称：拉链法（链路法）‘
• 存储流程
• 数组元素 & 链表节点的 实现类
HashMap中的数组元素&链表节点 采用 Entry 类实现
1.HashMap的本质=1个存储Entry类对象的数组+多个单链表
2.Entry对象本质=1个映射(键-值)，属性包括：键(key)、值(value) & 下1节点(next)=单链表的指针=也是一个Entry对象，用于解决hash冲突
三 具体使用
• 主要使用的API（方法、函数）
V get(Object key); // 获得指定键的值
V put(K key, V value); // 添加键值对
void putAll(Map<? extends K, ? extends V> m); // 将指定Map中的键值对 复制到 此Map中
V remove(Object key); // 删除该键值对
boolean containsKey(Object key); // 判断是否存在该键的键值对；是 则返回true
boolean containsValue(Object value); // 判断是否存在该值的键值对；是 则返回true
Set<K> keySet(); // 单独抽取key序列，将所有key生成一个Set
Collection<V> values(); // 单独value序列，将所有value生成一个Collection
void clear(); // 清除哈希表中的所有键值对
int size(); // 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
boolean isEmpty(); // 判断HashMap是否为空；size == 0时 表示为 空
•使用
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
public class HashMapTest {
public static void main(String[] args) {
/**
* 1. 声明1个 HashMap的对象
*/
Map<String, Integer> map = new HashMap<String, Integer>();
/**
* 2. 向HashMap添加数据（成对 放入 键 - 值对）
*/
map.put("Android", 1);
map.put("Java", 2);
map.put("iOS", 3);
map.put("数据挖掘", 4);
map.put("产品经理", 5);
/**
* 3. 获取 HashMap 的某个数据
*/
System.out.println("key = 产品经理时的值为：" + map.get("产品经理"));
/**
* 4. 获取 HashMap 的全部数据：遍历HashMap
* 核心思想：
* 步骤1：获得key-value对（Entry） 或 key 或 value的Set集合
* 步骤2：遍历上述Set集合(使用for循环 、 迭代器（Iterator）均可)
* 方法共有3种：分别针对 key-value对（Entry） 或 key 或 value
*/
// 方法1：获得key-value的Set集合 再遍历
System.out.println("方法1");
// 1. 获得key-value对（Entry）的Set集合
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
// 2. 遍历Set集合，从而获取key-value
// 2.1 通过for循环
for(Map.Entry<String, Integer> entry : entrySet){
System.out.print(entry.getKey());
System.out.println(entry.getValue());
}
System.out.println("----------");
// 2.2 通过迭代器：先获得key-value对（Entry）的Iterator，再循环遍历
Iterator iter1 = entrySet.iterator();
while (iter1.hasNext()) {
// 遍历时，需先获取entry，再分别获取key、value
Map.Entry entry = (Map.Entry) iter1.next();
System.out.print((String) entry.getKey());
System.out.println((Integer) entry.getValue());
}
// 方法2：获得key的Set集合 再遍历
System.out.println("方法2");
// 1. 获得key的Set集合
Set<String> keySet = map.keySet();
// 2. 遍历Set集合，从而获取key，再获取value
// 2.1 通过for循环
for(String key : keySet){
System.out.print(key);
System.out.println(map.get(key));
}
System.out.println("----------");
// 2.2 通过迭代器：先获得key的Iterator，再循环遍历
Iterator iter2 = keySet.iterator();
String key = null;
while (iter2.hasNext()) {
key = (String)iter2.next();
System.out.print(key);
System.out.println(map.get(key));
}
// 方法3：获得value的Set集合 再遍历
System.out.println("方法3");
// 1. 获得value的Set集合
Collection valueSet = map.values();
// 2. 遍历Set集合，从而获取value
// 2.1 获得values 的Iterator
Iterator iter3 = valueSet.iterator();
// 2.2 通过遍历，直接获取value
while (iter3.hasNext()) {
System.out.println(iter3.next());
}
}
}
// 注：对于遍历方式，推荐使用针对 key-value对（Entry）的方式：效率高
// 原因(此处存在疑问：看了源码keySet、valueSet相对于entrySet只多了一个获取值得操作)：
// 1. 对于 遍历keySet 、valueSet，实质上 = 遍历了2次：1 = 转为 iterator 迭代器遍历、2 = 从 HashMap 中取出 key 的 value 操作（通过 key 值 hashCode 和 equals 索引）
// 2. 对于 遍历 entrySet ，实质 = 遍历了1次 = 获取存储实体Entry（存储了key 和 value ）
四 基础知识
• HashMap中的重要参数(变量)
• 具体介绍
/*
*1.容量(capacity):HashMap中数组的长度
*a.容量范围：必须是2的幂 & <最大容量（2的30次方）
*b.初始容量=哈希表创建时的容量
*默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4 = 16
*/
static final int DEFAULT_INITIAL_CAPACITY =1 << 4;
//最大容量 = 2的30次方(若传入的容量过大，将被最大值替换)
static final int MAXIMUM_CAPACITY =1 <<30;
/*
*2.加载因子(load factor)：限制HashMap的容量，当容量超过 负载因子 * 哈希表的现有容量 * <= 添加元素后的容量，扩容
*/
//实际加载因子
final float loadFactor;
//默认加载因子=0.75
static final float DEFAULT_LOAD_FACTOR =0.75f;
//3.扩容阈值(threshold):当哈希表的大小 >=扩容阈值 时，就会扩容哈希表
//扩容阈值 = 容量 * 加载因子
int threshold;
//HashMap 的实现方式 = 拉链法，Entry数组上的每个元素本质上是一个单链表
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//HashMap的大小，即 HashMap中存储的键值对的数量
transient int size;
• 详细说明 加载因子
五 源码分析
• 声明一个HashMap的对象
/**
* 函数使用原型
*/
Map<String,Integer> map = new HashMap<String,Integer>();
/**
* 源码分析：主要是HashMap的构造函数 = 4个
* 仅贴出关于HashMap构造函数的源码
*/
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable{
// 省略上节阐述的参数
/**
* 构造函数1：默认构造函数（无参）
* 加载因子 & 容量 = 默认 = 0.75、16
*/
public HashMap() {
// 实际上是调用构造函数3：指定“容量大小”和“加载因子”的构造函数
// 传入的指定容量 & 加载因子 = 默认
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 构造函数2：指定“容量大小”的构造函数
* 加载因子 = 默认 = 0.75 、容量 = 指定大小
*/
public HashMap(int initialCapacity) {
// 实际上是调用指定“容量大小”和“加载因子”的构造函数
// 只是在传入的加载因子参数 = 默认加载因子
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 构造函数3：指定“容量大小”和“加载因子”的构造函数
* 加载因子 & 容量 = 自己指定
*/
public HashMap(int initialCapacity, float loadFactor) {
// HashMap的最大容量只能是MAXIMUM_CAPACITY，哪怕传入的 > 最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 设置 加载因子
this.loadFactor = loadFactor;
// 设置 扩容阈值 = 初始容量
// 注：此处不是真正的阈值，是为了扩展table，该阈值后面会重新计算，下面会详细讲解
threshold = initialCapacity;
init(); // 一个空方法用于未来的子对象扩展
}
/**
* 构造函数4：包含“子Map”的构造函数
* 即 构造出来的HashMap包含传入Map的映射关系
* 加载因子 & 容量 = 默认
*/
public HashMap(Map<? extends K, ? extends V> m) {
// 设置容量大小 & 加载因子 = 默认
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
// 该方法用于初始化 数组 & 阈值，下面会详细说明
inflateTable(threshold);
// 将传入的子Map中的全部元素逐个添加到HashMap中
putAllForCreate(m);
}
}
注：
1.此处仅用于接收初始容量大小(capacity)、加载因子(load factor),但仍无真正初始化哈希表，及初始化存储数组table；
2.此处结论：真正初始化哈希表(初始化存储数组table)是在第一次添加键值对时，即 第一次 调用 put()时
• 向HashMap添加数据
详细流程如下：
• put源码
/**
* 源码分析：主要分析： HashMap的put函数
*/
public V put(K key, V value)
（分析1）// 1. 若 哈希表未初始化（即 table为空)
// 则使用 构造函数时设置的阈值(即初始容量) 初始化 数组table
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 2. 判断key是否为空值null
（分析2）// 2.1 若key == null，则将该键-值 存放到数组table 中的第1个位置，即table [0]
// （本质：key = Null时，hash值 = 0，故存放到table[0]中）
// 该位置永远只有1个value，新传进来的value会覆盖旧的value
if (key == null)
return putForNullKey(value);
（分析3） // 2.2 若 key ≠ null，则计算存放数组 table 中的位置（下标、索引）
// a. 根据键值key计算hash值
int hash = hash(key);
// b. 根据hash值 最终获得 key对应存放的数组Table中位置
int i = indexFor(hash, table.length);
// 3. 判断该key对应的值是否已存在（通过遍历 以该数组元素为头结点的链表 逐个判断）
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
（分析4）// 3.1 若该key已存在（即 key-value已存在 ），则用 新value 替换 旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue; //并返回旧的value
}
}
modCount++;
（分析5）// 3.2 若 该key不存在，则将“key-value”添加到table中
addEntry(hash, key, value, i);
return null;
}
• 初始化哈希表-初始化数组
/**
* 函数使用原型
*/
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
/**
* 源码分析：inflateTable(threshold);
*/
private void inflateTable(int toSize) {
// 1. 将传入的容量大小转化为：>传入容量大小的最小的2的次幂
// 即如果传入的是容量大小是19，那么转化后，初始化容量大小为32（即2的5次幂）
int capacity = roundUpToPowerOf2(toSize);->>分析1
// 2. 重新计算阈值 threshold = 容量 * 加载因子
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 3. 使用计算后的初始容量（已经是2的次幂） 初始化数组table（作为数组长度）
// 即 哈希表的容量大小 = 数组大小（长度）
table = new Entry[capacity]; //用该容量初始化table
initHashSeedAsNeeded(capacity);
}
/**
* 分析1：roundUpToPowerOf2(toSize)
* 作用：将传入的容量大小转化为：>传入容量大小的最小的2的幂
* 特别注意：容量大小必须为2的幂，该原因在下面的讲解会详细分析
*/
private static int roundUpToPowerOf2(int number) {
//若 容量超过了最大值，初始化容量设置为最大值 ；否则，设置为：>传入容量大小的最小的2的次幂
return number >= MAXIMUM_CAPACITY ?
MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
• PUT源码
/**
* 函数使用原型
*/
if (key == null)
return putForNullKey(value);
/**
* 源码分析：putForNullKey(value)
*/
private V putForNullKey(V value) {
// 遍历以table[0]为首的链表，寻找是否存在key==null 对应的键值对
// 1. 若有：则用新value 替换 旧value；同时返回旧的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++;
// 2 .若无key==null的键，那么调用addEntry（），将空键 & 对应的值封装到Entry中，并放到table[0]中
addEntry(0, null, value, 0);
// 注：
// a. addEntry（）的第1个参数 = hash值 = 传入0
// b. 即 说明：当key = null时，也有hash值 = 0，所以HashMap的key 可为null
// c. 对比HashTable，由于HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
// d. 此处只需知道是将 key-value 添加到HashMap中即可，关于addEntry（）的源码分析将等到下面再详细说明，
return null;
}
•分析
为什么不直接采用经过hashCode()处理的哈希吗作为存储数组table的下标位置？
为什么采用 哈希码 & (数组长度-1) 计算数组下标？
引用:https://blog.csdn.net/carson_ho/article/details/79373026
