Java 的 HashMap 可以说是用的最多、问的最多的一个 Map Collection 了。HashMap 是非同步的，即线程不安全。HashMap 允许存放的 key 为 null，但并不保证映射的顺序，也不保证这个顺序随时间保持不变。 本文对 HashMap 的代码分析基于 JDK 1.8 public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable 我们可以先从 HashMap 底层使用的数据结构了解 HashMap。 哈希表 + 链表 / 红黑树 static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; // ... } /** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two....

红黑树（Red-Black Tree）是一种自平衡的二叉查找树（Binary Search Tree, BST），由于基于二叉查找树（并不是基于 AVL 树），因此它是有序的。它出现于 1978 年 Leo J. Guibas 和 Robert Sedgewick 的一篇论文。 红黑树和 AVL 树很像，都是为了让二叉查找树能保持平衡，不会退化成链表，让查找时间复杂度能够稳定在 O(log(n))。 相比 AVL 树，红黑树牺牲了部分平衡性来，来减少插入 / 删除操作的旋转次数。因此插入性能红黑树会比 AVL 树快，但由于平衡性不如 AVL 树，当拥有相同数量的节点时，树的层数可能会比 AVL 树高，查询效率也不如 AVL 树。 由于红黑树的结构比较复杂，因此它也比较难理解，但我们可以借助 2-3-4 树来理解它。 Perfect Balance 的 2-3-4 树 介绍 2-3-4 树的资料可能比较少，由于 2-3-4 树的图画起来比较麻烦，为了偷懒本文选取了 Sedgewick 介绍 LLRB Tree（左倾红黑树） 的 PPT 中的一些图来做说明，该 PPT 链接放在本文末尾参考部分。 2-3-4 树也是一颗自平衡的树，但它的节点比较特殊，可以分为以下 3 种节点： 2-node：普通的树节点，可存放一个数据，最多有两个子节点 3-node：能存放两个数据的节点，最多能有三个子节点 4-node：能存放三个数据的节点，最多能有四个子节点 它们的结构图示如下（该图来自 Sedgewick 的 PPT 第 12 页）： 该图中对子节点的连接位置进行描述的只有 3 节点，不过 4 节点与子节点连接方式其实也是一样的，子节点的连接决定于子节点存放的数据的大小范围和父节点的存放的数据的大小。...

在 Java Collections Framework 中有两个被遗弃的 List 实现类 —— Vector 和 Stack。 Vector 通过实现 AbstractList<E> 接口来成为 Java Collections Framework List 接口的一员，而 Stack 直接继承于 Vector。 public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable public class Stack<E> extends Vector<E> 与 ArrayList 类似的 Vector 如果希望了解 ArrayList 的底层结构可阅读另一篇文章 ArrayList 与 LinkedList 底层结构 与 ArrayList 一样，Vector 的底层结构也是 Object 数组 elementData，通过 elementCount 来表示 Vector 存储的元素个数，但与 ArrayList 不同的是，ArrayList 创建时不指定容器个数时，elementData 是一个长度为 0 的数组，只有在第一次添加元素的时候才会创建一个长度为 10 的数组，而 Vector 则是在构造方法中调用另一个构造方法直接为 elementData 创建一个长度为 10 的数组。...

在 Java 中，数组可用来存储相同类型的多个数据，但由于长度不可变，在某些场景下使用比较局限。当我们希望使用类似数组的结构来存储未知个数的元素时，可以使用 ArrayList<E> 和 LinkedList<E>，它们都是 Java Collection Framework 的成员，相比普通的数组，它们提供了更多的操作来方便我们开发。由于底层使用的数据结构不同，它们也经常被拿来做比较。 继承关系 ArrayList 属于 List<E> 接口中的一个 可变长数组 实现，直接 extends AbstractList<E> abstract 类。其继承关系如下： public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable LinkedList 直接 extends AbstractSequentialList<E> abstract 类，间接 extends AbstractList<E>，由于 LinkedList 也实现了 Deque<E> 接口，所以它属于 List<E> 和 Queue<E> 接口的实现。 public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable ArrayList 底层结构 对于 ArrayList，Java API 对它的第一句描述为 “Resizable-array implementation of the List interface”。其底层存储元素的结构为 Object 数组。...

字节码（Byte Code） 学习 Java 的都知道，我们所编写的 .java 代码文件通过编译将会生成 .class 文件，最初的方式就是通过 JDK 的 javac 指令来编译，再通过 java 命令执行 main 方法所在的类，从而执行我们的 Java 程序。而在这中间所生成的 .class 文件中的内容，就是 JVM 可以处理运行的字节码（Byte Code），它由 JVM 解释为对应系统可运行的机器指令，这也是我们的 Java 程序能够做到一处编译处处执行的原理。 对于 Java 开发人员来说，平时需要阅读 Byte Code 的场景比较少，但和阅读框架源码能够了解到框架的设计思路一样，阅读 Java Byte Code 也有利于我们理解 Java 一些深层的东西，提高我们解决问题的能力。能够阅读 Byte Code 也有利于我们去理解 Kotlin 或其它运行在 JVM 上的语言，是如何扩展 Java 所没有的特性或语法糖。 字节码文件结构 public class Hello { public static void main(String[] args) { int a = 1; int b = 1; int c = add(a, b); System....