关于hash

发表于 更新于 Changyan：

2G内存在20亿个整数中找出次数最多的数？

kv来描述一个数，一个整数4byte，两个整数8byte，20亿个整数需要16G内存。
数据结构存储：平衡二叉树map、散列表unordered_map。
分治：20亿个整数拆分成若干个范围，分别统计若干个范围中的次数多最大值，汇总若干个范围中的次数最大值，找出次数最大值对应的树。
逆向分析：
2GB = 2 * 2^10 * 2^10 * 2^10 B = 2^31 B，小范围的数字最多 2^31 / 8 = 2^28
有多少个小范围？整数4个字节共32bit，范围为-2^31～2^31，共2^32个整数，2^32/2^28 = 2^4
正向解决：

  • 将20亿个数拆分为16个范围
  • 将20亿个数依次除以2^28，得到一个0-15的值，放在一个小文件中，另外一种解法：hash分流，相同的key，经过多次hash总是得到相同的值，hash具备随机性，crc16、md5、murmurhash2、siphash、cityhash
  • 每个小文件unordered_map[k]++，散列表进行词频统计，如果某一个key出现次数超过10亿，就不必要统计了，这样也可以控制value的范围

40亿个非负整数中算中位数和找出现两次的数

  1. 最多使用1GB的内存，找出所有出现了两次的数
    出现了两次，共三种状态：
  • 小于2次
  • 等于2次
  • 大于2次
    怎么存储：
  • 对空间比较严格，使用位图，整数个数为2^32=42,9496,7296，由于有三种状态，需要242,9496,7296bit=2^33bit，而1GB = 2^102^102^108bit=2^33bit
    解决方案：
    2n,2n+1共两位来描述n的三种状态（n从0开始），00、01代表小于2次，10代表等于2次，11代表大于2次，对40亿个数进行统计，设置位图对应位数的值，最后遍历位图，找出10状态（等于2次）的n的值。
  1. 最多使用10MB内存，找出这40亿个非负整数的中位数
    总体思路：先将问题锁定在一个小范围之内，然后在小范围精准查找。
    问题拆分：将40亿个非负整数划分为多个有序区间，分别统计各个区间的个数，无需统计每个数字出现的次数，找到第20亿个数所在区间。
    逆向分析：出现的次数需要4Byte存储（最大可能就要40亿），小分区中数的个数：（10MB = 102^102^10Byte / 4Byte = 2.52^102^10），优化为22^102^10=2^21个数，共有2^32个整数，分区个数：2^32/(22^102^10)=2^11=2048个分区。
    正向解决：将40亿整数拆分为2048个分区，统计每个分区数字的个数，unsigned int arr[2048], arr[num/2^21]++，遍历分区，找到接近第20亿个所在的分区k，unsigned int arr[2^21],arr[num-k*2^21]++，统计出这个分区每个数字出现的次数，找出第20亿个数的值。

分布式一致性hash的原理以及应用

采用分布式一致性哈希算法的好处在于，当节点加入或离开系统时，只有与此节点相邻的节点需要重新计算，而不是整个哈希环，这样大大减少了计算量，同时保证了系统的可伸缩性和容错性。

  1. 首先将所有可用的节点（例如缓存服务器或数据库实例）映射到一个哈希环上
  2. 当一个新的数据需要存储或者查询时，先对数据进行哈希处理，得到一个哈希值。
  3. 将该哈希值映射到哈希环上
  4. 数据将存储在距离该哈希值最近的节点上
  5. 如果一个节点失效（例如宕机），则该节点上的数据应当重新映射到其他节点上，但是这个过程只需要重新映射该节点到其后面的第一个节点之间的数据即可
    这样，通过使用分布式一致性哈希算法，可以使得分布式系统中的数据访问负载均衡，并且减少了因节点失效导致的数据迁移量。

根据ip进行hash均衡

  1. 将每个服务器的IP地址进行哈希运算，将其映射到一个哈希环上
  2. 当一个请求到达时，使用与服务器端一样的哈希函数将其源IP地址转化为一个哈希值。
  3. 将该哈希值映射到哈希环上
  4. 然后从该哈希值对应的位置开始，沿着哈希环顺时针方向查找，找到第一个存储服务器的位置，并将请求转发到该服务器上
    因此，通过哈希分布，可以将请求均匀地分布在不同的服务器上，从而实现负载均衡。
    需要注意的是，如果有新的服务器加入或旧的服务器离开，则需要重新计算键的哈希值，并通过调整哈希环的大小，如重新分配存储区域或更改哈希函数等来重新分配负载。

LRU缓存

LRU缓存是一种常见的缓存淘汰算法，其全称是“Least Recently Used”，意为“最近最少使用”。简单来说，LRU缓存在缓存满的情况下，优先淘汰最近最少使用的那些缓存项，以释放空间来存储新的缓存项。其中，使用是指读操作或写操作。

实现LRU缓存需要使用数据结构双向链表（Doubly Linked List）和哈希表（Hash Table）。具体来说，哈希表用于快速查找某个key是否在缓存中，而双向链表则用于维护缓存项的顺序。当一个缓存项被访问时，就将其移动到链表头部，当缓存容量不足时，就淘汰链表尾部的缓存项。

LRU缓存的时间复杂度是O(1)，因为在链表头部和哈希表中查找和移动缓存项的操作都只需要常数时间。而空间复杂度为O(n)，其中n为缓存的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <unordered_map>

struct Node {
    int key, value;
    Node *prev, *next;
    Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
    int cap;
    unordered_map<int, Node*> map;
    Node *head, *tail;
public:
    LRUCache(int capacity) {
        cap = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (!map.count(key)) return -1;
        Node *node = map[key];
        remove(node);
        addFirst(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (map.count(key)) {
            Node *node = map[key];
            node->value = value;
            remove(node);
            addFirst(node);
        } else {
            if (map.size() >= cap) {
                Node *node = tail->prev;
                map.erase(node->key);
                remove(node);
                delete node;
            }
            Node *node = new Node(key, value);
            map[key] = node;
            addFirst(node);
        }
    }

private:
    void remove(Node *node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addFirst(Node *node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
};
// 我们使用了STL库中的unordered_map和list来分别实现哈希表和双向链表。其中，list用于维护缓存条目的访问顺序，unordered_map用于实现快速查找缓存条目。每个缓存条目包含一个键值对和一个过期时间戳，在缓存的访问和淘汰时都要使用到它。
#include <iostream>
#include <unordered_map>
#include <list>
#include <chrono>

using namespace std;

// 缓存条目结构体
struct CacheItem {
    int value;
    chrono::system_clock::time_point expire_time;
};

// 带过期时间的LRU缓存类
class LRUCache {
public:
    LRUCache(int capacity, int expire_time) : m_capacity(capacity), m_expire_time(expire_time) {}
    
    int get(int key) {
        // 如果key不存在，直接返回-1
        if (m_cache_map.find(key) == m_cache_map.end()) {
            return -1;
        }
        
        // 如果key存在但已过期，删除对应的缓存条目，并返回-1
        if (is_expired(key)) {
            m_cache_list.erase(m_cache_map[key]);
            m_cache_map.erase(key);
            return -1;
        }
        
        // 将访问过的缓存条目移动到链表头部
        m_cache_list.splice(m_cache_list.begin(), m_cache_list, m_cache_map[key]);
        return m_cache_map[key]->value;
    }
    
    void put(int key, int value) {
        // 如果key已存在，更新对应的缓存条目的值和过期时间戳，并将其移动到链表头部
        if (m_cache_map.find(key) != m_cache_map.end()) {
            m_cache_list.splice(m_cache_list.begin(), m_cache_list, m_cache_map[key]);
            m_cache_map[key]->value = value;
            m_cache_map[key]->expire_time = chrono::system_clock::now() + chrono::seconds(m_expire_time);
            return;
        }
        
        // 如果缓存已满，先淘汰最久未使用且未过期的缓存条目
        if (m_cache_map.size() == m_capacity) {
            int del_key = m_cache_list.back().first;
            m_cache_list.pop_back();
            m_cache_map.erase(del_key);
        }
        
        // 创建新的缓存条目，并将其插入到链表头部和哈希表中
        m_cache_list.push_front({key, value, chrono::system_clock::now() + chrono::seconds(m_expire_time)});
        m_cache_map[key] = m_cache_list.begin();
    }
    
private:
    bool is_expired(int key) {
        return m_cache_map[key]->expire_time <= chrono::system_clock::now();
    }

    int m_capacity; // 缓存容量
    int m_expire_time; // 缓存过期时间（秒）
    list<CacheItem> m_cache_list; // 缓存条目双向链表
    unordered_map<int, list<CacheItem>::iterator> m_cache_map; // 缓存条目哈希表
};

hash冲突

链式解决：将哈希表的每个槽都设置为链表，哈希冲突的数据可以添加到链表中。这种方法保证了每个数据都可以被哈希表存储，并且允许多个数据共享一个哈希值。

开放地址解决哈希冲突的方法是在哈希表的每个槽存储一个数据，当两个不同的哈希码哈希到了同样的位置上时，就查找这个位置后面的未使用位置，将数据插入该位置。开放地址解决哈希冲突的主要有以下几种方法：

  1. 线性探测法：当哈希表中的某个槽被占用时，线性探测法会在相邻的下一个槽位置上寻找一个空槽。插入的时候，如果哈希表某个位置已经被占用，那么就向下寻找下一个未被占用的位置，并在该位置存储数据。查找操作：从哈希位置开始，线性探测查找目标元素，直到找到匹配的元素或者遇到一个空槽。
  2. 二次探测法：在线性探测法的基础上，二次探测法会按照一定的步长在哈希表中查找可用的位置。例如，如果哈希冲突发生在槽s，则二次探测法会在槽s的1距离、4距离、9距离等位置查找可用槽。查找操作：类似于插入，从哈希位置开始使用二次方程来查找目标元素。
  3. 双重散列法：双重散列法需要两个哈希函数。当哈希冲突发生时，它会使用第一个哈希函数来定位第一个槽，然后使用第二个哈希函数来确定查找下一个可用槽的位置。如果第二个哈希函数计算得到的位置仍然被占用，继续使用第二个哈希函数的其他值，直到找到一个空槽。

相比链式解决哈希冲突的方法，开放地址解决哈希冲突的方法占用更少的内存空间，因为不需要为每个哈希槽分配链表。但是，开放地址解决哈希冲突的方法需要更加小心地设计哈希函数和解决哈希冲突的规则，以避免出现哈希表伸缩问题或者不能找到空槽等问题。