标签: hash-function

我在采访中遇到过需要对整数或字符串使用哈希函数的情况.在这种情况下我们应该选择哪一种？我在这些情况下错了,因为我最终选择了产生大量碰撞的那些,但是哈希函数往往是数学的,你不能在面试中回忆起它们.是否有任何一般性建议,以至于面试官对整数或字符串输入的方法感到满意？在"面试情境"中,哪些功能对于两个输入都是足够的

我正在阅读关于MD5哈希值的这个问题,接受的答案让我困惑.据我所知,cryptopgraphic哈希函数的一个主要属性是找到具有相同哈希值的两个不同消息(输入)是不可行的.

然而,为什么MD5哈希值不可逆的问题的共识答案呢？是由于输入字符串的无限数量将产生相同的输出. 这似乎与我完全矛盾.

另外,令我困惑的是,算法是公开的,但哈希值仍然是不可逆的.这是因为散列函数中总是存在数据丢失,因此无法分辨哪些数据被丢弃了吗？

当输入数据大小小于固定输出数据大小时(例如,散列密码"abc")会发生什么？

编辑:

好的,让我看看我是否有这个:

1. 实际上,很难从哈希中推断出输入,因为有无限量的输入字符串会产生相同的输出(不可逆属性).
2. 然而,找到生成相同输出的多个输入字符串的单个实例也非常非常困难(抗冲突属性).

我正在为我的对象编写一个哈希函数.由于所有STL容器的Generic Hash功能,我已经可以散列容器并组合散列.但我的课程也有枚举.当然我可以为每个枚举创建一个哈希函数,但这似乎不是一个好主意.是否可以为其创建一些通用规范std::hash,以便它可以应用于每个枚举？类似的东西,使用std::enable_if和std::is_enum

namespace std {
  template <class E>
  class hash<typename std::enable_if<std::is_enum<E>::value, E>::type> {
  public:
    size_t operator()( const E& e ) const {
      return std::hash<std::underlying_type<E>::type>()( e );
    }
  };
};

PS.此代码无法编译

error: template parameters not used in partial specialization:
error:         ‘E’

我无法适应待处理的C++ 1Z提案N3980通过@HowardHinnant一起工作制表散列.

从头开始计算制表散列的工作方式与N3980中描述的散列算法(Spooky,Murmur等)相同.它并不复杂:只需通过hash_append()序列化任何用户定义类型的对象,并让哈希函数在您进行时将指针更新为随机数表.

当试图实现制表散列的一个很好的属性时,麻烦就开始了:如果一个对象发生变异,计算散列的增量更新非常便宜.对于"手工制作"制表哈希,只需重新计算对象受影响字节的哈希值.

我的问题是:如何uhash<MyTabulationAlgorithm>在保持N3980的中心主题(类型不知道#)的同时,将功能对象的增量更新通信？

为了说明设计上的困难:假设我有一个用户定义的类型X,其中包含各种类型的N个数据成员xi

struct X 
{
   T1 x1;
   ...
   TN xN;
};

现在创建一个对象并计算其哈希值

X x { ... }; // initialize
std::size_t h = uhash<MyTabulationAlgorithm>(x);

更新单个成员,并重新计算哈希值

x.x2 = 42;
h ^= ...; // ?? I want to avoid calling uhash<>() again

我可以计算增量更新

h ^= hash_update(x.x2, start, stop); 

其中,[start, stop)表示与x2数据成员对应的随机数表的范围.但是,为了逐步(即便宜地!)更新任意突变的散列,每个数据成员都需要以某种方式知道其包含类的序列化字节流中的自己的子范围.这感觉不像是N3980的精神.例如,将新数据成员添加到包含类将更改类布局,从而更改序列化字节流中的偏移量.

应用程序:制表哈希是非常古老的,最近已经证明它具有非常好的数学属性(参见维基百科链接).它在棋盘游戏编程社区(计算机象棋,例如)中也很受欢迎,它以Zobrist哈希的名义命名.在那里,董事会职位扮演X的角色,并且移动一个小更新的角色(例如,将一个部分从其源移动到其目的地).如果N3980不仅可以适应这种制表散列,那还不错,但它也可以适应廉价的增量更新.

我正在尝试在Scala中实现Count-Min Sketch算法,因此我需要生成k个成对独立的散列函数.

这是我之前编程的任何一个低级别,除了Algorithms类之外我对哈希函数知之甚少,所以我的问题是:如何生成这些k成对独立哈希函数？

我应该使用像MD5或MurmurHash这样的哈希函数吗？我只生成表单的k哈希函数f(x) = ax + b (mod p),其中p是素数,a和b是随机整数？(即,每个人都在算法101中学习的通用散列家族)

我看起来更简单而不是原始速度(例如,如果它更容易实现,我将采取5倍的速度).

我正在读一本关于HashMap 哈希函数的Rust书,我无法理解这两句话.

默认情况下,HashMap使用加密安全散列函数,可以抵御拒绝服务(DoS)攻击.这不是最快的哈希算法,但是随着性能下降而带来更好的安全性的权衡是值得的.

我知道什么是加密安全哈希函数,但我不理解它背后的基本原理.根据我的理解,一个好的哈希函数HashMap应该只有三个属性:

• 确定性的(同一个对象具有相同的哈希值)
• 非常快
• 在散列值中具有均匀的位分布(意味着它将减少冲突)

在加密安全散列函数中,其他属性与散列表的99%(甚至99.99%)时间并不相关.

所以我的问题是:"对DoS攻击和更好的安全性的抵抗"甚至意味着在HashMap的背景下？

我正在尝试实现SHA-2加密而不是SHA-1.

为此,我知道这两个哈希算法之间的位数不同,这让我很困惑.

如何实现这一目标以及我需要在哪些部分进行必要的更改？

我可以使用Java,Python和任何其他主要编程语言的任何开源库.

如何在一个类中存储类的对象unordered_set？我的程序需要经常检查对象是否存在,如果存在unordered_set,则对该对象进行一些更新.

我已经在线查看了如何使用unordered_set,但遗憾的是大多数教程都是关于使用它int或string类型.但是我如何在课堂上使用它呢？我怎样才能定义一个哈希函数来使node_id下面的例子成为关键的unordered_set？

#include <iostream>
#include <unordered_set>

using namespace std;

// How can I define a hash function that makes 'node' use 'node_id' as key?    
struct node
{
    string node_id;
    double value;
    node(string id, double val) : node_id(id), value(val) {}
};

int main()
{
    unordered_set<node> set;
    set.insert(node("1001", 100));
    if(set.find("1001") != set.end()) cout << "1001 found" << endl;
}

我最近碰巧想到了 JavaScript 中的对象属性访问时间，并遇到了这个问题，它似乎合理地表明它应该是常数时间。这也让我想知道对象属性键长度是否有限制。显然现代浏览器支持长达 2^30 的密钥长度，这对于哈希函数来说似乎相当不错。那说，

• 有人知道JS引擎使用的哈希函数类型吗？

• 是否可以通过实验创建 JavaScript 属性访问器的冲突？

我将消息序列存储在数据库中,每个序列可以包含多达N消息.我想创建一个散列函数,它将表示消息序列,并且如果消息序列存在,则能够更快地检查.

每条消息都有一个区分大小写的字母数字通用唯一ID(UUID).考虑(M1, M2, M3)使用ids 跟踪消息 -

M1 - a3RA0000000e0taBB M2 - a3RA00033000e0taC M3 - a3RA0787600e0taBB

消息序列可以是

Sequence-1 : (M1,M2,M3) Sequence-2 : (M1,M3,M2) Sequence-3 : (M2,M1,M3) Sequence-4 : (M1,M2) Sequence-5 : (M2,M3) ...等等...

以下是用于存储消息序列的数据库结构示例

给定消息序列,我们需要检查数据库中是否存在该消息序列.例如,检查数据库中是否存在消息序列,M1 -> M2 -> M3即UID (a3RA0000000e0taBB -> a3RA00033000e0taC -> a3RA0787600e0taBB).

我想创建一个哈希函数来代替扫描表中的行,而哈希函数用哈希值表示消息序列.使用表中的哈希值查找应该更快.

我的简单哈希函数是 -

我想知道什么是最佳散列函数用于存储消息序列散列更快是存在检查.