🗞️ 返回专题页

LRU算法

概念

• LRU（Least Recently Used，最近最久未使用算法）：

  • 定义：根据页面调入内存后的使用情况来做决策。LRU页面置换算法选择最近最久未使用的页面予以淘汰；
  • 支持：该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问内以来锁经历的时间t；当淘汰一个页面时，选择现有页面中 t值最大的（即最近最久未使用的）页面进行淘汰

• 两种硬件支持（选择其中一种即可）：

  1.寄存器：

  • 作用：其中包含了标记位和时间戳，标记位可以快速判断缓存块（页面）是否有效，而无需遍历整个栈来查找。时间戳可以快速记录和更新缓存块（页面）的访问时间，而不必每次访问都遍历栈来更新。

  2.栈：

  • 作用：用于记录缓存块（页面）的访问顺序（当前使用中的各个页面的页面号）。
  • 新增页面步骤：
    • 每当进程访问某页面时，判断该页面在栈中是否存在
      • 若存在，则将该页面的页面号从栈中取出，并将该原页面号压入栈顶；
      • 若不存在，则将栈底元素移除，并将新页面号压入栈顶；
    • 因此，**栈顶始终是最新被访问页面的页面号 **， 栈底则是最近最久未使用页面的页面号！

概念图解

• 举例前提：假设内存只能容纳3个页大小，进程按照 5 2 1 9 2 0 2 8的次序访问页
• 假设内存按照栈的方式来描述访问时间，并保证 栈顶始终是最新被访问页面的页面号 ， 栈底则是最近最久未使用页面的页面号

基于HashMap和双向链表实现

核心思想

• 核心思想：使用自定义节点DLinkedNode模拟双向链表，并通过双向链表实现栈功能；

• 使用HashMap存储以页面号为key，value存储指向双向链表节点的指针

• 双向链表维护了页面的访问顺序，链表的头部（即栈顶）为最新访问的页面，底部为最久未使用的页面

• put(key,value)：首先在 HashMap 找到 Key 对应的节点，

  • 如果节点存在，更新节点的值，并把这个节点移动栈顶。

  • 如果不存在，需要构造新的节点，并且尝试把节点塞到栈顶 ，如果LRU空间不足，则通过 tail 淘汰掉栈底的节点，同时在 HashMap 中移除 Key。

代码解读

完整代码:

class DLinkedNode {
    String key;
    int value;
    DLinkedNode pre;
    DLinkedNode next;
}

public class LRUCache {


    private Hashtable<String, DLinkedNode> cache = new Hashtable<>();
    private int count;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.count = 0;
        this.capacity = capacity;

        head = new DLinkedNode();
        head.pre = null;

        tail = new DLinkedNode();
        tail.next = null;

        head.next = tail;
        tail.pre = head;
    }

    public void put(String key, int value) {
        DLinkedNode node = cache.get(key);

        if(node == null){

            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;

            this.cache.put(key, newNode);
            this.addNode(newNode);

            ++count;

            if(count > capacity){
                // 淘汰栈底元素
                DLinkedNode tail = this.popTail();
                this.cache.remove(tail.key);
                --count;
            }
        }else{
            //该元素已经存在
            //将该元素移动到栈顶
            node.value = value;
            this.moveToHead(node);
        }
    }

    //添加节点
    private void addNode(DLinkedNode node){
        node.pre = head;
        node.next = head.next;

        head.next.pre = node;
        head.next = node;
    }


    //删除该节点（跳过该节点）
    private void removeNode(DLinkedNode node){
        DLinkedNode pre = node.pre;
        DLinkedNode next = node.next;

        pre.next = next;
        next.pre = pre;
    }

    //将该节点移动到头节点
    private void moveToHead(DLinkedNode node){
        this.removeNode(node);
        this.addNode(node);
    }

    //淘汰栈底元素
    private DLinkedNode popTail(){
        DLinkedNode res = tail.pre;
        this.removeNode(res);
        return res;
    }

    @Override
    public String toString() {
        StringBuilder sbu = new StringBuilder();
        DLinkedNode cur = head.next;
        sbu.append("{");
        while (cur != tail) {
            if (cur.next != tail) {
                sbu.append(cur.key).append("=").append(cur.value).append(", ");
            } else {
                sbu.append(cur.key).append("=").append(cur.value);
            }
            cur = cur.next;
        }
        sbu.append("}");
        return sbu.toString();
    }


    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(3);
        lruCache.put("1", 5);
        lruCache.put("2", 2);
        lruCache.put("3", 1);
        System.out.println(lruCache);

        System.out.println("使用后：");
        lruCache.put("2",2);
        System.out.println(lruCache);
        lruCache.put("2",2);
        System.out.println(lruCache);
        lruCache.put("4", 13);
        System.out.println("最不常用的被删除，新元素插到头部：");
        System.out.println(lruCache);
    }

}

核心概念与流程

1. 数据结构：
   • DLinkedNode：用于双向链表节点，存储键值对 (key, value)，并提供前向和后向指针 (pre, next)。
   • Hashtable<String, DLinkedNode>：哈希表，用于快速查找键值对的位置。
   • 双向链表：用来维持缓存的访问顺序，头部为最新访问，尾部为最久未使用。
2. 核心方法：
   • addNode(DLinkedNode node)：将节点插入到链表头部。
   • removeNode(DLinkedNode node)：将节点从链表中移除。
   • moveToHead(DLinkedNode node)：将链表中的某节点移动到头部。
   • popTail()：移除链表尾部节点，并返回它。
3. 工作流程：
   • 添加新元素：
     • 若元素 不存在：创建新节点，插入到链表头部，更新哈希表，若超出容量，移除尾部元素。
     • 若元素 存在：更新节点的值，并将该节点移动到头部。
   • 获取元素（在这段代码中未实现get方法）时，需移动节点到头部，标记为“最新使用”。
4. 方法实现：
   • put(String key, int value)
     • 负责插入或更新缓存数据，并根据容量限制淘汰最久未使用的数据。

代码解析：

DLinkedNode类

class DLinkedNode {
    String key;
    int value;
    DLinkedNode pre;
    DLinkedNode next;
}

DLinkedNode 是双向链表节点，存储键和值，同时记录前向节点（pre）和后向节点（next）。

LRUCache类

1. 构造方法

 public LRUCache(int capacity) {
    this.count = 0;
    this.capacity = capacity;

    head = new DLinkedNode();
    head.pre = null;

    tail = new DLinkedNode();
    tail.next = null;

    head.next = tail;
    tail.pre = head;
}

• 初始化缓存容量 (capacity) 和计数 (count)。
• 使用哨兵节点 head 和 tail 作为双向链表的边界，便于操作。
• 初始时，head 和 tail 相连，链表为空。

​ 2.插入/更新元素

 public void put(String key, int value) {
    DLinkedNode node = cache.get(key);

    if (node == null) {
        // 不存在时创建新节点，插入头部
        DLinkedNode newNode = new DLinkedNode();
        newNode.key = key;
        newNode.value = value;

        this.cache.put(key, newNode);
        this.addNode(newNode);

        ++count;

        if (count > capacity) {
            // 超过容量，淘汰尾部节点
            DLinkedNode tail = this.popTail();
            this.cache.remove(tail.key);
            --count;
        }
    } else {
        // 存在时更新值并移到头部
        node.value = value;
        this.moveToHead(node);
    }
}

1. 辅助方法

• addNode：将节点插入到链表头部。

 private void addNode(DLinkedNode node) {
    node.pre = head;
    node.next = head.next;

    head.next.pre = node;
    head.next = node;
}

• removeNode：从链表中移除节点。

 private void removeNode(DLinkedNode node) {
    DLinkedNode pre = node.pre;
    DLinkedNode next = node.next;

    pre.next = next;
    next.pre = pre;
}

• moveToHead：先移除，再插入头部。

 private void moveToHead(DLinkedNode node) {
    this.removeNode(node);
    this.addNode(node);
}

• popTail：移除尾部节点并返回。

 private DLinkedNode popTail() {
    DLinkedNode res = tail.pre;
    this.removeNode(res);
    return res;
}

打印缓存

@Override
public String toString() {
    StringBuilder sbu = new StringBuilder();
    DLinkedNode cur = head.next;
    sbu.append("{");
    while (cur != tail) {
        if (cur.next != tail) {
            sbu.append(cur.key).append("=").append(cur.value).append(", ");
        } else {
            sbu.append(cur.key).append("=").append(cur.value);
        }
        cur = cur.next;
    }
    sbu.append("}");
    return sbu.toString();
}

遍历链表，从头到尾输出缓存内容。

示例运行解析

在主方法 main 中，我们创建了一个容量为 3 的 LRU 缓存实例，并进行了一系列操作。

代码段与输出分析

LRUCache lruCache = new LRUCache(3); // 创建容量为3的缓存
lruCache.put("1", 5);                // 插入键 "1"，值 5
lruCache.put("2", 2);                // 插入键 "2"，值 2
lruCache.put("3", 1);                // 插入键 "3"，值 1
System.out.println(lruCache);        // 打印缓存内容

缓存状态：

• 插入 "1=5"：链表头部是 1，内容为 {1=5}。
• 插入 "2=2"：2 插入到链表头部，1 移到次头部，内容为 {2=2, 1=5}。
• 插入 "3=1"：3 插入到链表头部，2 和 1 向后移动，内容为 {3=1, 2=2, 1=5}。

输出：

{3=1, 2=2, 1=5}

System.out.println("使用后：");
lruCache.put("2", 2);                // 访问 "2"，更新值（虽然未变），并将其移动到头部
System.out.println(lruCache);        // 打印缓存内容

缓存状态：

• 访问 "2"：虽然值未变化，但 2 被标记为“最新使用”，移到链表头部，内容为 {2=2, 3=1, 1=5}。

输出：

使用后：
{2=2, 3=1, 1=5}

lruCache.put("4", 13);               // 插入键 "4"，值 13（超出容量，需要淘汰）
System.out.println("最不常用的被删除，新元素插到头部：");
System.out.println(lruCache);        // 打印缓存内容

缓存状态：

• 插入"4=13"：
  1. 4 插入到链表头部。
  2. 缓存容量达到 4，超出最大容量 3，移除尾部节点 1（最久未使用）。
  3. 最终链表内容为 {4=13, 2=2, 3=1}。

输出：

最不常用的被删除，新元素插到头部：
{4=13, 2=2, 3=1}

完整运行过程总结

1. 初始状态：
   • 缓存为空。
2. 操作与结果：
   • 插入键 "1"：缓存 {1=5}。
   • 插入键 "2"：缓存 {2=2, 1=5}。
   • 插入键 "3"：缓存 {3=1, 2=2, 1=5}。
   • 访问键 "2"：缓存 {2=2, 3=1, 1=5}。
   • 插入键 "4"：缓存 {4=13, 2=2, 3=1}，淘汰最久未使用的 "1"。

缓存的特点

• 每次操作后，链表头部始终是最近使用的元素。
• 当超出容量时，尾部的元素（最久未使用）被淘汰。

总结

• 时间复杂度：
  • 插入/获取：O(1)（哈希表查找 + 链表操作）
• 空间复杂度：
  • 取决于缓存容量 capacity。

此实现高效且简洁，是常见的 LRU 缓存设计方案。

MySQL对于LRU的优化

MySQL 在查询数据时，对于 InnoDB 存储引擎而言，会先将磁盘上的数据以页为单位，先将数据页加载进内存，然后以缓存页的形式存放在**「Buffer Pool」**中。Buffer Pool 是 InnoDB 的一块内存缓冲区，在 MySQL 启动时，会按照配置的缓存页的大小，将 Buffer Pool 缓存区初始化为许多个缓存页，默认情况下，缓存页大小为 16KB。

为了方便理解，对于磁盘上的数据所在的页，叫做数据页，当加载进 Buffer Pool 中后，叫做缓存页，这两者是一一对应的

在 MySQL 启动初期，Buffer Pool 中的这些缓存页都是处于空闲状态，也就是还没有被使用，而随着 MySQL 的运行时间越来越长，这些缓存页渐渐地都被使用了，用来存放从磁盘上加载的数据页，导致空闲的缓存页就越来越少。当某一时刻，所有空闲的缓存页都被使用了，那么这个时候，从磁盘加载到内存中的数据页该怎么办呢？

理想的LRU算法

既然没有空闲缓存页了，而又想使用缓存页，那么最简单的办法就是淘汰一个缓存页。应该淘汰谁呢？当然是淘汰那个最近一段时间最少被访问过的缓存页了，这种思想就是典型的 LRU 算法了。

LRU 是 Least Recently Used 的简写，这个算法的实现就是淘汰最久未使用的数据，它通过维护一个链表，每当访问了某个数据时，就将这个数据加入到链表的头部，如果数据本身存在于链表中，那么就将数据从链表的中间移动到链表的头部，这样最终下来，在链表尾部的数据一定就是最久未被使用的数据了，因此可以将其淘汰。

将 LRU 算法应用到缓存页的淘汰策略上，那么就是在 InnoDB 存储引擎层内部，维护了一个链表，这些链表中的元素存储的就是指向缓存页的指针。

在 MySQL 启动的时候，这个链表为空。MySQL 启动以后，在进行数据查询时，InnoDB 会先判断要查询的数据所在的数据页，是否存在于 Buffer Pool 的缓存页当中，如果不存在，就从磁盘中读取对应数据页，存放到 Buffer Pool 一个空闲的缓存页当中，然后将这个缓冲页放入到链表的头部；如果要查询的数据已经存在于 Buffer Pool 当中了，那么就将对应的缓存页从链表的中间移动到链表头部。

这样随着 MySQL 的运行，空闲的缓存页越来越少，LRU 链表越来越长，直到某一时刻，剩余的空闲缓存页数为 0，当需要申请一个新的空闲缓存页的时候，就需要淘汰一个缓存页了，此时只需要把链表尾部的那个缓存页刷入到磁盘，然后清空缓存页里面的数据，这样就空余出一个新的缓存页了。

LRU链表带来的问题

咋一看，似乎 LRU 链表完美解决了缓存页淘汰的问题。但理想很丰满，现实却很骨感，如果直接使用这种 LRU 算法的话，在 MySQL 中就会存在很大的问题。

全表扫描！！！

在 MySQL 中经常会出现全表扫描，一种是开发人员对索引的使用不当导致的，一种是业务如此，无法避免。

当出现全表扫描时，InnoDB 会将该表的数据页全部从磁盘文件加载进缓存页中，这些缓存页会被加入到 LRU 链表中。如果进行全表扫描的对象是一张非常大的表，可能是几十 GB 的数据，而且这张表记录的是类似于账户流水、操作日志等使用不频繁的数据，这个时候如果 LRU 链表已经满了，现在我们就要淘汰一部分缓存页，腾出空间来存放全表扫描出来的数据。这样就会因为全表扫描的数据量大，需要淘汰的缓存页多，导致在淘汰的过程中，极有可能将需要频繁使用到的缓存页给淘汰了，而放进来的新数据却是使用频率很低的数据，甚至是这一次使用之后，后面几乎再也不用，如操作日志等。

最终导致的现象就是，当我们在对这些使用不频繁的大表进行全表扫描之后，在一段时间内，Buffer Pool 缓存的命中率明显下降，SQL 的性能也明显下降，因为常用的缓存页被淘汰了，再进行查询时，需要从重新磁盘读取，发生磁盘 IO，性能下降。所以，如果 MySQL 只是简单的使用 LRU 算法，那么碰到全表扫描时，就会存在性能下降的问题，甚至在高并发场景下，成为性能瓶颈。

预读

预读是 InnoDB 引擎的一个优化机制，当你从磁盘上读取某个数据页，InnoDB 可能会将与这个数据页相邻的其他数据页也读取到 Buffer Pool 中。

InnoDB 为什么要这样做呢？因为从磁盘读取数据时发生的磁盘 IO 是随机 IO，性能差。当你读取某一个数据页时，InnoDB 会猜测你可能也需要下一个数据页的数据，如果一次能连着读取多个数据页，那么对其他的数据页而言，这是顺序读取（节省了寻道时间、磁头旋转时间），相对较快，那这样就能提升一点性能。

在两种情况下会触发预读机制：

1. 顺序的访问了磁盘上一个区的多个数据页，当这个数量超过一个阈值时，InnoDB 就会认为你对下一个区的数据也感兴趣，因此触发预读机制，将下一个区的数据页也全都加载进 Buffer Pool。这个阈值由参数 「innodb_read_ahead_threshold」 控制，默认为 56。 可以通过如下命令查看：

show variables like 'innodb_read_ahead_threshold';

1. 如果 Buffer Pool 中已经缓存了同一个区数据页的个数超过 13 时，InnoDB 就会将这个区的其他数据页也读取到 Buffer Pool 中。这个开关由参数 「innodb_random_read_ahead」 控制，默认是关闭的。

show variables like 'innodb_random_read_ahead';

如果 MySQL 仅是简单的使用 LRU 算法，那么预读机制和全表扫描带来的问题类似，预读机制会将其他的数据页也加载进内存，当 LRU 链表满时，可能将我们频繁访问的缓存页给淘汰，从而导致性能下降。

冷热分离

实际上，MySQL 确实没有直接使用 LRU 算法，而是在 LRU 算法上进行了优化。

从上面的全表扫描和预读机制的问题分析中，我们可以看到，根本原因就是从磁盘上新读取到的数据页，在加载进 Buffer Pool 时，可能将我们频繁访问的数据给淘汰，也就是出现了冷热数据的现象。因此，MySQL 的优化思路就是：对数据进行冷热分离，将 LRU 链表分成两部分，一部分用来存放冷数据，也就是刚从磁盘读进来的数据，另一部分用来存放热点数据，也就是经常被访问到数据。

其中，存放冷数据的区域占这个 LRU 链表的多少呢？这由参数 「innodb_old_blocks_pct」 控制，默认是 37%（约八分之三）。冷热分离的 LRU 链表示意图如下（图片来自于MySQL官方文档）。

show variables like 'innodb_old_blocks_pct';

优化过后的 LRU 链表，又是如何进行数据页的存放的呢？

「当从磁盘读取数据页后，会先将数据页存放到 LRU 链表冷数据区的头部，如果这些缓存页在 1 秒之后被访问，那么就将缓存页移动到热数据区的头部；如果是 1 秒之内被访问，则不会移动，缓存页仍然处于冷数据区中。1 秒这个数值，是由参数 innodb_old_blocks_time 控制。」

show variables like 'innodb_old_blocks_time';

当遇到全表扫描或者预读时，如果没有空闲缓存页来存放它们，那么将会淘汰一个数据页，而此时淘汰地是冷数据区尾部的数据页。冷数据区的数据就是不经常访问的，因此这解决了误将热点数据淘汰的问题。如果在 1 秒后，因全表扫描和预读机制额外加载进来的缓存页，仍然没有人访问，那么它们会一直待在冷数据区，当再需要淘汰数据时，首先淘汰地就是这一部分数据。

至此，基于冷热分离优化后的 LRU 链表，完美解决了直接使用 LRU 链表带来的问题。

LRU 链表的极致优化

实际上，MySQL 在冷热分离的基础上还做了一层优化。

当一个缓存页处于热数据区域的时候，我们去访问这个缓存页，这个时候我们真的有必要把它移动到热点数据区域的头部吗？

从代码的角度来看，将链表中的数据移动到头部，实际上就是修改元素的指针指向，这个操作是非常快的。但是为了安全起见，在修改链表的时候，我们需要对链表加上锁，否则容易出现并发问题。

当并发量大的时候，因为要加锁，会存在锁竞争，每次移动显然效率就会下降。因此 MySQL 针对这一点又做了优化，如果一个缓存页处于热数据区域，且在热数据区域的前 1/4 区域（注意是热数据区域的 1/4，不是整个链表的 1/4），那么当访问这个缓存页的时候，就不用把它移动到热数据区域的头部；如果缓存页处于热数据的后 3/4 区域，那么当访问这个缓存页的时候，会把它移动到热数据区域的头部。

生产上的 MySQL 调优

理解了上面的原理，下面则基于这些原理，说一些MySQL可以优化的方案。

MySQL 的数据最终是存储在磁盘上的，每次查询数据时，我们先需要把数据加载进缓存，然后读取，如果每次查询的数据都已经存在于缓存了，那么就不用去磁盘读取，避免了一次磁盘 IO，这是我们最期望的。因此为了尽量在 LRU 链表中缓存更多的缓存页，我们**「可以根据服务器的配置，尽量调大 Buffer Pool 的大小」**。

另外，在进行增删改查的时候，需要涉及到对 Buffer Pool 中 LRU 链表、Free 链表、Flush 链表的修改，为了线程安全，我们需要进行加锁。因此为了提高并发度，MySQL 支持配置多个 Buffer Pool 实例。当有多个Buffer Pool实例时，就能将请求分别分摊到这些Buffer Pool中，减少了锁的竞争。

可以通过如下命令去查看 Buffer Pool 的大小以及 Buffer Pool 实例的个数。

# buffer pool大小
show variables like 'innodb_buffer_pool_size';
# buffer pool实例个数
show variables like 'innodb_buffer_pool_instances';

Free 链表是维护空闲缓存页的列表，Flush 链表是维护脏页的链表。什么是脏页，感兴趣的同学可以先自己查阅相关资料

另外在实际应用中，在没有外部监控工具的情况下，我们该如何知道 MySQL 的一些状态信息呢？如：缓存命中率、缓存页的空闲数、脏页数量、LRU 链表中缓存页个数、冷热数据的比例、磁盘 IO 读取的数据页数量等信息。可以通过如下命令查看：

show engine innodb status;

这个命令的查询结果是一个很长的字符串，可以复制出来，放在文本文件中查看分析，部分信息截图如下：

如果看到 「youngs/s」 这个值较高，说明数据从冷数据区移到热数据的频率较大，因此可以适当调大热数据所占的比例，也就是减小**「innodb_old_blocks_pct」参数的值，也可以调大「innodb_old_blocks_time」**参数的值

如果看到 「non-youngs/s」 这个值较高，说明数据被加载进缓存当中后，没有被移动到热数据区，这是因为在 1s 内被访问了，这很可能是全表扫描造成的，这个时候就可以去检查一下代码，是不是SQL语句写得不恰当。

总结

总结一下，本文详细说明了普通的 LRU 链表并不适用于 MySQL，全表扫描和预读机制均会导致热点数据被淘汰，从而导致性能下降的问题。MySQL 在 LRU 算法的基础上做了优化，将链表拆分为冷、热两部分，从而解决了冷热数据的问题。最后介绍了几种 MySQL 优化的方法，可以通过调到 Buffer Pool 的大小以及个数来提升性能，也可以结合 MySQL 的运行状态信息来决定是否需要调整 LRU 链表的冷热数据区的比例。

另外，将数据进行冷热分离的这种思路，非常值得借鉴。

最后，实践是检验理论的唯一标准，MySQL 相关的原理明白了，至于生产环境的 MySQL 应该如何优化，还需要结合实际情况以及机器的配置来决定如何配置 MySQL 的参数。

HashMap

概念

HashMap 是 Java 中常用的一种数据结构，属于 java.util 包。它实现了 Map 接口，提供了一种基于哈希表的键值对存储方式。每个元素是一个键值对（key-value），其中键（key）是唯一的，而值（value）则可以是任意对象。

基本特点：

1. 基于哈希表：HashMap 内部通过哈希表（数组 + 链表/红黑树）来存储键值对，通过计算键的哈希值来找到对应的存储位置。
2. 允许 null 值：HashMap 允许一个 null 键和多个 null 值。
3. 不保证顺序：HashMap 中的元素是无序的，插入顺序和迭代顺序可能不同。如果需要保持顺序，可以使用 LinkedHashMap。
4. 线程不安全：HashMap 是非同步的，因此在多线程环境下，如果多个线程同时访问 HashMap 并且至少一个线程修改了映射关系，那么它必须通过外部同步机制来保证线程安全。如果需要线程安全的哈希表，可以使用 ConcurrentHashMap。
5. 操作复杂度：大多数情况下，HashMap 的增、删、查操作时间复杂度为 O(1)，但是在哈希冲突较严重的情况下，性能可能会退化到 O(n)。

结构

HashMap 内部由一个数组（Node[] table）和若干个链表/红黑树（用于处理哈希冲突）组成。每个数组的元素叫做“桶”（bucket），每个桶会存储多个哈希值相同的键值对（即发生哈希冲突的情况）。当哈希冲突较多时，桶内部可能会使用链表（Java 8 之后的版本）或红黑树（在链表较长时）来存储元素。

工作原理

1. 哈希算法：在插入一个元素时，HashMap 会首先通过键的 hashCode() 方法获取哈希值，然后使用该哈希值计算索引位置（数组的下标）。如果两个键的哈希值相同，则发生哈希冲突。
2. 哈希冲突处理：当发生哈希冲突时，HashMap 会将具有相同哈希值的元素放入同一个桶内。早期版本使用链表来存储这些冲突元素；从 Java 8 开始，如果链表长度超过一定阈值（默认 8），就会将链表转换成红黑树，以优化查找性能。
3. 加载因子和扩容：HashMap 还有一个负载因子（load factor），用来控制何时进行扩容。默认的负载因子为 0.75，表示当 HashMap 中的元素数量超过当前数组容量的 75% 时，会进行扩容。扩容时，HashMap 会将数组的容量翻倍，并重新计算每个元素的存储位置。

主要操作

1. put(K key, V value)：插入键值对。如果键已经存在，则更新该键对应的值。
2. get(Object key)：根据键获取对应的值。如果键不存在，则返回 null。
3. remove(Object key)：删除指定键的元素。
4. containsKey(Object key)：判断 HashMap 是否包含指定的键。
5. containsValue(Object value)：判断 HashMap 是否包含指定的值。
6. size()：返回 HashMap 中键值对的数量。
7. clear()：清空 HashMap 中的所有键值对。

示例代码

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        // 创建一个 HashMap 实例
        HashMap<String, Integer> map = new HashMap<>();

        // 插入元素
        map.put("Apple", 10);
        map.put("Banana", 20);
        map.put("Orange", 30);

        // 获取元素
        System.out.println("Apple count: " + map.get("Apple")); // 输出 10

        // 删除元素
        map.remove("Banana");

        // 判断元素是否存在
        System.out.println("Contains Apple: " + map.containsKey("Apple")); // 输出 true
        System.out.println("Contains Banana: " + map.containsKey("Banana")); // 输出 false

        // 输出 HashMap 的大小
        System.out.println("Size of map: " + map.size()); // 输出 2

        // 清空 HashMap
        map.clear();
        System.out.println("Size of map after clear: " + map.size()); // 输出 0
    }
}

优缺点

优点：

1. 查找、插入、删除操作时间复杂度为 O(1)，在没有哈希冲突的情况下，效率非常高。
2. 支持 null 键和 null 值，灵活性较强。
3. 使用哈希表实现，内存占用通常较小。

缺点：

1. 无序：HashMap 不保证元素的顺序，如果需要保证插入顺序，可以使用 LinkedHashMap。
2. 存在哈希冲突时，性能可能下降：当哈希冲突严重时，查找效率会下降。Java 8 之后，通过使用红黑树来优化这个问题。
3. 线程不安全：HashMap 在多线程环境下使用时需要额外同步，否则可能导致数据不一致。

总结

HashMap 是一种高效的键值对存储结构，特别适合用来查找、插入、删除元素。它通过哈希算法实现 O(1) 的平均时间复杂度，但在哈希冲突严重时可能退化为 O(n)。在单线程环境中，HashMap 是非常常用的数据结构，而在多线程环境下，则需要使用 ConcurrentHashMap 或对其进行显式同步。

栈

堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

基本概念

要搞清楚这个概念，首先要明白“栈”原来的意思，如此才能把握本质。栈，存储货物或供旅客住宿的地方，可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。

堆栈是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，top）进行插入数据（PUSH）和删除数据（POP）的运算。

首先，系统或者数据结构栈中数据内容的读取与插入（压入）PUSH和 删除POP是两回事。压入是增加数据，弹出是删除数据 ，这些操作只能从栈顶即最低地址作为约束的接口界面入手操作 ，但读取栈中的数据是随便的，没有接口约束之说。很多人都误解这个理念从而对栈产生困惑。而系统栈在计算机体系结构中又起到一个跨部件交互的媒介区域的作用即CPU 与内存的交流通道 ，CPU只从系统提供用户自己编写的应用程序所规定的栈入口线性地读取执行指令， 用一个形象的词来形容它就是pipeline（管道线、流水线）。CPU内部交互具体参见 EU与BIU的概念介绍。

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为出栈/退栈（POP）。栈也称为先进后出表。

栈可以用来在函数调用的时候存储断点，做递归时要用到栈。

以上定义是在经典计算机科学中的解释。

在计算机系统中，栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小，弹出的操作使得栈顶的地址增大。

栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息：

1．函数的返回地址和参数

2． 临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量。

基本特点

堆栈的基本特点：

1. 先入后出，后入先出。
2. 除头尾节点之外，每个元素有一个前驱，一个后继。

基本算法

1．进栈（PUSH）算法

①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；

②置TOP=TOP+1（栈指针加1，指向进栈地址）；

③S(TOP)=X，结束（X为新进栈的元素）；

2．出栈（POP）算法

①若TOP≤0，则给出下溢信息，作出错处理（出栈前先检查是否已为空栈， 空则下溢；不空则作②）；

②X=S(TOP)，（出栈后的元素赋给X）：

③TOP=TOP-1，结束（栈指针减1，指向栈顶）。

到底什么是栈呢？

栈某种意义上讲，它像是一个开口的盒子，先放进去的东西总是会被后放进去的东西压在下面，那么如果想拿出被压住的东西，必须要先取出顶部的东西，也就是后放进去的东西。换个说法就是先入后出。那它有点像什么呢?想象一下装在盘子里的若干张油饼。

对，他们是摞在一起的。如果想拿下面的油饼是不是要先拿开上面的呢?或许，这就是栈的根源。

或者到这里，我们恍然大悟，哦，原来是这样!栈还有堆叠的意思。但是，我个人更觉得这是一种初期程序员之间的交流翻译吴缪。暂且放下这个不谈，至少我们明白一件事情，在某些领域，如果一个词汇很生涩，那么，不妨去查找一下他的英文愿意，或许你会有更深入的收获。

我们在来探讨下一个话题——“栈”stack，这种摞大饼大数据组织方式到底有什么用?

栈有什么用？

在"栈"结构里面，数据是累起来的，堆的高高的。那也就是说，“栈”(stack)不适合存放需要随机查找的东西。那它能做什么呢?

首先说说CPU里的“堆栈”。我们可以这样设想：一个CPU等同于一个完全没有记忆力的人，他只知道按照一份很详细的说明文档(也就是程序)来一步一步做某件事情，并且，他永远不会记得之前做过什么。我们在电影里常常会看到这样的情节，失忆症的人常常会随身携带一些本子和照片，然后按顺序把发生的事情记录下来，方便自己查阅。CPU也有这样的需求。

在CPU里，有一种机制叫做“中断”interrupt，就是中途插一嘴的意思。怎么插呢?比方说，你正在玩儿一个单机游戏，在更要通关的时候，外面突然有人敲门。那么是不是要把你的游戏暂停一下?然后再去开门。然后正在你去开门的路上，厨房的煤气报警器响起，是不是要赶紧去厨房看一下是不是误报警?确认是误报警后，我们是先去开门呢?还是继续打游戏呢?对于CPU来说，也会有同样的困惑。对于人，我们或许可以思考一下——哦，开门这件事器比较紧迫，应该先开门。但是对于CPU来说，又如何区分紧迫度呢?这就变成了一个很麻烦的问题。我们回头再想想“栈”，他是如何组织数据的?先入后出。玩游戏是先发生的事情，那么打断他的事情就是更紧迫的事情，开门虽然比游戏紧迫，但是他次于煤气报警，所以，它才是紧迫的事情。不过到现在也应该注意到了。紧迫的事情往往在后产生，又要被优先处理。

在CPU的中断机制里，每当cpu执行的一个任务被打断时，cpu就需要备份当前的处理状态，就像没有记忆的人，总是要记笔记拍照。那么cpu怎么区分优先次序呢?就像你吃盘子里的饼!先拿上面的。而存储数据的过程，就像你向盘子里放饼的过程。

再说说C语言分段里的“栈区”，我们都知道，局部自动变量分配到内存的“栈区”，栈区里的数据组织方式也类似摞饼，每当你调用了一个子函数，那么编译器会将子函数里的局部变量分配到栈区的栈顶位置(与当前函数的空间相邻)，当子函数在再调用另一个函数是，也是会做同样处理。儿关于局部变量的释放，其实本质就是讲栈顶的一块空间的使用权归还回去，看起来就好像客栈一样，来人的时候开房，走人的时候退房。或许这也是stack会被翻译成“栈”的原由。

后在来说“栈”，这种单纯的逻辑结构。它和前两者一样，遵循类似先入后出的数据处理规则。

那这个“盒子“什么时候会用到呢?典型的例子，就是迷宫算法(具体细节可以自己搜索一下)，我们可以用栈来存放已经走过的有效路线。也或者利用栈来模拟局部变量分配，实现将递归算法转换为非递归。也或者利用栈来优化，自己的程序处理逻辑，在实际问题解决中，如果你涉及到了临时保存数据，那么你可以尝试考虑一下使用栈，或许可以让自己的程序在逻辑上变得更加清晰明了。

简单的总结一下：所谓“栈”，其实就是一本 相互堆叠的便签儿。我们可以逐次备份自己要保存的信息，然后在反向依次处理。

例子

检查字符串中的括号是否对上

假如现在有一组括号[{()}]，但是机器只能逐个检查，如何只检查一遍就可以完成：

现在借助栈：第一个是左括号，那就入栈，也就是所有左括号都这样做，第二个也是左括号继续入栈，第三个一样，第四个是右括号，所有右括号都要让栈顶出栈并和第四个比较，发现配对成功，第五个，第六个右括号一样，都配对成功，检查结束。

机器如何读取并计算如1+(6+2)*3

正常逻辑：先计算括号中的算式，将结果与3相乘，最后才和1相加。

简单做法是：先扫描一遍算式，检查是否有括号，优先计算，再重头开始，检查是否有乘号或者除号，最后再次扫描，计算加号和减号；

更高效的方法：先将算式转换成一个中间态，去掉括号，把运算符放到数字后面；

我们把运算符在中间的(例子中为1+(6+2)*3这种运算符不在最后的)称为中缀表达式(Infix Expression)，将运算符在后(例子:162+3*+)的是后缀表达式(Postfix Expression)

入栈规则：

1.所有的数字直接输出，所以1不入栈直接输出；(栈内为空)

2.运算符优先级高于栈内的要入栈(或栈空)。否则，从堆栈中弹出所有优先级更高或一样的运算符(或直到括号)，再将当前的入栈，所以+运算符入栈(栈内有+)；

3.所有左括号都要入栈(栈内有+和()

数字6按第一条规则来，直接输出，栈不变；

4.若栈内包含左括号，运算符都入栈，所以+入栈(栈内有+和(,+);

数字2按第一条规则来，直接输出，栈不变；

5.若是右括号，栈不断出栈，直到碰到左括号，所以先出栈+，再出栈(，碰到左括号，结束，此时栈内只有+，因为上一个+出栈后没有入栈。

运算符*遵循规则2，入栈(栈内有+和*)

数字3直接输出

此时栈内情况：

输出情况：

再将栈中都一一出栈，得出该后缀表达式为：162+3*+

最后我们再次利用栈进行计算：

凡是数字就压栈，凡是运算符就出栈两次

即：栈底为1，在6,2入栈，接下来，碰到+，出栈两次,即6+2，得出结果8入栈，3入栈，碰到*，出栈两次，即8*3得24，24入栈，然后碰到+，出栈两次，24+1，得25，结束运算。