HashMap底层结构与JVM内存模型 - 阿里技术面试

1. HashMap底层结构

1.1 基本解释

在 Java 中，HashMap 是一个基础模块，HashMap由数组和链表组成的。

数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。

如果定位到的数组位置不含链表那么对于查找，添加等操作很快，仅需一次寻址即可。

如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增。

对于查找操作来讲，仍需遍历链表，然后通过 key 对象的 equals 方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

1.2 代码解释

HashMap 的主干是一个 Entry 数组。Entry 是 HashMap 的基本组成单元，每一个 Entry 包含一个 键值对。

代码如下：

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

而 Entry 是 Hashmap 中的静态类

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
        int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
  ...
}

1.3 需要注意

  1. HashMap 有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值，initialCapacity默认为16，loadFactory默认为0.75。
  2. 当发生哈希冲突并且 size 大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的 Entry 数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。

2. JVM内存模型

Java内存模型（Java Memory Model）就是一种符合内存模型规范的，屏蔽了各种硬件和操作系统的访问差异的，保证了Java程序在各种平台下对内存的访问都能保证效果一致的机制及规范。

2.1 五大内存区

2.1.1 程序计数器

程序计数器是一块很小的内存空间，它是线程私有的，可以认作为当前线程的行号指示器。

2.1.2 Java栈

同计数器也为线程私有，生命周期与相同，就是我们平时说的栈，栈描述的是Java方法执行的内存模型。

每个方法被执行的时候都会创建一个栈帧用于存储局部变量表，操作栈，动态链接，方法出口等信息。每一个方法被调用的过程就对应一个栈帧在虚拟机栈中从入栈到出栈的过程。

栈帧大小确定时间: 编译期确定，不受运行期数据影响。

2.1.3 本地方法栈

本地方法栈是与虚拟机栈发挥的作用十分相似,区别是虚拟机栈执行的是 Java 方法(也就是字节码)服务，而本地方法栈则为虚拟机使用到的 native 方法服务，可能底层调用的 C/C++，我们打开 jdk 安装目录可以看到也有很多用 C 编写的文件，就是 native 方法所调用的 C 代码。

2.1.4 堆

对于大多数应用来说，堆是 Java 虚拟机管理内存最大的一块内存区域，因为堆存放的对象是线程共享的，所以多线程的时候也需要同步机制。

Java 虚拟机规范对这块的描述是：所有对象实例及数组都要在堆上分配内存，但随着 JIT 编译器的发展和逃逸分析技术的成熟，这个说法也不是那么绝对，但是大多数情况都是这样的。

2.1.5 方法区

方法区同堆一样，是所有线程共享的内存区域，为了区分堆，又被称为非堆。

用于存储已被虚拟机加载的类信息、常量、静态变量，如static修饰的变量加载类的时候就被加载到方法区中。

2.2 对象的内存布局

HotSpot虚拟机，对象在内存中存储的布局分为：

  1. 对象头
  2. 实例数据
  3. 对齐填充

2.2.1 对象头

第一部分用于存储对象自身的运行时数据，如哈希码（HashCode）、GC 分代年龄、锁状态标志、线程持有的锁、偏向线程 ID、偏向时间戳、对象分代年龄，这部分信息称为“Mark Word”；Mark Word 被设计成一个非固定的数据结构以便在极小的空间内存储尽量多的信息，它会根据自己的状态复用自己的存储空间。

第二部分是类型指针，即对象指向它的类元数据的指针，虚拟机通过这个指针来确定这个对象是哪个类的实例；

如果对象是一个 Java 数组，那在对象头中还必须有一块用于记录数组长度的数据。因为虚拟机可以通过普通 Java 对象的元数据信息确定 Java 对象的大小，但是从数组的元数据中无法确定数组的大小。

2.2.2 实例数据

存放对象程序中各种类型的字段类型，不管是从父类中继承下来的还是在子类中定义的。 分配策略：相同宽度的字段总是放在一起，比如 double 和 long。

2.2.3 对齐填充

这部分没有特殊的含义，仅仅起到占位符的作用满足 JVM 要求。

3. Java中volatile关键字的作用与用法

volatile 让变量每次在使用的时候，都从主存中取。而不是从各个线程的“工作内存”。

volatile 具有 synchronized 关键字的“可见性”，但是没有 synchronized 关键字的“并发正确性”，也就是说不保证线程执行的有序性。

也就是说，volatile 变量对于每次使用，线程都能得到当前 volatile 变量的最新值。但是 volatile 变量并不保证并发的正确性，synchronized 要比 volatile 消耗更多资源。

使用volatile关键时一定要谨慎，如果自己没有把握，可以使用 synchronized 来代替 volatile。
展开剩余53%