hash_pair

hash_2_3.cxx

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>

using namespace std;

// 双射函数
// proven : 
// as 
/*
  1 2  3 4
  --------
1|1 2 4 7
2|3 5 8
3|6 9
4|10
first get the diagonal line @ m + n , so the total numbers before this line is sum(m + n)
then this number (m, n) is the m-th point of this diagonal line  (any point  will mapping to -> cord x &y, so you can add m or n either)
*/

int64_t hash_2(int64_t m, int64_t n) {
	int64_t t = m + n;
	return (t + 1) * t / 2 + m;
}

// then we get three number hash-function
int64_t hash_3(int64_t m, int64_t n, int64_t k) {
	// can be hash_2(hash_2(m, n), k)
	int64_t t = (m + n + k);
	t = (t + 1) * t / 2;
	t = t * t;
	return t + hash_2(m, n);
}

int main(){
	map<int64_t, tuple<int64_t, int64_t, int64_t> > sTest;	
	int64_t n = 500;
	for (int64_t i = 0; i < n; ++i) {
		for (int64_t j = 0; j < n; ++j) {
			for (int64_t k = 0; k < n; ++k) {
				int64_t t = hash_3(i, j, k);
				auto it = sTest.find(t);
				if (it != sTest.end())
				{
					int64_t a,b,c;
					tie(a, b,c) = (*it).second;
					printf("(%d,%d,%d) & (%d,%d,%d) ->%d\n", a, b, c, i, j, k, t); // this setence will never executed.
					continue;
				}
				sTest.insert(make_pair(t, make_tuple(i, j, k)));
			}
		}
	}
	system("pause");
	return 0;
}