catalog

• 二分哈希

二分哈希

所谓哈希问题，即一个集合里 存了很多数组，比如我们用：VE< T>来表示这个集合。

然后有一个T，问这个T，是否在这里集合里面。

有一种最简单的（二分哈希）

VE< T> A{ t1, t2, t3, ... };

sort( A.begin(), A.end());

bool exist( T t){
	return std::binary_search( A, t);
}

前提是，你的T，必须有 （大小关系）！ 要么重载<，要么放入仿函数。
当然，你规定的比较规则，必须是正确的！！
比如，你： bool operator()( T a, T b){ return true; }，这肯定是错误的。

所谓，（正确的比较规则）是： 如果a < b, b < c，则一定有：a < c

假如，你的T 是标准库的东西（vector，string，，）
那么，你就默认使用 标准库的规则即可！！ 不用管其他的。因为这里的哈希的唯一要求是： 确保（比较规则）是正确的
（而，标准库的比较规则，肯定是正确的）

比如，你集合里 有很多VE<int>（长度不必都相同），“因为标准库对vector的<比较，对不等长也是适用的！”
即，你的集合是： VE< VE<int> > all

现在，每次给你一个VE<int> dest（他的长度和值，都可以是任意的）
、、你需要查询下，这个dest，是否在集合里有出现。

做法是：
sort( all.begin(), all.end());
bool isExist = binary_search( all.begin(), all.end(), dest);

这种方式，非常实用，也非常好写。
但是，时间是：log(n) * O(k)。 k是 vector的长度