标签: hash-collision

我目前使用线性探测器的实现是使用线性探测,现在我想转向二次探测(以后再进行链接,也可能是双重哈希).我已经阅读了一些文章,教程,维基百科等...但我仍然不知道我应该做什么.

基本上,线性探测的步长为1,这很容易做到.当从哈希表中搜索,插入或删除元素时,我需要计算哈希值,为此我执行此操作:

index = hash_function(key) % table_size;

然后,在搜索,插入或删除I循环通过表时,直到找到一个空闲桶,如下所示:

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + 1) % table_size;
    }
while(/* LOOP UNTIL IT'S NECESSARY */);

对于二次探测,我认为我需要做的是改变计算"索引"步长的方式,但这是我不明白应该怎么做的.我见过各种代码,而且所有代码都有所不同.

此外,我已经看到了一些Quadratic Probing的实现,其中哈希函数被改变为适应(但不是全部).是真的需要改变还是我可以避免修改散列函数并仍然使用二次探测？

编辑: 在阅读了以下Eli Bendersky指出的所有内容后,我想我得到了一般的想法.以下是http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx中代码的一部分:

15   for ( step = 1; table->table[h] != EMPTY; step++ ) {
16     if ( compare ( key, table->table[h] ) == 0 )
17       return 1;
18 
19     /* Move forward …

我有一个 md5 函数，我已经确认它适用于文件和字符串。但是当我在非常大的文件的可变大小块上使用它时，它会生成相同的 md5 值，但块的大小不同。

我想知道是否有可能具有不同长度但可能具有相同内容的两个块导致相似的 md5 指纹。

我正在研究将CRC校验和用作哈希时的冲突可能性。我知道如何计算均匀分布的哈希算法的冲突可能性（这意味着获得随机输入数据的所有可能校验和的机会是相同的）。

我不知道的东西（我在网络上找不到）：

1. CRC校验和是否一般[不]均匀分布？
2. 分布是否取决于多项式？
3. 分布是否取决于输入数据大小？

PS：我知道将CRC用作哈希时的限制，因此这不是此问题的一部分。

我正在尝试在 go 中实现一个哈希程序，我使用线性探测进行了插入和解决冲突。当我尝试取回值时，我得到了不同的值，因为我使用线性探测来修复冲突。

这是我的程序：https : //play.golang.org/p/7Pmqu6A313

我目前正在开发一个需要缓存不同资源的应用程序。不同类型的资源都有处理程序，这些处理程序将知道哪些数据与确定相关，是否必须重建资源或者是否可以从缓存中获取它。为此，处理程序应生成所有相关数据的哈希值以进行缓存。根据上下文，数据可以是基元（int、float...）、字符串、切片、结构体和映射。所以几乎一切。用于散列的对象数量也可能有所不同。

为了计算处理程序中的哈希值，我创建了一个具有类型 的可变参数的哈希函数interface{}。

我目前的做法是这样的：

func Hash(objs ...interface{})([]byte) {
    // Use MD5 because it's fast and is reasonably enough protected against accidental collisions.
    // There is no scenario here where intentional created collisions could do harm.
    digester := crypto.MD5.New()

    encoder := gob.NewEncoder(digester)
    encoder.Encode(objs) // In real life one would handle that error

    return digester.Sum(make([]byte, 0))
}

这有效。但这个实现有一些让我头疼的事情。因为我不确定gob 是否总是表现出确定性，对于当前版本似乎是这种情况，但正如引用的答案指出的那样，版本之间可能会有变化。根据 gob 的文档，传输结构时将省略默认值（0 表示整数、空字符串、nil...）。此外，所有 int 值都将作为通用数字传输。所以unit64和int将是相同的。对于我的用例，我想不出这有什么实际问题，但这听起来像是麻烦的根源。

现在，如果我从头开始编写该函数，我会适当地谨慎行事，用反射遍历该结构并创建一个哈希树。但我不想那样做。

我很确定我不是第一个满足这些要求的人，但我无法在网络上找到任何经过良好测试的 go 代码来解决这个问题。

附录

另请参阅：https://crypto.stackexchange.com/questions/10058/how-to-hash-a-list-of-multiple-items

这并不像看起来那么微不足道。正如 Adrian 指出的那样，简单地连接数据是行不通的，因为这样Hash("12", "3")和Hash("123") …

我定义了一个名为的类，该类Point将用作unordered_map. 所以，我operator==在类中提供了一个函数，我还提供了一个template specializationfor std::hash。根据我的研究，这是我认为必要的两件事。相关代码如图：

class Point
{
    int x_cord = {0};
    int y_cord = {0};
public:
    Point()
    {

    }
    Point(int x, int y):x_cord{x}, y_cord{y}
    {

    }
    int x() const
    {
        return x_cord;
    }
    int y() const
    {
        return y_cord;
    }
    bool operator==(const Point& pt) const
    {
        return (x_cord == pt.x() && y_cord == pt.y());
    }
};

namespace std
{
    template<>
    class hash<Point>
    {
    public:
        size_t operator()(const Point& pt) const
        {
            return …

我正在使用使用单独链接作为冲突解决技术的哈希表。

我确实知道一般公式是 N/table_length，其中 N 是表中当前项目的数量。

我对分母有点困惑。它是数组的大小+链式元素的数量，还是只是数组的大小？

使用我的webapp，我将使用散列生成的文件名将缓存的文件存储在各个子目录中，以优化性能水平。我知道可以提高性能的一种方法是，确保生成的名称遵循8.3文件名结构，这样NTFS不必生成短文件名（我将无法在注册表中进行设置）。

为了做到这一点，尽管我必须将哈希（我在想SHA1）修剪为8个字符，但是显然这将大大增加冲突的可能性。我想知道碰撞的可能性是多少？

我在这里看到了完整的SHA1哈希冲突率的答案，但是我的数学很糟糕，因此计算值远远超出了我的范围。

让我们考虑一下HashMap,它使用单独的链接来解决哈希码冲突.

如果我有多个条目,其中hascode是相同的,则冲突机制形成所有这些条目的链表链.

现在,让我们考虑一个案例,其中这样的链表存在:

(K1,V1,->) (K2,V2, ->) (K7,V7,->) (K9,V9,)

现在有一个新条目进入,哈希码的格式相同,键的值与K7相同.它会覆盖K7的现有价值吗？

我刚刚了解到:

• .NET中的字典作为Hash表实现,来自此答案以及关于Dictionary<TKey,?TValue>Class的链接MSDN文章.
• 字符串散列函数GetHashCode()不为每个唯一字符串值提供唯一的散列码值.根据有关字符串类的相应MSDN文章,不同的字符串可以返回相同的哈希码.

这让我想到,.NET中的字典(至少在使用字符串作为键时)容易受到键冲突的影响.

这种钥匙碰撞会发生什么？是否存在任何已知的唯一字符串值,实际发生碰撞？字典是否会在这些关键值上被打破？

另外:

• 这取决于代码是在32位还是64位系统上运行？
• 使用短字符串到特定长度是否安全？更安全吗？

注意:我不是指特定的.NET CLR,但如果重要,那么让我们来谈谈桌面的4.5.2 32位版本.

关于重复的说明:

• 实际上,我并不是在询问碰撞本身,而是关于它们在功能/正确性方面的含义.
• 2个不同的字符串可以在C#中使用相同的哈希码吗？解决了字符串具有非唯一哈希的事实,我已经知道并且没有问过.对于hashCode用于什么,情况也是如此？它有独特之处吗？
• 我删除了关于密钥冲突的可能性的部分,因此在字符串上调用GetHashCode()时获取重复值的概率应该不再重复.
• 在Dictionary键中发生哈希冲突会发生什么？帮助了我,所以我认为这个问题是重复的.

我正在查看HashMap的源代码，但是二进制运算符使很多人感到困惑。

我确实了解以下的一般目的，公平分配并将hashCode限制在存储桶限制之内。

有人可以在这里解释评论吗？立即进行操作有什么好处？

/**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * …

如果我有一些数据，我会像这样使用 SHA256 进行哈希处理：- hash=SHA256(data)

然后只复制哈希的前 8 个字节而不是整个 32 个字节，找到不同数据的哈希冲突有多容易？是 2^64 还是 2^32 ？

如果我需要将某些数据的哈希减少到较小的大小（n 位），有什么方法可以确保搜索空间 2^n ？

我有一个Dictionary自定义散列函数。我想测试散列函数，因为即使它为我的测试值返回不同的散列结果，由于模%运算，其中一些可能仍然映射到同一个存储桶。

这是一个微调hash函数的开发测试，不会投入生产，所以不用担心其他版本内部实现的变化！！！

在 C++ 中，可以获取地图的桶大小来检查碰撞状态，但我找不到在 C# 中执行此操作的方法。我怎么知道是否Dictionary发生了碰撞？