假设您有两个哈希H(A)并且H(B)您想要将它们组合在一起.我已经读到了将两个哈希值组合在一起的好方法XOR,例如XOR( H(A), H(B) ).
我发现的最佳解释在这里简要介绍了这些哈希函数指南:
对具有大致随机分布的两个数字进行异或,导致另一个数字仍具有大致随机分布*,但现在取决于这两个值.
...
*在两个数字相结合的每个比特,一个输出0,如果两个比特相等,否则为1.换句话说,在组合的50%,1将输出.因此,如果两个输入位各有大约50-50的机会为0或1,那么输出位也是如此.
你能解释为什么XOR应该是组合散列函数(而不是OR或AND等)的默认操作的直觉和/或数学吗？
我在其他帖子中读到,这似乎是组合哈希值的最佳方式.有人可以打破这一点,并解释为什么这是最好的方法吗？
template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
std::hash<T> hasher;
seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
编辑:另一个问题只是要求神奇的数字,但我想知道整个功能,而不仅仅是这一部分.
我可以在C++中创建一个无序的向量集吗？这样的事情
std::unordered_set<std::vector<int>> s1;
因为我知道std lib的"set"类是可能的,但似乎它不适用于无序版本谢谢
更新:这是我正在尝试使用的确切代码
typedef int CustomerId;
typedef std::vector<CustomerId> Route;
typedef std::unordered_set<Route> Plan;
// ... in the main
Route r1 = { 4, 5, 2, 10 };
Route r2 = { 1, 3, 8 , 6 };
Route r3 = { 9, 7 };
Plan p = { r1, r2 };
如果我使用set,它可以,但在尝试使用无序版本时收到编译错误
main.cpp:46:11: error: non-aggregate type 'Route' (aka 'vector<CustomerId>') cannot be initialized with an initializer list
Route r3 = { 9, 7 };
问题
对于用户定义类型的std :: unordered_map或std :: unordered_set的第三个模板参数,std :: hash有什么好的特殊性,所有成员数据类型都已经具有良好的std :: hash特性？
对于这个问题,我将"好"定义为易于实现和理解,合理有效,并且不太可能产生哈希表冲突.商品的定义不包括任何有关安全性的陈述.
什么是谷歌的状态
目前,两个StackOverflow问题是Google搜索"std hash specialization"的第一个问题.
第一个,如何在无序容器中为用户定义的类型专门化std :: hash :: operator()？,解决了打开std命名空间和添加模板特化是否合法的问题.
第二个,如何专门化来自其他库的类型的std :: hash,基本上解决了同样的问题.
这留下了当前的问题.鉴于C++标准库的实现为标准库中的基本类型和类型定义了散列函数,为用户定义的类型专门化std :: hash的简单有效方法是什么？有没有一种很好的方法来组合标准库实现提供的哈希函数？
(编辑感谢dyp.)StackOverflow的另一个问题是如何组合一对哈希函数.
谷歌的其他结果没有任何帮助.
这篇 Dobbs博士的文章指出,两个令人满意的哈希的XOR将产生一个新的令人满意的哈希值.
这篇文章似乎是从知识中说出并暗示了很多东西,但却注重细节.它与第一个例子中的简短评论中的Dr. Dobbs文章相矛盾,称使用XOR组合散列函数会产生一个弱的结果散列函数.
因为XOR应用于任何两个相等的值导致0,我可以看出为什么XOR本身很弱.
元问题
一个很好的理由回答解释为什么这个问题无效且一般无法回答也是受欢迎的.
我正在尝试创建一组无序的对
到目前为止,我有:
typedef std::pair<int, int> Move;
typedef std::unordered_set<Move> Set;
我将在未来制作一套Move,现在我只有:
Set* King::possibleMoves()
{
Set hello; <-------- THINK ERROR OCCURS HERE
return &hello;
}
但我一直得到这3个错误:
`/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../lib/c++/v1/type_traits:770:38: error:
implicit instantiation of undefined template 'std::__1::hash<std::__1::pair<int, int>
>'
: public integral_constant<bool, __is_empty(_Tp)> {};
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../lib/c++/v1/memory:1951:40: note:
in instantiation of template class
'std::__1::is_empty<std::__1::hash<std::__1::pair<int, int> > >' requested here
bool = is_empty<_T2>::value
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../lib/c++/v1/memory:1973:44: note:
in instantiation of default argument for '__libcpp_compressed_pair_switch<unsigned
long, std::__1::hash<std::__1::pair<int, int> >, false, false>' required here
template <class _T1, class _T2, unsigned …boost::hash 具有大多数内置类型(包括容器)的散列函数.
但正如boost::hash_range函数描述中所述,范围的哈希算法
对元素的顺序很敏感,因此将它与无序容器一起使用是不合适的
因而,没有boost::hash专业化std::unordered_map,也没有boost::unordered_map.
问题是:
如果unordered_map没有从头开始重新实现哈希算法,是否有"简单而有效"的方法来哈希？
正如在回答指出了在unordered_map / unordered_set通用哈希元组和其他地方，加速了实现的boost::hash<tuple<string, string>>。
所以，我们可以做这样的事情：
#include <boost/functional/hash.hpp>
#include <boost/unordered_map.hpp>
std::tuple<string, string> t;
size_t bh = boost::hash<tuple<string, string>>{}(t);
boost::unordered_map<tuple<string, string>, int> bm;
但不是：
size_t sh = std::hash<tuple<string, string>>{}(t); // error C2338: The C++ Standard doesn't provide a hash for this type.
std::unordered_map<tuple<string, string>, int> sm; // same error
为什么它没有进入 C++ 标准？
由委员会或其他专家给出理由的参考文献的额外加分。
我有一个这样定义的圆：
class Circle {
public:
int x;
int y;
int r;
Circle() : x(0), y(0), r(0) {}
Circle(int x, int y, int r) {
this->x = x;
this->y = y;
this->r = r;
}
double area() {
return PI * pow(r, 2);
}
};
我希望能够根据其中心（x和y）的哈希将其添加到集合中
在 C++ 11 中执行此操作的正确且惯用的方法是什么？
我的问题有两个
(1) 有没有办法让 C++ 帮我哈希它？在 Kotlin 中，有一个数据类的概念，它会自动对类属性进行哈希处理。我正在寻找类似的东西。
(2) 如果没有，我如何自己对其进行哈希处理，以及相关的 - 我需要重载哪些运算符？
我必须编写一个哈希函数,以便我可以放入std::pair<int,std::string>一个unordered_set.
关于输入:
使用字符串的哈希值(作为数字)是否有意义,并且只使用Cantor的对的枚举来生成"新"哈希？
由于"内置"哈希函数std::string应该是一个不错的哈希函数...
struct intStringHash{
public:
inline std::size_t operator()(const std::pair<int,std::string>&c)const{
int x = c.first;
std::string s = c.second;
std::hash<std::string> stringHash;
int y = stringHash(s);
return ((x+y)*(x+y+1)/2 + y); // Cantor's enumeration of pairs
}
};
我正在尝试编写康威的"生命游戏".在接近我的目标时,我遇到了编译错误:
C2338:C++库不提供此类型的哈希值.
起初我使用了SFML类sf::Vector2D.当它无法为我工作时,我写了一个属于我自己的类,希望我能实现丢失的hashCode方法.
我的问题是:
是否可以使用我自己的类使用自己的hashCode方法std::unordered_map？我需要使用一个可以容纳两个数字的类.(我也尝试过std::tuple,但是struct东西).
这是我的一张代码:
#include "GameMechanics.h"
GameMechanics::GameMechanics(Elements * elements):elements(elements)
{
this->refreshTime = 1000000; //ms
this->clock.restart();
}
GameMechanics::~GameMechanics()
{
}
bool GameMechanics::isRunning()
{
return this->running;
}
void GameMechanics::setRunning(bool running)
{
this->running = running;
}
void GameMechanics::loop()
{
unsigned passedTime = clock.getElapsedTime().asMicroseconds(); //check passed time since the clock got restarted
this->timeHeap += passedTime; //add passed time to the timeheap
this->clock.restart();
//only refresh every "refreshTime" seconds
if (timeHeap >= …我有两个整数数组
int A[] = {2, 4, 3, 5, 6, 7};
int B[] = {9, 2, 7, 6};
而且我必须得到这些数组的交集.
即输出为-2,6,7
我想通过在数据结构中保存数组A然后我想要比较所有元素直到大小A或B然后我将得到交集.
现在我有一个问题,我需要首先将数组A的元素存储在容器中.
我会跟着像 -
int size = sizeof(A)/sizeof(int);
为了获得大小,但通过这样做,我将获得大小后,我想访问所有元素也存储在容器中.
在这里,我用来找到交叉点的代码 - >
#include"iostream"
using namespace std;
int A[] = {2, 4, 3, 5, 6, 7};
int B[] = {9, 2, 7, 6};
int main()
{
int sizeA = sizeof(A)/sizeof(int);
int sizeB = sizeof(B)/sizeof(int);
int big = (sizeA > sizeB) ? sizeA : sizeB;
int small = (sizeA > sizeB) ? sizeB …