首先看结构图

HashMap继承了AbstractMap 实现了 Serializable，Cloneable，Map

继承和实现

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

参考: https://juejin.im/post/5cb163bee51d456e46603dfe 好文章 ！！ 在Java中，HashMap的实现采用了（数组 + 链表 + 红黑树）的复杂结构，数组的一个元素又称作桶。 在添加元素时，会根据hash值算出元素在数组中的位置，如果该位置没有元素，则直接把元素放置在此处，如果该位置有元素了，则把元素以链表的形式放置在链表的尾部。 当一个链表的元素个数达到一定的数量（且数组的长度达到一定的长度）后，则把链表转化为红黑树，从而提高效率。 数组的查询效率为O(1)，链表的查询效率是O(k)，红黑树的查询效率是O(log k)，k为桶中的元素个数，所以当元素数量非常多的时候，转化为红黑树能极大地提高效率。

在前面一直搞混淆 size和capacity的含义 HashMap中的size和capacity之间的区别其实解释起来也挺简单的。我们知道，HashMap就像一个“桶”，那么capacity就是这个桶“当前”最多可以装多少元素，而size表示这个桶已经装了多少元素。

我们定义了一个新的HashMap，并想其中put了一个元素。那么输出结果为：capacity : 16、size : 1

变量

HashMap中的size和capacity之间的区别其实解释起来也挺简单的。我们知道，HashMap就像一个“桶”，那么capacity就是这个桶“当前”最多可以装多少元素，而size表示这个桶已经装了多少元素。

// 序列化ID private static final long serialVersionUID = 362498820763181265L; /** * 默认的初始化容量为 * 左移运算符 10000 * 简化运算是 1*(2^4) */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * 最大的容量是 1*(2^30) */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 默认的加载因子是 0.75 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 链表变成红黑树的阈值为8 */ static final int TREEIFY_THRESHOLD = 8; /** * 红黑树变成链表的阈值为6 */ static final int UNTREEIFY_THRESHOLD = 6; /** * "大桶" （table[]） 变成红黑树的最小容量为64 */ static final int MIN_TREEIFY_CAPACITY = 64; /** * table 简称 哈希桶 * Node数组 组成 */ transient Node<K,V>[] table; /** * 将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。 */ transient Set<Map.Entry<K,V>> entrySet; /** * 实际容量大小 在前面已说明！！！ */ transient int size; /** * 用于快速失败机制 fast-fail * 记录HashMap结构修改的次数 */ transient int modCount; /** * 阈值 * 当桶达到了阈值，会进行扩容 threshold = capacity * loadFactor */ int threshold; /** * 加载因子 又称 负载因子 */ final float loadFactor; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

关于tableSizeFor（）方法的讲解：详情请看： https://blog.csdn.net/fan2012huan/article/details/51097331

构造函数 4个

/** * 初始容量，加载因子 */ public HashMap(int initialCapacity, float loadFactor) { // 当初始容量 < 0 抛异常 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 当初始容量 > 容量最大值 初始容量 = 容量最大值 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 加载因子<=0 or 输出的加载因子不是数字 抛出异常 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; // 阈值 = 如下 this.threshold = tableSizeFor(initialCapacity); } /** *由此可以看到，当在实例化HashMap实例时， 如果给定了initialCapacity，由于HashMap的capacity都是2的幂， 因此这个方法用于找到大于等于initialCapacity的最小的2的幂 （initialCapacity如果就是2的幂，则返回的还是这个数）。 下面分析这个算法： 首先，为什么要对cap做减1操作。int n = cap - 1; 这是为了防止，cap已经是2的幂。如果cap已经是2的幂， 又没有执行这个减1 操作，则执行完后面的几条无符号右移操作之后， 返回的capacity将是这个cap的2倍。如果不懂，要看完后面的几个无符号右移 之后再回来看看。 下面看看这几个无符号右移操作： 如果n这时为0了（经过了cap-1之后），则经过后面的几次无符号右移依然是 0， 最后返回的capacity是1（最后有个n+1的操作）。 这里只讨论n不等于0的情况。 */ static final int tableSizeFor(int cap) { // 扩容门槛为传入的初始容量往上取最近的2的n次方 int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } /** * 传入初始容量大小 */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 无参构造器 */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * */ public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } /** * */ final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { // 获取传入Map的实际容量大小 int s = m.size(); // 实际容量大小 > 0 if (s > 0) { // 且 table == null if (table == null) { // pre-size // 算出所需容量 //+1是因为小数相除，基本都不会是整数， //容量大小不能为小数的，后面转换为int， //多余的小数就要被丢掉，所以+1，例如， //map实际长度22，22/0.75=29.3,所需要的容量肯定为30， //有人会问如果刚刚好除得整数呢，除得整数的话，容量大小多1也没什么影响 float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); // 所需要的容量 > 阈值 if (t > threshold) // 阈值 如上讲解 threshold = tableSizeFor(t); } // 实际容量 > 阈值 扩容 else if (s > threshold) resize(); // 然后 进行PUT操作 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }

Node节点

//定义一个静态类 类是Node<K,V> static class Node<K,V> implements Map.Entry<K,V> { //成员变量有 //hash值 final int hash; //K final K key; //V V value; //有一个相同的Node类 定义为next Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } //获取K值 public final K getKey() { return key; } //获取value值 public final V getValue() { return value; } //重写toString方法 key=value public final String toString() { return key + "=" + value; } //获取hashcode值 调用Object的方法 //hashcode最终的值为 k的hash值 的 V的hash值的次方 public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } //定义一个oldValue 把当前对象的value赋值给oldValue //把新值赋值给当前的value //返回之前未改变的value值 public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { //对象o是否==this yes 返回true if (o == this) return true; //对象o 是否是 Map.Entry //因为Node是实现了Map的Entry if (o instanceof Map.Entry) { //对象o赋值给E Map.Entry<?,?> e = (Map.Entry<?,?>)o; //当前的key与对象的k是否相等 //当前的v与对象的o是否相等 if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }

扩容

参考： https://blog.csdn.net/u013132758/article/details/89181005

/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */ final Node<K,V>[] resize() { // 没插入值之前的table 定义为oldTab Node<K,V>[] oldTab = table; // 旧容量 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧扩容门槛 int oldThr = threshold; // 新的容量 新的阈值为 0 int newCap, newThr = 0; // 旧容量 > 0 if (oldCap > 0) { // 旧容量 >= 最大容量 if (oldCap >= MAXIMUM_CAPACITY) { // 阈值为Integer的最大值 threshold = Integer.MAX_VALUE; // 且返回旧容量 return oldTab; } /** * 标记** * 旧容量*2 < 最大容量值 && 旧容量 >= 默认的初始容量 * 新容量 = 旧容量 * 2 * 新阈值 = 旧阈值 * 2 */ else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } // 旧容量 = 0 且 旧阈值 > 0 什么时候会出现这种情况？ // 如果oldCap<0，但是已经初始化了 // 像把元素删除完之后的情况，那么它的临界值肯定还存在 // 新容量 = 旧阈值 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // 首次初始化 // 旧容量 = 0 且 旧阈值 = 0 HashMap的懒加载 else { // zero initial threshold signifies using defaults // 新容量 = 默认初始容量 newCap = DEFAULT_INITIAL_CAPACITY; // 阈值 = 加载因子 * 默认初始容量 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 新阈值 == 0 // 此处的if为上面标记##的补充，也就是初始化时容量小于默认值16的 // 此时newThr没有赋值 // 新的阈值 赋值 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // 当前阈值 = 新阈值 // 把上面各种情况分析出的临界值，在此处真正进行改变，也就是容量和临界值都改变了。 threshold = newThr; //表示忽略该警告 @SuppressWarnings({"rawtypes","unchecked"}) // 扩容好的table 赋值给 newTab Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // newTab 取代当前的table table = newTab; // 以前的table 不为null if (oldTab != null) { // 遍历旧容量 for (int j = 0; j < oldCap; ++j) { // 定义临时节点e Node<K,V> e; // 当前节点不为null if ((e = oldTab[j]) != null) { // 令当前节点为null oldTab[j] = null; // 如果当前节点的下一个节点为null // 即当前节点为尾节点 if (e.next == null) // 当前节点 赋值到 newTab[]位置上去 newTab[e.hash & (newCap - 1)] = e; // 如果不是尾节点 且 是树结构 else if (e instanceof TreeNode) // 如果第一个元素是树节点，则把这颗树打散成两颗树插入到新桶中去 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 不是尾节点 且 不是树结构 else { // 如果这个链表不止一个元素且不是一颗树 // 则分化成两个链表插入到新的桶中去 // 比如，假如原来容量为4，3、7、11、15这四个元素都在三号桶中 // 现在扩容到8，则3和11还是在三号桶，7和15要搬移到七号桶中去 // 也就是分化成了两个链表 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // (e.hash & oldCap) == 0的元素放在低位链表中 // 比如，3 & 4 == 0 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { // (e.hash & oldCap) != 0的元素放在高位链表中 // 比如，7 & 4 != 0 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 遍历完成分化成两个链表了 // 低位链表在新桶中的位置与旧桶一样（即3和11还在三号桶中） if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 高位链表在新桶中的位置正好是原来的位置加上旧容量 // （即7和15搬移到七号桶了） if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

在扩容之前，我们要考虑如下这几种情况：

当旧容量 = null ，旧容量 = 0 旧阈值 = 当前的阈值 新容量，新阈值 = 0

（1）当旧容量 > 0

已初始化过容器

1. 旧容量>最大容量值 阈值 = Integer的最大值 2. 旧容量*2 < 最大容量值 && 旧容量 > 默认初始容量 新容量 = 旧容量*2 （注意：是先执行了这语句，才进行2的判断的。） 新阈值 = 旧阈值*2 还有一种情况 ：也就是初始化容量小于默认值16的 此时新阈值还没有赋值 注：跳转到（4）

（2）旧容量=0,且旧阈值>0

如果阈值>0,已初始化容量。 像把元素删除完之后的情况，那么它的临界值肯定还存在

新容量 = 旧阈值

（3）旧容量 = 0 且 旧阈值 = 0

HashMap的懒加载,首次初始化

新容量 = 默认初始化容量 新阈值 = 默认加载因子*默认初始化容量

（4）新阈值 = 0 也就是初始化容量小于默认值16的 此时新阈值还没有赋值

注：接（1）中的 2

新的阈值 = 新容量 * 加载因子（新容量<最大容量值 && 阈值 < 最大容量）

（5） 新建一个新容量的数组 容量 新的哈希桶取代当前的table

1. 如果旧数组不为空，则搬移元素， 遍历旧桶 1.1 如果桶中第一个元素不为空 清空旧桶，便于GC回收 1.1.1 旧桶中只有一个元素 则计算它在新桶中的位置并把它搬移到新桶中 ，e.hash & (newCap - 1)并不等于j 因为每次都扩容两倍，所以这里的第一个元素搬移到新桶的时候新桶肯定还没有元素 1.1.2 旧桶不止一个元素，且是红黑树 把这棵树 打散成2颗树插入到新桶中去 1.1.3 旧桶不止一个元素，是链表 意味着是链表，把链表分化成2个链表插入到新桶中去 低位链表在新桶中的位置与旧桶一样 高位链表在新桶中的位置正好是原来的位置加上旧容量

Put

/** put值 K,V hash（key），k，v，false，ture */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * evict： 驱逐；逐出 * absent： 缺席 */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 桶数量为0 则扩容 因为HashMap懒加载 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // (n - 1) & hash 计算元素在哪个桶中 // 如果这个桶中还没有元素，则把这个元素放在桶中的第一个位置 if ((p = tab[i = (n - 1) & hash]) == null) // 新建一个节点放入桶中 tab[i] = newNode(hash, key, value, null); // 桶中有元素存在 else { Node<K,V> e; K k; // 如果桶中第一个元素的key与待插入元素的key相同，保存到e中用于后续修改value值 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 桶中有元素 且是红黑树结果 else if (p instanceof TreeNode) // 如果第一个元素是树节点，则调用树节点的putTreeVal插入元素 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 桶中有元素 且为链表 else { // 遍历这个桶对应的链表，binCount用于存储链表中元素的个数 for (int binCount = 0; ; ++binCount) { // 如果链表遍历完了都没有找到相同key的元素，说明该key对应的元素不存在，则在链表最后插入一个新节点 if ((e = p.next) == null) { //如果找到尾部，则表明添加的key-value没有重复，在尾部进行添加 p.next = newNode(hash, key, value, null); // 如果插入新节点后链表长度大于8，则判断是否需要树化，因为第一个元素没有加到binCount中，所以这里-1 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果链表中有重复的key，e则为当前重复的节点，结束循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 如果找到了对应key的元素 if (e != null) { // existing mapping for key // 记录当前的V值 V oldValue = e.value; // 判断是否需要替换旧值 if (!onlyIfAbsent || oldValue == null) // 替换旧值为新值 e.value = value; // 在节点被访问后做点什么事，在LinkedHashMap中用到 afterNodeAccess(e); // 返回旧值 return oldValue; } } // Map结构改造 ++modCount; // 实际容量 > 阈值 扩容 if (++size > threshold) resize(); // afterNodeInsertion(evict); return null; }

添加元素

1. 桶是否为null，或者长度为0 初始化，或者已经初始化过 删除完了。 HashMap的懒加载

扩容

2. 通过计算将元素(node)放入哪个桶 如果这个桶中没有元素

根据key计算出在数组中存储的下标 新建一个节点放入桶中 元素放到桶中的第一个位置

3.桶中有元素存在

3.1 桶中第一个元素的key与待插入元素的key相同，保存到e中用于后续修改V值 3.2 桶中第一个元素的key与待插入元素的key不相同 且是红黑树结构. 则调用树节点的putTreeVal()寻找元素或插入树节点。 为红黑树的节点，则在红黑树中进行添加，如果该节点已经存在，则返回该节点（不为null）， 该值很重要，用来判断put操作是否成功，如果添加成功返回null 3.3 桶中第一个元素的key与待插入元素的key不相同 且是链表结构： >8: 树化 否：尾部进行添加 添加元素>8? 遍历链表，查询链表元素中是否有重复的key值 是： 待插入元素替换当前元素

提出问题

1 什么是序列化接口（Serializable）？

详细请参考: https://www.jianshu.com/p/a54d30b92690 可以很明显的看到它是一个序列化的 接口 这个Serializable接口，以及相关的东西，全部都在 Java io 中。 一想到序列化，什么是序列化？ 根据官方的解释： 序列化：就是将对象的当前状态写入字节流，用于保存或传输的过程 序列化：把对象转换为字节序列的过程称为对象的序列化。

反序列化：从字节流中恢复对象，是序列化的逆过程。 反序列化：把字节序列恢复为对象的过程称为对象的反序列化。

序列化（Serializable）是指把 Java 对象字节序列的过程，就是说将原本保存在内存中的对象，保存到硬盘（或数据库等）中。当需要使用时，再反序列化恢复到内存中使用。

/** * 实现了序列化接口的学生类 */ public class Student implements Serializable { private String name; private char sex; private int year; private double gpa; public Student() { } public Student(String name,char sex,int year,double gpa) { this.name = name; this.sex = sex; this.year = year; this.gpa = gpa; } public void setName(String name) { this.name = name; } public void setSex(char sex) { this.sex = sex; } public void setYear(int year) { this.year = year; } public void setGpa(double gpa) { this.gpa = gpa; } public String getName() { return this.name; } public char getSex() { return this.sex; } public int getYear() { return this.year; } public double getGpa() { return this.gpa; } } /** * 学生信息应用类 */ public class UserStudent { public static void main(String[] args) { Student st = new Student("Tom",'M',20,3.6); File file = new File("/Users/sschen/Documents/student.txt"); try { file.createNewFile(); } catch(IOException e) { e.printStackTrace(); } try { //Student对象序列化过程 FileOutputStream fos = new FileOutputStream(file); ObjectOutputStream oos = new ObjectOutputStream(fos); oos.writeObject(st); oos.flush(); oos.close(); fos.close(); //Student对象反序列化过程 FileInputStream fis = new FileInputStream(file); ObjectInputStream ois = new ObjectInputStream(fis); Student st1 = (Student) ois.readObject(); System.out.println("name = " + st1.getName()); System.out.println("sex = " + st1.getSex()); System.out.println("year = " + st1.getYear()); System.out.println("gpa = " + st1.getGpa()); ois.close(); fis.close(); } catch(ClassNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } } }

2 instanceof？

答： java中的instanceof运算符是在运行时指出对象是否是特定类的一个实例。 A instanceof B 指的是：A是否是B的实例 或者A是否是B的子类 （其中Tom继承了Person） public static void main(String[] args){ People p = new People(); Tom t = new Tom(); System.out.println(p instanceof Person); System.out.println(p instanceof Tom); System.out.println(t instanceof Person); System.out.println(t instanceof People); } 运行结果： true false true true

3 关键词transient (短暂的，暂时的)

import java.io.Serializable; // 参与序列化只需要实现 Serializable 接口即可 public class Account implements Serializable { // Java 的序列化机制通过判断以下 ID 来进行版本比对，本处使用默认 private static final long serialVersionUID = 1L; private Long accountId; private String username; // transient 修饰： private transient String password; private transient double balance; public static int staticVar; public Account(Long accountId, String username, String password, double balance) { super(); this.accountId = accountId; this.username = username; this.password = password; this.balance = balance; } public String toString() { return "Account [accountId=" + accountId + ", username=" + username + ", password=" + password + ", balance=" + balance + "]"; } } import java.io.*; public class Demo01 { public static void main(String[] args) { // 此处需要改为你要存入的地址，注意 Win 下地址中的 \ 需要转义 String src = "/Users/kingcos/Desktop/demo.object"; Account kingcos = new Account(62278888L, "kingcos", "123456", 1000.0); Account.staticVar = 11; System.out.println("序列化之前："); System.out.println(kingcos); System.out.println("staticVar = " + Account.staticVar); write(kingcos, src); Account.staticVar = 22; Account newKingcos = read(src); System.out.println("序列化之后："); System.out.println(newKingcos); System.out.println("staticVar = " + Account.staticVar); } static void write(Account acc, String src) { OutputStream os = null; ObjectOutputStream oos = null; try { os = new FileOutputStream(src); oos = new ObjectOutputStream(os); // 写入 oos.writeObject(acc); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } finally { try { oos.flush(); oos.close(); } catch (IOException e) { e.printStackTrace(); } } } static Account read(String src) { Account acc = null; InputStream is = null; ObjectInputStream ois = null; try { is = new FileInputStream(src); ois = new ObjectInputStream(is); // 读取 acc = (Account) ois.readObject(); } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } catch (ClassNotFoundException e) { e.printStackTrace(); } finally { try { ois.close(); } catch (IOException e) { e.printStackTrace(); } } return acc; } }

结果显示：

// Console: // 序列化之前： // Account [accountId=62278888, username=kingcos, password=123456, balance=1000.0] // staticVar = 11 // 序列化之后： // Account [accountId=62278888, username=kingcos, password=null, balance=0.0]

静态变量不管是不是transient关键字修饰，都不会被序列化