算法与数据结构面试笔记

参考：一致性哈希、B+ 树、Heap 数据结构、LRU Cache 实现、Bloom filter 原理

1 一致性哈希

当系统节点数目动态变化（节点失效、新节点加入）时，如何保证良好的服务。如果某台服务器失效而不采用合适算法，通过取模计算 hash（与节点数有关）的缓存系统会因 hash 值改变而找不到保存对象的节点，导致缓存大面积失效。良好的分布式缓存一致性哈希应满足：

平衡性（Balance)：哈希结果尽可能分布到所有缓冲中，让所有缓冲空间都得到利用；
单调性（Monotonicity）：已有内容通过哈希分派后，新增缓冲区时原有已分配内容应能被映射到新缓冲区，而不是映射到旧缓冲集合的其他缓冲区。简单哈希（如 x = (ax + b) mod P）在缓冲大小变化时所有结果都变化，不满足单调性；
分散性（Spread）：不同终端所见缓冲范围不同会导致相同内容被映射到不同缓冲区，降低存储效率，好的哈希算法应尽量降低分散性；
负载（Load）：从另一个角度看待分散性问题，特定缓冲区可能被不同用户映射为不同内容，应尽量降低缓冲负荷；
平滑性（Smoothness）：缓存服务器数目平滑改变和缓存对象平滑改变一致。

一致性哈希思想

把哈希值空间组织成一个虚拟圆环（0 ~ 2^32-1），服务器节点和 key 都通过 hash 映射到环上；key 沿环顺时针找到的第一个服务器即其归属。节点增减只会影响环上相邻范围的数据，实现单调性。引入虚拟节点解决节点较少时的数据倾斜。

Python 实现参考

        
      
# -*- coding: utf-8 -*-
"""Implements consistent hashing that can be used when
the number of server nodes can increase or decrease (like in memcached)."""
import math
import sys
from bisect import bisect

if sys.version_info >= (2, 5):
    import hashlib
    md5_constructor = hashlib.md5
else:
    import md5
    md5_constructor = md5.new

class HashRing(object):

    def __init__(self, nodes=None, weights=None):
        """`nodes` is a list of objects that have a proper __str__ representation.
        `weights` is dictionary that sets weights to the nodes.
        The default weight is that all nodes are equal."""
        self.ring = dict()
        self._sorted_keys = []
        self.nodes = nodes
        self.weights = weights or {}
        self._generate_circle()

    def _generate_circle(self):
        total_weight = 0
        for node in self.nodes:
            total_weight += self.weights.get(node, 1)

        for node in self.nodes:
            weight = self.weights.get(node, 1)
            factor = math.floor((40 * len(self.nodes) * weight) / total_weight)

            for j in range(0, int(factor)):
                b_key = self._hash_digest('%s-%s' % (node, j))
                for i in range(0, 3):
                    key = self._hash_val(b_key, lambda x: x + i * 4)
                    self.ring[key] = node
                    self._sorted_keys.append(key)

        self._sorted_keys.sort()

    def get_node(self, string_key):
        """Given a string key a corresponding node in the hash ring is returned.
        If the hash ring is empty, `None` is returned."""
        pos = self.get_node_pos(string_key)
        if pos is None:
            return None
        return self.ring[self._sorted_keys[pos]]

    def get_node_pos(self, string_key):
        if not self.ring:
            return None
        key = self.gen_key(string_key)
        nodes = self._sorted_keys
        pos = bisect(nodes, key)
        if pos == len(nodes):
            return 0
        return pos

    def gen_key(self, key):
        b_key = self._hash_digest(key)
        return self._hash_val(b_key, lambda x: x)

    def _hash_val(self, b_key, entry_fn):
        return ((b_key[entry_fn(3)] << 24)
                | (b_key[entry_fn(2)] << 16)
                | (b_key[entry_fn(1)] << 8)
                | b_key[entry_fn(0)])

    def _hash_digest(self, key):
        m = md5_constructor()
        m.update(key.encode('utf-8'))
        return list(m.digest())

2 堆（Heap）

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树；
根节点最大的堆叫大顶堆/大根堆，根节点最小的叫小顶堆/小根堆；
常见的堆有二叉堆、斐波那契堆等。堆是非线性数据结构，相当于一维数组，每个节点有两个直接后继。

二叉树与堆的关系

堆是满足特定条件的完全二叉树（父节点值 ≥/≤ 子节点值），用数组存储时 i 节点的左孩子是 2i+1、右孩子是 2i+2。

3 B+ 树

数据库索引最常用的结构，特点：

非叶子节点只存储索引键，不存储数据；
叶子节点存储全部数据，且叶子节点之间有链指针，可以顺序遍历、支持区间访问；
相比 B-树，B+ 树节点更小、单次磁盘 IO 读出的有效数据更多、IO 次数更少；
相比 AVL/红黑树，B+ 树深度更低，磁盘寻道开销小。

（详尽的 B+ 树分析见《MySQL 面试笔记》一文。）

4 LRU Cache 实现（C）

用双向链表 + 哈希表实现：

QNode 双向链表节点（prev/next/pageNumber）；
Queue 表示缓存帧，front（最近使用）rear（最久未使用）；
Hash 哈希表，快速定位页号对应的链表节点；
算法：引用页时若 hash 中无该页则 Enqueue（满则淘汰队尾最久未使用页），若已存在则把该节点移到队首。

完整实现参考：

        
      
// A C program to show implementation of LRU cache
#include <stdio.h>
#include <stdlib.h>

// A Queue Node (Queue is implemented using Doubly Linked List)
typedef struct QNode {
    struct QNode *prev, *next;
    unsigned pageNumber;
} QNode;

// A Queue (A FIFO collection of Queue Nodes)
typedef struct Queue {
    unsigned count;
    unsigned numberOfFrames;
    QNode *front, *rear;
} Queue;

// A hash (Collection of pointers to Queue Nodes)
typedef struct Hash {
    int capacity;
    QNode** array;
} Hash;

QNode* newQNode(unsigned pageNumber) {
    QNode* temp = (QNode*)malloc(sizeof(QNode));
    temp->pageNumber = pageNumber;
    temp->prev = temp->next = NULL;
    return temp;
}

Queue* createQueue(int numberOfFrames) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->count = 0;
    queue->front = queue->rear = NULL;
    queue->numberOfFrames = numberOfFrames;
    return queue;
}

Hash* createHash(int capacity) {
    Hash* hash = (Hash*)malloc(sizeof(Hash));
    hash->capacity = capacity;
    hash->array = (QNode**)malloc(hash->capacity * sizeof(QNode*));
    for (int i = 0; i < hash->capacity; ++i)
        hash->array[i] = NULL;
    return hash;
}

int AreAllFramesFull(Queue* queue) {
    return queue->count == queue->numberOfFrames;
}

int isQueueEmpty(Queue* queue) {
    return queue->rear == NULL;
}

void deQueue(Queue* queue) {
    if (isQueueEmpty(queue))
        return;
    if (queue->front == queue->rear)
        queue->front = NULL;
    QNode* temp = queue->rear;
    queue->rear = queue->rear->prev;
    if (queue->rear)
        queue->rear->next = NULL;
    free(temp);
    queue->count--;
}

void Enqueue(Queue* queue, Hash* hash, unsigned pageNumber) {
    if (AreAllFramesFull(queue)) {
        hash->array[queue->rear->pageNumber] = NULL;
        deQueue(queue);
    }
    QNode* temp = newQNode(pageNumber);
    temp->next = queue->front;
    if (isQueueEmpty(queue))
        queue->rear = queue->front = temp;
    else {
        queue->front->prev = temp;
        queue->front = temp;
    }
    hash->array[pageNumber] = temp;
    queue->count++;
}

void ReferencePage(Queue* queue, Hash* hash, unsigned pageNumber) {
    QNode* reqPage = hash->array[pageNumber];
    if (reqPage == NULL)
        Enqueue(queue, hash, pageNumber);
    else if (reqPage != queue->front) {
        reqPage->prev->next = reqPage->next;
        if (reqPage->next)
            reqPage->next->prev = reqPage->prev;
        if (reqPage == queue->rear) {
            queue->rear = reqPage->prev;
            queue->rear->next = NULL;
        }
        reqPage->next = queue->front;
        reqPage->prev = NULL;
        reqPage->next->prev = reqPage;
        queue->front = reqPage;
    }
}

int main() {
    Queue* q = createQueue(4);      // cache can hold 4 pages
    Hash* hash = createHash(10);    // 10 different pages can be requested

    ReferencePage(q, hash, 1);
    ReferencePage(q, hash, 2);
    ReferencePage(q, hash, 3);
    ReferencePage(q, hash, 1);
    ReferencePage(q, hash, 4);
    ReferencePage(q, hash, 5);

    // print cache frames after the above referenced pages
    printf("%d ", q->front->pageNumber);
    printf("%d ", q->front->next->pageNumber);
    printf("%d ", q->front->next->next->pageNumber);
    printf("%d ", q->front->next->next->next->pageNumber);
    return 0;
}

5 布隆过滤器

见《Redis 面试笔记》一文中的详细介绍：bit 向量 + k 个哈希函数，只能确定”一定不存在”，不能确定”一定存在”。

6 其他算法题

10 亿 int 型数，统计只出现一次的数：分治 + 哈希/位图，参考 CSDN 题解；
大数据统计 TOP K / 去重：布隆过滤器、Hash 分桶 + 小顶堆（topk）。

常考手写题目

手写一致性哈希
手写 LRU Cache
手写生产者-消费者模式
链表 k 次反转、单链表逆序
查找树中连接两个节点最大路径
最大连续和 dp 解法
排序与时间复杂度/空间复杂度分析

阅读 — · 全站 —