美团 Java 开发面试题整理
面试题目
1、什么是半连接队列，什么是全连接队列 2、半连接队列会遇到什么问题 3、零拷贝原理 4、epoll是怎么实现的 5、布隆过滤器的原理 6、限流有哪些算法 7、几种常见的排序算法，以及稳定性分析
参考解析
1. 半连接与全连接队列： 半连接队列（SYN Queue）存放已收到SYN但未完成握手的请求；全连接队列（Accept Queue）存放已完成三次握手等待Accept的请求。半连接队列溢出会导致丢弃新请求，全连接队列溢出则会导致客户端连接超时。
2. 零拷贝原理： 指数据在传输时不需要CPU参与内核态与用户态之间的内存拷贝。常见实现有mmap、sendfile和splice，通过减少数据拷贝次数和上下文切换，大幅提升IO吞吐量。
3. Epoll实现： Epoll通过红黑树管理所有待监控的文件描述符（FD），并用双向链表存储就绪事件。其核心在于回调机制，无需像Select/Poll那样遍历全量FD，效率更高。
4. 布隆过滤器： 使用位数组和多个哈希函数表示集合。优点是空间利用率高、查询快；缺点是存在误判率，且不支持删除操作（除非使用计数布隆过滤器）。
5. 限流算法： 固定窗口（简单但有临界问题）、滑动窗口（平滑但有突发）、漏桶（平滑流量，处理速率固定）、令牌桶（允许一定突发流量，常用）。
6. 排序算法稳定性： 稳定排序算法有冒泡、插入、归并、基数排序；不稳定排序有快速排序、选择排序、堆排序、希尔排序。稳定性定义为相同值的元素在排序后相对顺序是否保持不变。