Skip to content

Latest commit

 

History

History
166 lines (113 loc) · 4.04 KB

基础提升01.md

File metadata and controls

166 lines (113 loc) · 4.04 KB

1. 与哈希函数有关的结构

MyHashTable.cpp

1.1 认识哈希函数和哈希表的实现

1. 哈希函数的特征

f(in) = out

  1. 输入域无穷，输出域有限（MD5: 0~2^64-1, SHA1: 0~2^128-1）

  2. 相同的输入参数，返回相同的输出值（不随机）

  3. 不同的输入，也可能产生相同的输出（哈希碰撞）

  4. 均匀离散

例：一个大文件中有40亿个数，文件中都是无符号整数0~2^32-1（0~42亿），使用 1G 内存统计出现次数最多次的是哪个数

  • 经典解法：哈希表（内存不够）

  • 解法：哈希函数

    • 每个数通过调用哈希函数得到一个哈希值，再对100取模，根据结果将数分到100个文件中
    • 对每个小文件使用哈希表统计

2. 哈希表的实现

Separate Chaning

扩容代价:

加入N个字符串，

  • 扩容次数: O(logN)
  • 每次扩容的代价：O(N)
  • 总的扩容代价：O(NlogN)
  • 单次扩容代价：O(logN)
  • 使用时可以做到 O(1)，理论上为 O(logN)

1.2 设计RandomPool结构

设计一种结构，在该结构中有如下三个功能：

insert(key)：将某个key加入到该结构，做到不重复加入

delete(key)：将原本在结构中的某个key移除

getRandom()：等概率随机返回结构中的任何一个key。

[要求]

Insert、delete和getRandom方法的时间复杂度都是 O(1)

哈希表的使用

template <typename T>
class Pool {
public:
    Pool() {
        this->size = 0;
    }

    void insertKey(T key) {
        if (KeyIndexMap.find(key) == KeyIndexMap.end()) {
            this->KeyIndexMap.insert(key, this->size);
            this->indexKeyMap.insert(this->size++, key);
        }
    }

    void deleteKey(T key) {
        if (KeyIndexMap.find(key) != KeyIndexMap.end()) {
            int deleteIndex = this->KeyIndexMap[key];
            int lastIndex = --this->size;
            T lastKey = this->indexKeyMap[lastIndex];
            this->KeyIndexMap[lastIndex] = deleteIndex;
            this->indexKeyMap[deleteIndex] = lastKey;
            this->KeyIndexMap.erase(key);
            this->indexKeyMap.erase(lastIndex);
        }
    }

    T getRandom() {
        if (this->size == 0) {
            return NULL;
        }
        srand(time(NULL));
        int randomIndex = rand() % this->size();
        return this->indexKeyMap[randomIndex];
    }

private:
    unordered_map<T, int> KeyIndexMap;
    unordered_map<int, T> indexKeyMap;
    int size;
};

1.3 布隆过滤器

解决的问题：黑名单，爬虫去重操作

特点：

  • 有添加，有查询，没有删除
  • 允许有失误率（白 → 黑）
  • 节省内存

基础知识：位图(bit arr, bit map)

  • bit类型的数组
array<int, 10> arr; // 320 bits
// arr[0] 0 - 31
// arr[1] 32 - 63
// arr[2] 64 - 95

int i = 178;
int numIndex = i / 32; // 找哪个数
int bitIndex = i % 32; // 找哪一位

// 拿到i位的状态
int s = (arr[numIndex] >> bitIdenx) & 1;

// 把i位的状态改为 1
arr[numIndex] = arr[numIndex] | (1 << bitIndex);

// 把i位的状态改为 0
arr[numIndex] = arr[numIndex] & (~ (1 << bitIndex));

// 拿到i位的状态
int bit = (arr[i / 32] >> (i % 32)) & 1;

长度为m的位图，k个哈希函数，算出k个哈希值，对m取模，得到k个值描黑。

已知：样本量 n，失误率 P

  1. set结构，只有增加，查询，没有删除行为
  2. 失误率

注：与单样本的大小无关

$$m=-(n*lnP)/(ln2)^2$$

$$k = ln2 * m / n = 0.7*m/n$$

$$P_{true} = (1-e^{-n*k_{true}/m_{true}})^{k_{true}}$$

1.4 详解一致性哈希原理

分布式系统

  • 适合的key：人名，身份证号（种类比较多，高频、中频、低频都有一定数量）

  • 不适合的key：国家名，性别

数据服务器如何组织

问题：使用模的方式，数据迁移代价高

  • 解决方案：把整个哈希域想象成一个环

问题一：少数量机器如何把环均分

问题二：增加或减少一台机器，负载不均衡

  • 解决：虚拟节点技术

  • 管理负载（通过分配不同的虚拟节点的数量）