哈希表&位图&topk&一致性哈希算法_布隆过滤器 topk

一、哈希表

二、线性探测哈希表

哈希表的长度最好是素数表中的数，哈希表扩容的时候也是从哈希表中取得，扩容后需要把原来表中的数据重新哈希，存入新的哈希表

装载因子：当表的使用量 超过 总容量 * 装载因子 时，需要进行扩容，使用哈希表的 均摊时间复杂度是O(1)

enum State {
	UNUSE,    // 从未被使用
	USING,    // 正在使用
	DELETE    // 使用后被删除
};

struct Node {
	Node(int val = 0, State state = UNUSE) 
		:val_(val)
		, state_(state)
	{}
	int val_;
	State state_; // 节点的状态
};

class HashTable {
public:
	HashTable(int cap = primes_[0], double load_factor = 0.75)
		: load_factor_(load_factor)
		, prime_idx(0)
		, size_(0)
	{
		// 如果用户传入的cap不符合素数表，需要重新指定cap_
		if (cap != primes_[0]) {
			for (; prime_idx < PRIMES_SIZE; prime_idx++) {
				if (primes_[prime_idx] >= cap) {
					break;
				}
			}
			// 用户传入的cap过大，不合法，重新指定cap_
			if (prime_idx == PRIMES_SIZE) {
				prime_idx--;
			}
		}
		cap_ = primes_[prime_idx];
		table_ = new Node[cap_];
	}
	
	~HashTable() {
		delete[] table_;
		table_ = nullptr;
	}

public:
	// 可以插入重复的val
	bool insert(int val) {
		cout << "哈希表使用因子：" << size_ * 1.0 / cap_ << endl;
		if (size_ >= load_factor_ * cap_) {
			cout << "当前使用：" << size_ << " 哈希表总容量：" << cap_ << " 需要扩容" << endl;
			expand();
			cout << "扩容完成，当前容量："<<cap_ << endl;
		}

		int start = val % cap_;
		int idx = start;
		do {
			if (table_[idx].state_ != UNUSE) {
				table_[idx].state_ = USING;
				table_[idx].val_ = val;
				size_++;
				return true;
			}
			idx = (idx + 1) % cap_;
		} while (idx != start);

		return false;
	}

	// 删除所有val
	bool erase(int val) {
		int start = val % cap_;
		int idx = start;
		do {
			// 在用 && 找到
			if (table_[idx].state_ == USING && table_[idx].val_ == val) {
				table_[idx].state_ = DELETE;
				size_--;
			}
			idx = (idx + 1) % cap_;
		} while (table_[idx].state_ != UNUSE && idx != start);  // 若碰到了UNUSE，则说明后面肯定没有自己要找的val了
		return true;
	}
	
	// 找到val返回对应的key，找不到返回-1
	int find(int val) {
		int start = val % cap_;
		int idx = start;
		do {
			// 在用 && 找到
			if (table_[idx].state_ == USING && table_[idx].val_ == val) {
				return idx;
			}
			idx = (idx + 1) % cap_;
		} while (table_[idx].state_ != UNUSE && idx != start);  // 若碰到了UNUSE，则说明后面肯定没有自己要找的val了
		return -1;
	}

private:
	void expand() {
		prime_idx++;
		if (prime_idx == PRIMES_SIZE) {
			throw "current hashtable is too large, can't expand anymore!";
		}
		Node* tmp = new Node[primes_[prime_idx]];
		for (int i = 0; i < cap_; i++) {
			if (table_[i].state_ == USING) {
				// 取出旧表中的元素，在新表中重新哈希
				int start = table_[i].val_ % primes_[prime_idx];
				int idx = start;
				do {
					if (tmp[idx].state_ != USING) {
						tmp[idx].state_ = USING;
						tmp[idx].val_ = table_[i].val_;
						break;       // 新表中插入一个元素后，就可以跳出查找位置的while循环
					}
					idx = (idx + 1) % primes_[prime_idx];
				} while (idx != start);
			}
		}
		cap_ = primes_[prime_idx];
		delete[] table_;
		table_ = tmp;
	}

private:
	Node* table_;
	int cap_;                      // 哈希表的容量
	int size_;                     // 已经使用的空间
	double load_factor_;           // 装载因子
	
	static const int PRIMES_SIZE = 10;
	static const int primes_[PRIMES_SIZE];
	int prime_idx;                 // 当前哈希表使用的素数
};

const int HashTable::primes_[PRIMES_SIZE] = { 3,7,23,47,251,443,911,1471,42773 };

int main() {
	HashTable h_table;
	h_table.insert(21);
	h_table.insert(32);
	h_table.insert(14);
	h_table.insert(15);
	h_table.insert(22);
	cout << h_table.find(21) << endl;
	h_table.erase(21);
	cout << h_table.find(21) << endl;
	
	return 0;
}
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

缺点：

1. 发生冲突时，线性探测的过程会逐渐逼近O(n)，存储会比较慢
2. C++ STL中的所有容器都不是线性安全的，需要额外进行同步互斥操作，并且锁的粒度很大，需要锁住整个数组。

三、链式哈希表

若使用线性探测哈希表，要锁住整个数组。使用链式哈希表，则可以只使用分段的锁（锁住一个桶即可），既保证了线程安全，又有一定的并发量，提高了效率

优化空间：

1. 当数组里每个链表过长时，可以把链表转成红黑树O(n)
2. 链式哈希表都可以创建自己的锁（分段锁），不同的桶中的操作是可以并发的

class HashTable {
public:
	// size用于初始化vector的大小
	HashTable(int size = primes_[0], double load_factor=0.75)
		: load_factor_(load_factor)
		, prime_idx(0)
		, use_num(0)
	{
		if (size != primes_[0]) {
			for (; prime_idx < PRIMES_SIZE; prime_idx++) {
				if (primes_[prime_idx] >= size) {
					break;
				}
			}
			if (prime_idx == PRIMES_SIZE) {
				prime_idx--;
			}
		}
		// 开辟空间，并且创建元素:table_.size() == primes_[prime_idx] && table_.capacity == primes_[prime_idx]
		table_.resize(primes_[prime_idx]);  
	}

	// 实现为不可重复插入
	bool insert(int val) {
		bool inserted = false;
		double factor = use_num * 1.0 / table_.size();
		cout << "当前装载因子：" << factor << endl;
		if (factor >= load_factor_) {
			cout <<" 需要扩容" << endl;
			expand();
			cout << "扩容完成，当前容量："<<table_.size() << endl;
		}
		int idx = val % table_.size();
		if (table_[idx].empty()) {
			use_num++;
			table_[idx].emplace_front(val);     // 链表头插
			inserted = true;
		}
		else {
			auto iter = ::find(table_[idx].begin(), table_[idx].end(), val);
			if (iter == table_[idx].end()) {
				// 当前插入的值不存在，则插入链表
				table_[idx].emplace_front(val); // 链表头插
				inserted = true;
			}
		}
		return inserted;
	}

	// 删除元素
	bool erase(int val) {
		int idx = val % table_.size();
		// 如果链表节点过长，说明散列函数有问题，如果散列结果很离散，链表不会很长
		auto iter = ::find(table_[idx].begin(), table_[idx].end(), val);
		if (iter != table_[idx].end()) {
			table_[idx].erase(iter);
			if (table_[idx].empty()) {
				use_num--;        // 删完后当前链表为空，则调整vector已经使用的个数
			}
			return true;
		}
		return false;
	}

	bool find(int val) {
		int idx = val % table_.size();
		auto iter = ::find(table_[idx].begin(), table_[idx].end(), val);
		return iter != table_[idx].end();
	}

private:
	void expand() {
		if (prime_idx + 1 == PRIMES_SIZE) {
			throw "hash table can't expand anymore!";
		}
		vector<list<int>> tmp;     // 资源交换过来后，局部变量出作用域自动析构
		table_.swap(tmp);          // 若使用相同的容器适配器，只是交换成员变量
		table_.resize(primes_[++prime_idx]);

		// 遍历旧表中的元素，然后重新哈希
		for (list<int> l : tmp) {
			for (int val : l) {
				int idx = val % table_.size();
				if (table_[idx].empty()) {
					use_num++;
				}
				table_[idx].emplace_front(val); // 链表头插
			}
		}
	}

private:
	vector<list<int>> table_;
	double load_factor_;           // 装载因子
	int use_num;

	static const int PRIMES_SIZE = 10;
	static const int primes_[PRIMES_SIZE];
	int prime_idx;                 // 当前哈希表使用的素数
};

const int HashTable::primes_[PRIMES_SIZE] = { 3,7,23,47,251,443,911,1471,42773 };
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

四、哈希表相关面试题

1. 有两个文件，分别存放了一些ip地址，找出同时在两个文件中都出现的ip地址

把一个文件的ip放在一个哈希表，然后遍历另一个文件的同时在哈希表中查找，找到则输出

2. 有两个文件，分别存放了1亿个数，每条数字4B，限制内存100MB，找出同时在两个文件中都出现的数

1亿 约等于 100M
100M * 4B = 400MB数据 ==> 放入链式哈希表后，还需要增加400MB的地址域，一共800MB

将两个大文件分成足够多的小文件，使得哈希过后将数字存入每个小文件的数据不至于超过100MB，这样相同的数必然会被哈希到下标相同的小文件中。

把某个a小文件全部读入内存中的哈希表，然后从下标相同的b文件中挨个读取数据，然后在哈希表中查找，找到则在两个文件中重复出现

五、位图大数据查重

现在有1亿个数据，最大值为1亿，每个数字4B，限制内存100MB

若使用哈希表，需要使用100M * 4B * 2 = 800MB

使用位图，则只需要使用100000000bit，(100000000/8+1)B = 12500000B = 12.5MB

位操作： | 是赋值的，&是求值的

template<typename T>
void show_repeat(const vector<int>& vec, T bit_map_type = char()) {
	int max_val = *max_element(vec.begin(), vec.end());
	char* bitmap = new char[max_val / (sizeof(char) * 8) + 1]();
	unique_ptr<char> ptr(bitmap);

	for (int v : vec) {
		int index = v / (sizeof(T) * 8);
		int offset = v % (sizeof(T) * 8);
		// &用于取出某个bit，|用于对某个bit赋值
		if ((bitmap[index] & (1 << offset)) == 0) {
			bitmap[index] |= (1 << offset);
		}
		else {
			cout << v << "重复" << endl;
		}
	}
}

int main() {
	vector<int> vec = {42,3,45,423,15,1,23,1,3412,45,12,45,2,65,412,5,4};
	show_repeat(vec, int());
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

位图适用场景： 数据数量和数据的最大值相当的时候适用，不适用于数据很少，但是最大值很大的情况，因为要按照最大值开辟内存空间

六、布隆过滤器Bloom Filter

增加元素： 把key用k个哈希函数计算后，得到一组下标，将Bloom Filter中对应的bit置为1

搜索元素： 把key用k个哈希函数计算后，得到一组下标，若Bloom Filter中对应的bit全为1，那这个key有可能存在，若对应的bit不全为1，则key肯定不在。Bloom Filter存在一定的误判率，但随着其长度和哈希函数的增加，误判率会大大降低

删除元素： Bloom Filter不提供删除操作，若key1和key2有公用的bit，删除key1对应的bit后，那也改变了key2对应的bit，再查找key2的时候，也就查不到key2了

一些应用场景


优点： 结合了哈希表的效率高和位图的省内存的优点，但是会存在一定的误判率，但随着其长度和哈希函数的增加，误判率会大大降低

#include<iostream>
#include<vector>
#include<string>
#include"stringhash.h"

using namespace std;

class BloomFilter {
public:
	BloomFilter(int bit_cap = 1471)
		: bit_cap_(bit_cap)
		, type_size_(sizeof(char))
	{
		bit_map_.resize(bit_cap_ / (type_size_ * 8) + 1);
	}
	
	// 往Bloom Filter中插入key
	void set_bit(const char* key) {
		int idx1 = BKDRHash(key) % bit_cap_;
		int idx2 = RSHash(key) % bit_cap_;
		int idx3 = APHash(key) % bit_cap_;

		int index = 0;
		int offset = 0;
		
		index = idx1 / (type_size_ * 8);
		offset = idx1 % (type_size_ * 8);
		bit_map_[index] |= (1 << offset);

		index = idx2 / (type_size_ * 8);
		offset = idx2 % (type_size_ * 8);
		bit_map_[index] |= (1 << offset);

		index = idx3 / (type_size_ * 8);
		offset = idx3 % (type_size_ * 8);
		bit_map_[index] |= (1 << offset);
	}

	// 查询key是否存在于Bloom Filter
	bool get_bit(const char* key) {
		int idx1 = BKDRHash(key) % bit_cap_;
		int idx2 = RSHash(key) % bit_cap_;
		int idx3 = APHash(key) % bit_cap_;

		int index = 0;
		int offset = 0;

		index = idx1 / (type_size_ * 8);
		offset = idx1 % (type_size_ * 8);
		if ((bit_map_[index] & (1 << offset)) == 0) {
			return false;
		}

		index = idx2 / (type_size_ * 8);
		offset = idx2 % (type_size_ * 8);
		if ((bit_map_[index] & (1 << offset)) == 0) {
			return false;
		}

		index = idx3 / (type_size_ * 8);
		offset = idx3 % (type_size_ * 8);
		if ((bit_map_[index] & (1 << offset)) == 0) {
			return false;
		}

		return true;
	}
	
private:
	int bit_cap_;
	int type_size_;
	vector<char> bit_map_; 
};

class BlackList {
public:
	void add(string url) {
		bloom_filter_.set_bit(url.c_str());
	}

	bool query(string url) {
		return bloom_filter_.get_bit(url.c_str());
	}
private:
	BloomFilter bloom_filter_;
};

int main() {
	BlackList b_list;
	b_list.add("www.baidu.com");
	b_list.add("www.alibaba.com");
	b_list.add("www.tencent.com");
	cout << b_list.query("www.baidu.com") << endl;
	cout << b_list.query("www.alibaba.com") << endl;
	cout << b_list.query("www.tencent.com") << endl;
	cout << b_list.query("www.bytedance.com") << endl;
	return 0;
}
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

这里总结一下Bloom Filter的注意事项：

1. Bloom Filter是通过一个位数组+k个哈希函数构成的。
2. Bloom Filter的空间和时间利用率都很高，但是它有一定的错误率，虽然错误率很低，Bloom Filter判断某个元素不在一个集合中，那该元素肯定不在集合里面；Bloom Filter判断某个元素在一个集合中，那该元素有可能在，有可能不在集合当中。
3. Bloom Filter的查找错误率，当然和位数组的大小、哈希函数的个数有关系，具体的错误率计算有相应的公式（错误率公式的掌握看个人理解，不做要求）。
4. Bloom Filter默认只支持add增加和query查询操作，不支持delete删除操作（因为存储的状态位有可能也是其它数据的状态位，删除后导致其它元素查找判断出错）。

Bloom Filter增加元素的过程： 把元素的值通过k个哈希函数进行计算，得到k个值，然后把k当作位数组的下标，在位数组中把相应k个值修改成1。

Bloom Filter查询元素的过程： 把元素的值通过k个哈希函数进行计算，得到k个值，然后把k当作位数组的下标，看看相应位数组下标标识的值是否全部是1，如果有一个为0，表示元素不存在（判断不存在绝对正确）；如果都为1，表示元素存在（判断存在有错误率）。

所以用Bloom Filter需要少量的内存就可以判断元素是否存在集合当中，当需要查找同时在a、b两个大文件中都出现的元素时，我们可以用a文件的数据构建Bloom Filter的位数组中的状态值，然后再读取b文件的数据进行布隆过滤的查找操作就可以了

参考：https://blog.csdn.net/QIANGWEIYUAN/article/details/88815772

七、topK问题

（1）堆排序求topk

求最小的K个元素，用大根堆：堆中加入小的，淘汰大的

求最大的K个元素，用小根堆：堆中加入大的，淘汰小的
时间复杂度： O(logK)*O(n) = O(n)

手写堆，实现求最大的k个数

求出最大的K个元素，使用小根堆
把数组前K个元素建立一个小根堆，从前K个元素第一个内部节点（K-1）/2开始建堆

建堆完成后，开始遍历数组的其他元素

1. 若当前元素大于堆顶元素，则淘汰堆顶元素，将当前元素放在堆顶，然后对堆顶元素调堆

2. 若当前元素小于堆顶元素，则直接遍历下一个元素

// 在[0,size-1]的范围内调堆，使下标为cur的元素满足堆性质
void sift_down(int arr[], int cur, int size) {
	int val = arr[cur];
	int n = size - 1;
	while (cur <= (size - 2) / 2) {
		int min_child = 2 * cur + 1;   // 若满足while循环条件，则必然存在左孩子
		if (2 * cur + 2 <= n) {
			min_child = arr[min_child] < arr[2 * cur + 2] ? min_child : 2 * cur + 2;
		}
		if (arr[min_child] < val) {
			arr[cur] = arr[min_child];
			cur = min_child;
		}
		else {
			break;
		}
	}
	arr[cur] = val;
}

int main() {
	int arr[10] = { 11,54,62,45,27,98,7,625,37,59 };
	int k = 5;
	for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
		sift_down(arr, i, k);  // 下标为 0 ~ k-1 的前k个元素建小顶堆   
	}

	int n = sizeof(arr) / sizeof(arr[0]);
	for (int i = k; i < n; i++) {
		if (arr[i] > arr[0]) {
			arr[0] = arr[i];       // 大于堆顶元素，则放在堆顶，然后调堆
			sift_down(arr, 0, k);
		}
		else {
			continue;              // 比小顶堆的堆顶元素还小，一定不是前k大的数，跳过
		}
	}
	for (int i = 0; i < k; i++) {
		cout << arr[i] << " ";     // 数组前k个元素就是最大的k个
	}
	return 0;
}
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

使用内置的优先级队列和哈希表实现统计出现次数最少的k个数字

int main() {
	int k = 5;
	vector<int> vec;
	srand(time(nullptr));
	for (int i = 0; i < 1000; i++) {
		vec.push_back(rand() % 100);
	}

	// 统计元素出现的个数
	unordered_map<int, int> mp;
	for (int key : vec) {
		mp[key]++;
	}

	using Type = pair<int, int>;
	using Comp = function<bool(Type&, Type&)>;
	priority_queue<Type, vector<Type>, Comp> max_heap(
		[](Type& a, Type& b)->bool {
			return a.second < b.second;  // 大根堆
		}
	);

	auto iter = mp.begin();
	for (int i = 0; i < k; i++, iter++) {
		max_heap.push(*iter);
	}
	for (; iter != mp.end(); iter++) {
		if (iter->second < max_heap.top().second) {
			max_heap.pop();
			max_heap.push(*iter);
		}
	}

	while (!max_heap.empty()) {
		cout <<"value:"<< max_heap.top().first << " times:" << max_heap.top().second << endl;
		max_heap.pop();
	}
	return 0;
}
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

（2）快排分割求topk

int partition(int arr[], int begin, int end, int k) {
	int l = begin;
	int r = end;
	int val = arr[l];
	
	while (l < r) {
		while (l < r && arr[r] > val) r--;
		
		if (l < r) {
			arr[l] = arr[r];
			l++;
		}

		while (l < r && arr[l] < val) l++;
		
		if (l < r) {
			arr[r] = arr[l];
			r--;
		}
		
	}
	arr[l] = val;
	return l;
}

// 递归函数作用：能把[begin, end]区间内，前topk的元素放在[0, k]
void select_topk(int arr[], int begin, int end, int k) {
	int pos = partition(arr, begin, end, k);
	if (pos == k - 1) {
		return;
	}
	else if (pos < k - 1) {
		select_topk(arr, pos + 1, end, k);
	}
	else {
		select_topk(arr, begin, pos - 1, k);
	}
}
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

最好时间复杂度： 每次基准数都在中间，二叉树很平衡，n+n/2+…+1 = O(n)
最坏时间复杂度： 数据本就有序，基准数每次都在最边上，二叉树退化为链表，O(n^2)

八、一致性哈希算法

（1）负载场景

经过哈希算法hash(ip:port)%N，同一客户的请求都会被映射到相同的服务器上，这有效解决了会话共享 的问题，这时候就不需要加入redis缓存服务器去记录客户的登录状态，避免引用外部模块过多导致系统不稳定的问题。

但这种方法也有问题，比如当某个服务器宕机了（或增加服务器），这时候N的值就发生改变，导致相同客户的请求就不一定还会转发到以前那台服务器上，这会发生身份认证的问题。

我们想要的是 同一 ip:port 的请求，永远被映射到同一台server上处理

（2）缓存场景

客户通常发请求查询信息的时候，是现在缓存服务器上查找，查找不到再到DB查找，然后把数据从DB转移到缓存服务器。

1. 若此时有一台服务器宕机了，同理在2号缓存服务器中的信息再次被查询时，这个请求很有可能会被转发到1号服务器，此时无法在1号缓存服务器中找到信息，就会去DB中查找，此时大量的磁盘IO会严重影响server的响应速度。更严重来讲，一台服务器的负载太高，可能会影响整个系统的运转，甚至崩溃

2. 若此时增加了一台服务器，N发生改变。举个极端的例子，此时所有的请求都被转发到新的服务器中，新的服务器无法查询到相应信息，同理会产生大量的磁盘IO，甚至服务器崩溃

我们的理想情况是：

1. 某个server挂了，不影响其他server的正常运转，其他server的请求不会急剧增加
2. server增加了，尽可能少影响原来server的请求，而只是把后续的请求映射到新的server上

（3）解决方法：一致性哈希算法

为解决普通哈希算法导致的以上问题，提出一致性哈希算法（分布式系统负载均衡的首选算法）

一个良好的分布式哈希方案应该具有良好的单调性，即服务节点数量的改变不会造成大量哈希的重新定位

算法过程

容错性分析

1. 假设server A 宕机了，那原来在server C的请求2、3依然在server C，原来在server B的请求4依然在server B，只是原来在server A的请求会被转发到server C
2. 假设多了一台server D放在如下位置，这只会影响新增server D与逆时针碰到的第一个server C之间的请求4，不会影响到其他的请求，这将影响降到了最低

为了达到良好的负载均衡，经过一致性哈希算法后的 server最好在哈希环上分散开，所以一般我们要在哈希环上加入物理节点的虚拟节点。加入物理节点的虚拟节点可防止由于物理节点过少，导致哈希处理后几台服务器挤在一起，从而导致某一台主机的负载过多，而其他空闲的情况

类设计如下：

#include<iostream>
#include<set>
#include<list>
#include<map>
#include<string>
#include"md5.h"

using namespace std;
using uint = unsigned int;

class PhysicalHost;

class VirtualHost {
public:
	VirtualHost(string ip, PhysicalHost* phy_host_ptr) 
	: ip_(ip)
	, phy_host_ptr_(phy_host_ptr)
	{
		md5_ = getMD5(ip_.c_str());
	}

	// 虚拟节点存放到set的时候，需要排序，默认less，需要提供operator<
	bool operator<(const VirtualHost& vir_host) const {
		// 根据md5值排序
		return md5_ < vir_host.md5_;
	}

	// 删除哈希环上的虚拟节点时，需要查找，重载operator==
	bool operator==(const VirtualHost& vir_host) const {
		return ip_ == vir_host.ip_;
	}

	const uint get_md5() const {
		return md5_;
	}

	const PhysicalHost* get_phy_host() const {
		return phy_host_ptr_;
	}
private:
	string ip_;                   // 虚拟节点记录的ip信息
	uint md5_;                    // 根据物理节点的ip计算的ip值得到的MD5，这是32位加密串运算得到的uint
	PhysicalHost* phy_host_ptr_;  // 指向实际的物理节点
};

class PhysicalHost {
public:
	// 物理节点的ip，创建虚拟节点的个数
	PhysicalHost(string ip, int v_number)
	: ip_(ip)
	{
		for (int i = 0; i < v_number; i++) {
			// 虚拟节点需要记录物理主机的ip以及对应的物理节点
			virtual_hosts_.push_back(VirtualHost(ip_ + "#" + ::to_string(i), this));
		}
	}

	const string get_ip() const{
		return ip_;
	}

	const list<VirtualHost>& get_virtual_hosts() const {
		return virtual_hosts_;
	}

private:
	string ip_;
	list<VirtualHost> virtual_hosts_;  // 双向循环链表
};

class ConsistentHash {
public:
	// 添加物理主机的虚拟节点到一致性哈希环
	void add_host(PhysicalHost& phy_host) {
		auto vir_list = phy_host.get_virtual_hosts();
		for (auto vir_host : vir_list) {
			hash_circle_.insert(vir_host);
		}
	}

	// 删除哈希环物理节点所有的虚拟节点
	void del_host(PhysicalHost& phy_host) {
		auto vir_list = phy_host.get_virtual_hosts();
		for (auto vir_host : vir_list) {
			// 红黑树查找，O(log2n)
			auto iter = hash_circle_.find(vir_host);
			if (iter != hash_circle_.end()) {
				hash_circle_.erase(iter);
			}
		}
	}

	// 根据客户的ip，计算其对应的虚拟主机，然后根据虚拟主机返回真是的物理主机的ip
	string get_client_host(string client_ip) const{
		uint client_md5 = getMD5(client_ip.c_str());
		// 找第一个比客户ip的md5大的虚拟主机
		for (VirtualHost vir_host : hash_circle_) {
			if (vir_host.get_md5() > client_md5) {
				return vir_host.get_phy_host()->get_ip();
			}
		}
		// 客户的ip得到的md5过大，无法找到更大的md5，那直接分配第一个虚拟节点
		return hash_circle_.begin()->get_phy_host()->get_ip();
	}

private:
    // 由于需要顺时针查找，需要排序，所以一致性哈希算法底层用到红黑树
	set<VirtualHost> hash_circle_;
};

void show_consistent_hash(const ConsistentHash& hash_circle) {
	list<string> client_ip_list{
		"192.168.1.100",
		"192.168.1.101",
		"192.168.1.102",
		"192.168.1.103",
		"192.168.1.104",
		"192.168.1.105",
		"192.168.1.106",
		"192.168.1.107",
		"192.168.1.108",
		"192.168.1.109",
		"192.168.1.110",
		"192.168.1.111",
		"192.168.1.112",
		"192.168.1.113",
	};

	// 物理服务器ip  所服务的客户端ip
	map<string, list<string>> ip_map;
	for (string client_ip : client_ip_list) {
		// 根据客户端的ip，计算哈希环上的虚拟主机，从而拿到对应物理主机的ip
		string phy_host_ip = hash_circle.get_client_host(client_ip);  
		ip_map[phy_host_ip].push_back(client_ip);
	}
	for (auto pair : ip_map) {
		cout << "server ip :" << pair.first << endl;
		cout << "该服务器服务的客户端有" << pair.second.size() << "个" << endl;
		cout << "client ip :" << endl;
		for (string client_ip : pair.second) {
			cout << client_ip << endl;
		}
		cout << "-----------------------------" << endl;
	}
}

int main() {
	PhysicalHost phy_host1("10.117.121.66", 200);
	PhysicalHost phy_host2("10.117.121.67", 200);
	PhysicalHost phy_host3("10.117.121.68", 200);
	
	ConsistentHash hash_circle;
	hash_circle.add_host(phy_host1);
	hash_circle.add_host(phy_host2);
	hash_circle.add_host(phy_host3);
	
	show_consistent_hash(hash_circle);
	hash_circle.del_host(phy_host2);
	cout << "*********主机2宕机*********" << endl;
	show_consistent_hash(hash_circle);

	return 0;
}
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

server ip :10.117.121.66
该服务器服务的客户端有3个
client ip :
192.168.1.105
192.168.1.109
192.168.1.112
-----------------------------
server ip :10.117.121.67
该服务器服务的客户端有5个
client ip :
192.168.1.100
192.168.1.102
192.168.1.103
192.168.1.107
192.168.1.110
-----------------------------
server ip :10.117.121.68
该服务器服务的客户端有6个
client ip :
192.168.1.101
192.168.1.104
192.168.1.106
192.168.1.108
192.168.1.111
192.168.1.113
-----------------------------
*********主机2宕机*********
server ip :10.117.121.66
该服务器服务的客户端有4个
client ip :
192.168.1.105
192.168.1.109
192.168.1.110
192.168.1.112
-----------------------------
server ip :10.117.121.68
该服务器服务的客户端有10个
client ip :
192.168.1.100
192.168.1.101
192.168.1.102
192.168.1.103
192.168.1.104
192.168.1.106
192.168.1.107
192.168.1.108
192.168.1.111
192.168.1.113
-----------------------------
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

该代码需要md5源码才可运行，需要可以私信