八股-随记

八股

‍

一致性哈希算法

‍

‍

跳表

‍

‍

B+树

‍

‍

IO多路复用 select/poll/epoll

🧠 什么是 IO 多路复用？

是一种单线程监听多个 IO 事件的机制，当某个 IO 准备好后才去处理，从而提升效率，减少线程/进程资源浪费。

‍

🛠️ 背景：为什么需要 IO 多路复用？

普通阻塞 IO（blocking I/O）的问题：

• 一个线程/进程只能阻塞在一个 fd 上
• 要处理多个客户端连接，就需要多个线程/进程，资源开销大

非阻塞 IO + 多路复用：

• 一个线程使用 select/poll/epoll 同时监听多个 socket fd 的可读/可写状态，只有事件发生才进行处理

‍

select

[用户态 fd_set] --拷贝--> [内核态 fd_set]
                            |
               内核遍历每个 fd，找出就绪 fd
                            |
[返回用户态] <--------------|

select 通过将 fd_set​ 从用户态复制到内核态，交给内核判断哪个 fd 有消息，提高了速度

‍

int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);

‍

缺点：

• bitmap 默认大小是 1024，虽然可以调整大小，但仍有上限

• ​fd_set​ 不可重用，每次循环需要先赋空值

• 将 fd_set​ 从用户态复制到内核态，导致 用户态 <-> 内核态 仍然需要一定开销

• 并不知道是哪些文件描述符里有数据，需要遍历一遍 O(n)

‍

poll

使用 struct pollfd 数组存储 fd 与监听事件

每次调用都遍历整个数组，检查 IO 是否准备好

有事件内核将 revents 置位

返回后在遍历后，将置位复位，就实现了重用pullfds​

struct pollfd
{
	int fd;
	short events;
	short revents;
};

int poll(struct pollfd *fds, nfds_t nfds, int timeout);

‍

解决的 select 的 1️⃣、2️⃣ 缺点

‍

👍 优势：

• 无 FD 数量限制（受限于操作系统最大 fd 数）
• 支持更多事件（如 POLLIN、POLLOUT、POLLERR）

👎 缺点：

• 每次 poll 调用都要重新传入所有 fd
• 遍历所有 fd 找出准备好的 → O(n) 时间复杂度

‍

epoll

Redis、Nginx、Java NIO、Linux 底层都使用 epoll

‍

基本原理：

• 使用红黑树存储所有监听的 fd（注册一次即可）
• 使用就绪链表记录发生事件的 fd
• ​epoll_wait​ 直接从就绪链表取 → 高效 O(1)

‍

int epoll_create(int size);                      // 创建 epoll 对象
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); // 添加/删除/修改监听 fd
int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout); // 等待事件

‍

fd 注册一次 → 红黑树中保存
发生事件 → 加入就绪链表
epoll_wait 从就绪链表中取事件 → 非阻塞 / 高性能

‍

特性	select	poll	epoll
出现时间	最早	较早	Linux 2.6 之后
最大连接数	1024（固定）	无限制	无限制
数据结构	位图数组	数组	红黑树 + 就绪链表
拷贝成本	每次都复制	每次都复制	注册一次即可
就绪判断	遍历全部 fd	遍历全部 fd	事件通知
时间复杂度	O(n)	O(n)	O(1)（就绪 fd 数）
支持触发模式	无	无	LT / ET
跨平台	是	是	否（仅 Linux）

‍

==、equals()、hashCode()

==

== 比较的是两个变量是否引用同一个对象（地址值） ，或者两个基本类型值是否相等。

String a = new String("hello");
String b = new String("hello");

System.out.println(a == b);          // false（不同对象）
System.out.println(a.equals(b));     // true（内容相同）

---

.equals()

.equals() 是 Object 类中的方法，默认和 == 一样（也是比较地址）。

但是多数类（如 String、Integer、List、自己定义的类）重写了 .equals()，用于比较内容是否相同。

String s1 = "abc";
String s2 = "abc";
System.out.println(s1.equals(s2));  // true（内容相等）

---

hashCode()

是一种将对象映射成整数的散列方法，用于提高 HashMap、HashSet 等哈希容器 的效率。

为什么要有它？

• 如果两个对象 .equals() 为 true，它们的 hashCode() 必须相等
• 但如果两个对象 .hashCode() 相等，.equals() 不一定为 true（哈希冲突）

---

☑️ 自定义类重写 equals & hashCode（IDE 会自动生成）

public class Person {
    private String name;
    private int age;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Person person = (Person) o;
        return age == person.age &&
               Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

---

🔥 面试高频陷阱

场景	是否相等	原因
new String("abc") == "abc"	false	前者是堆对象，后者是常量池
"abc" == "abc"	true	两者都在常量池
Integer a = 1000; Integer b = 1000; a == b	false	超过了 -128~127 缓存范围
Map.containsKey(obj)	看的是 hashCode + equals	两者都要命中才能匹配

‍

为什么要同时重写.equals()和hashCode()

🧠 一句话总结：

如果你只重写了 equals()，却没重写 hashCode()，那么你的对象在基于哈希的集合中（如 HashMap/HashSet）就会“找不到自己”。

---

☑️ 原因详解

HashMap/HashSet 工作流程：

put(K key, V value) / contains(key) 做的操作顺序是：
1. 先根据 key.hashCode() 找到对应的桶（bucket）
2. 再用 key.equals() 在桶中查找具体的对象

如果只重写 .equals() 而没重写 .hashCode() ：

Person p1 = new Person("Tom", 18);
Person p2 = new Person("Tom", 18);

Set<Person> set = new HashSet<>();
set.add(p1);

System.out.println(set.contains(p2));  // ❌ false

为什么是 false？

• p1.equals(p2) 返回 true（你重写了 equals）
• 但是 p1.hashCode() != p2.hashCode()（你没重写 hashCode）
• HashSet 根本不会进入 equals 判断，因为在“不同的桶”里！

---

🚨 Java 规范（来自 Object 类文档）：

如果两个对象使用 .equals() 比较相等，那么它们必须具有相同的 hashCode() 值。

也就是说：

✅ 正确的类重写方式：

@Override
public boolean equals(Object o) {
    ...
}

@Override
public int hashCode() {
    ...
}

          put / contains
               ↓
       +----------------+
       |   hashCode()   | → 找桶（快速定位）
       +----------------+
               ↓
       +----------------+
       |    equals()    | → 桶中比内容（精确比较）
       +----------------+

‍