我知道我可以将奇异值作为键中的哈希值dict.例如,我可以将哈希5作为其中一个键dict.
我目前面临一个问题,需要我散列一系列值.
基本上,我需要一种更快的方法来做到这一点:
if 0 <= x <= 0.1:
# f(A)
elif 0.1 <= x <= 0.2:
# f(B)
elif 0.2 <= x <= 0.3:
# f(C)
elif 0.3 <= x <= 0.4:
# f(D)
elif 0.4 <= x <= 0.5:
# f(E)
elif 0.5 <= x <= 0.6:
# f(F)
其中x是一些float任意精度的参数.
我能想到的最快的方法是散列,但问题在于:我可以(0.1, 0.2)用作键,但这仍然会花费我O(n)运行时间,并且最终并不比elifs的更好(我必须迭代键并检查是否key[0] <= x <= key[1]).
有没有办法散列一系列值,以便我可以检查哈希表0.15,仍然得到#execute B？ …
我正在实现通用散列并使用以下通用散列函数:
h(k)=((A*k)mod 2 ^ 64)rsh 64-r
其中A是一个随机数
2 ^ 61和2 ^ 62.
C++中的rand()函数有返回类型整数,它不能生成那么大的数字.那么如何在这个范围内生成随机数？(数字应该是非常随机的,即每个数字应该具有相同的概率被选中)
注意:
long long int random=rand();
不起作用返回的数字rand是int.
有人告诉我,Hashtable在.NET使用中重复以减少/避免碰撞.
IE浏览器."Rehasing的工作原理如下:假设我们有一组散列不同的函数,H1 ... Hn,并且当从散列表中插入或检索项目时,最初使用H1散列函数.如果这导致碰撞,则尝试使用H2,然后再尝试Hn,以避免在Hashtable中发生碰撞."
假设:我们有一个哈希表,其中n(其中n <Infinity)元素的渐近时间复杂度为o(1); 我们(CLR)在应用一些散列函数(Hn-1散列函数,其中n> 1)时实现了这一点.
问题:当我们寻找(检索)任何元素时(如果使用了不同的散列函数),有人可以解释一下CLR map如何键入哈希码？CLR如何跟踪(如果是)任何活动对象(哈希表)的哈希函数？
提前致谢
我有可以便宜地转换为 a 的输入键uint64_t（即输入包含小于或等于 64 位）。
每个唯一的键（尚未在映射中）将被分配一些数据（指向对象的指针）。很像std::map<uint64_t, Object*>这样。
插入新密钥对时间并不重要，因为总共只有少量密钥，并且永远不会再次删除它们。其中小是指小于 100。
典型的实现将使用 a std::vector（因为元素数量较少）并且仅扫描所有元素，或使用二分搜索（即boost::flat_map）；但这对我来说还不够理想。一旦插入所有元素，映射就是静态的，并且应该可以在短短几个时钟周期内找到属于给定键的指针。
我想到的是每次插入新键时确定一个完美的哈希，然后使用这个哈希（函数）来找回指针。
这需要两件事：
一种寻找廉价哈希函数的算法，该函数将给定 64 位值的小列表转换为 8、9、10（或需要多少）位且不会发生冲突（又名完美哈希函数），以便后者可以直接在查找表中使用（即大小为 256、512、1024...）。
动态创建此类哈希函数的方法；我不得不承认我不愿意运行外部编译器并动态加载新的哈希函数;-)。
我目前的理解Universal Hashing是一种在运行时随机选择散列函数的方法,以保证任何类型输入的合理性能.
我知道我们可能会这样做是为了防止有人故意选择恶意输入的操纵(知道确定性散列函数的可能性).
我的问题如下:是不是真的,我们仍需要保证每次哈希时都将一个密钥映射到同一个地址？例如,如果我们想要检索信息,但随机选择哈希函数,我们如何保证我们可以回到我们的数据？