我想我会回答这个问题，因为我正在研究一个类似的问题。这种具有高冲突可能性的相似对象散列的想法的名称是“局部敏感散列”。关于这个主题有很多文献，但这里有一个简单的例子：
假设我们有一个固定长度的二进制向量 {1,0}。我们可以使用内置的 stl 和 boost 算法选择一个随机的索引子集来计算哈希：
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <algorithm>
#include <boost/iterator/filter_iterator.hpp>
#include <boost/functional/hash.hpp>
template<class It, class pred>
std::size_t hash_filtered_range(It first, It last, pred f){
return boost::hash_range(boost::make_filter_iterator(f, first, last),
boost::make_filter_iterator(f, last, last));
}
template<class iter>
struct IterableHash{
IterableHash(const iter indices_begin, const iter indices_end): _inc_indices(indices_begin, indices_end){
}
template <class obj_type>
std::size_t operator()(const obj_type& type)const{
int _ix = 0;
return hash_filtered_range(std::begin(type), std::end(type), [this, &_ix](const auto& t){
return (this->_inc_indices.find(_ix++) != this->_inc_indices.end());
});
}
private:
std::unordered_set<int> _inc_indices;
};
template<class hasher>
struct ApproxEqual{
ApproxEqual(const hasher& hash):hash(hash) {}
template<class obj_type>
bool operator() (const obj_type& o1, const obj_type& o2)const{
return hash(o1) == hash(o2);
}
private:
hasher hash;
};
然后，如果可迭代对象仅在以下索引处相等，则它们具有相同的哈希值和相等值：
即在我的电脑上
std::vector<int> hash_vec{0,2,3};
using it = std::vector<int>::iterator;
IterableHash<it> hasher(hash_vec.begin(),
hash_vec.end());
ApproxEqual<IterableHash<it>> cmp(hasher);
std::unordered_map<std::vector<char>, int, IterableHash<it>, ApproxEqual<IterableHash<it>> > map( 0, hasher,
cmp);
std::vector<char> vec {1,0,1,0,1};
map[vec] = 33;
std::cout << hasher(vec)<< "\n";
std::vector<char> fuzzy_vec {1,0,1,0,0};
std::cout << hasher(fuzzy_vec)<< "\n";
std::cout << (map.find(fuzzy_vec)->second);
生产
11093822460655
11093822460655
33
即，当我们使用fuzzy_res 查询时，我们恢复了不同向量res 的值；