logo标签列表

有意的哈希碰撞

mathhash
4
我正在尝试编写一些代码来实现“模糊哈希”。也就是说：我希望多个输入可以哈希到相同的输出，以便我可以快速轻松地进行搜索等操作。如果A哈希为1且C哈希为1，则我可以很容易地找出A等同于C。
设计这样的哈希函数似乎很困难，因此我想知道是否有人有使用CMPH或GPERF的经验，并能够指导我创建一个结果为此哈希函数的函数。
提前感谢！ Stefan
@Ben
在这种情况下，是布尔矩阵，但我可以很容易地将它们打包成64位整数。输入中的旋转、平移等都是无关紧要的，需要被淘汰。
000
111
000

等价于

111
000
000

并且

001
001
001

（简化）

@Kinopiko

目前我最好的办法是确定一种“规范”表示形式，并设计代码，当转换达到这种表示形式时终止代码（比如…将所有位都打包在底部）。但这样做速度很慢，我正在寻找更好的方法。我的数据集很大。

@Jason

这两个不会散列到相同的值。

000
010
000

000
011
000
如果您想在摘要上执行搜索，也许您应该寻找索引算法而不是哈希函数。您正在对哪种类型的数据进行哈希处理，并且典型的搜索是什么？ - Ben S
这取决于你的数据。你目前有什么？ - user181548
你是否正在寻找类似于布隆过滤器的东西？http://en.wikipedia.org/wiki/Bloom_filter - Hasturkun
5个回答
2
让我们以SOUNDEX作为您可能寻找的东西的例子...
  • 它可以使用哈希将不同但相似的键映射到相同的值
  • 它可以断言实体A（比如"麦当劳"）可能与实体C（"麦克唐纳"）相同
SOUNDEX的一个特点是它在特定领域（例如姓氏）中表现良好，并利用与单词发音相关的规则[在英语及其衍生语言中]。
您的哈希算法（或者说它几乎是一种索引？）只有在存在（或者可以发现）一个相对简单的规则集来表达所考虑的项目/记录的“相似性”时才能成功。例如，如果底层数据库涉及汽车，并且如果“相似性”的标准是大小和一般性能，则哈希算法可能应基于记录中的属性，如价格（转换为范围），气缸数，门数，以及可能的油耗估计（也转换为范围）。
简而言之，我希望上述内容说明了需要根据我们希望与哈希值身份相关联的语义来定制算法（或接近...因此看起来越来越像索引...），以及这些语义如何在可用数据中表示。
项目可能在许多维度上非常相似。关键是定义这些维度是什么，以及如何使用该维度上的属性作为哈希函数的键。
关于CMPH和gperf...这些是完美、可选最小的哈希函数实现。这种函数将允许您防止碰撞。不是这里需要的（我认为）。
1

cmph 实现的 chd 算法可以进行 k-完美哈希，我认为这正是您所需要的：

http://cmph.sourceforge.net/chd.html

不过，最好知道你所说的“大输入”具体是指什么。如果你指的是数十万条目，那么有更直接的解决方案。如果你有数亿条目，那么chd可能是最佳选择。

1
你可以查看MinHash，它是一种概率方法，适用于由集合成员定义项目的情况。
我知道你想设计自己的哈希函数，但也许这正是你要找的东西。
0

散列表在防止误判的时候有多少无冲突性？

尝试以下方法：

  1. 将数字排序，然后对该序列运行标准哈希算法？
  2. 或者，将每行/列视为集合，并使用加法处理每个内容，然后对这些结果进行排序并在排序后的总和上运行标准哈希？
  3. 或，将方法1和2乘起来。

例如，这是Java示例（快速而肮脏，但您会明白意思）：

import java.util.*;

/**
 *
 * @author Mark Bolusmjak
 */
public class MatrixTest {


  LinkedList<LinkedList<Integer>> randomMatrix(int size){
    LinkedList<LinkedList<Integer>> rows = new LinkedList<LinkedList<Integer>>();
    for (int i=0; i<size; i++){
      LinkedList<Integer> newRow = new LinkedList<Integer>();
      for (int j=0; j<size; j++){
        newRow.add((int)(5*Math.random()));
      }
      rows.add(newRow);
    }
    return rows;
  }

  LinkedList<LinkedList<Integer>> trans(LinkedList<LinkedList<Integer>> m){
    if (Math.random()<0.5){ //column translation
      for (LinkedList<Integer> integers : m) {
        integers.addFirst(integers.removeLast());
      }
    } else { //row translation
      m.addFirst(m.removeLast());
    }
    return m;
  }

  LinkedList<LinkedList<Integer>> flipDiagonal(LinkedList<LinkedList<Integer>> m){
    LinkedList<LinkedList<Integer>> flipped = new LinkedList<LinkedList<Integer>>();
    for (int i=0; i<m.size(); i++){
      flipped.add(new LinkedList<Integer>());
    }

    for (LinkedList<Integer> mRows : m) {
      Iterator<Integer> listIterator = mRows.iterator();
      for (LinkedList<Integer> flippedRows : flipped) {
        flippedRows.add(listIterator.next());
      }
    }
    return flipped;
  }


  public static void main(String[] args) {
    MatrixTest mt = new MatrixTest();
    LinkedList<LinkedList<Integer>> m = mt.randomMatrix(4);
    mt.display(m);

    System.out.println(mt.hash1(m));
    System.out.println(mt.hash2(m));

    m = mt.trans(m);
    mt.display(m);
    System.out.println(mt.hash1(m));
    System.out.println(mt.hash2(m));

    m = mt.flipDiagonal(m);
    mt.display(m);
    System.out.println(mt.hash1(m));
    System.out.println(mt.hash2(m));

    m = mt.trans(m);
    mt.display(m);
    System.out.println(mt.hash1(m));
    System.out.println(mt.hash2(m));

    m = mt.flipDiagonal(m);
    mt.display(m);
    System.out.println(mt.hash1(m));
    System.out.println(mt.hash2(m));

  }


  private void display(LinkedList<LinkedList<Integer>> m){
    for (LinkedList<Integer> integers : m) {
      System.out.println(integers);
    }
    System.out.println("");
  }

  int hash1(LinkedList<LinkedList<Integer>> m){
    ArrayList<Integer> sorted = new ArrayList<Integer>();

    for (LinkedList<Integer> integers : m) {
      for (Integer integer : integers) {
        sorted.add(integer);
      }
    }
    Collections.sort(sorted);
    return sorted.hashCode();
  }

  int hash2(LinkedList<LinkedList<Integer>> m){
    List<Integer> rowColumnHashes = new ArrayList<Integer>();
    for (LinkedList<Integer> row : m) {
      int hash = 0;
      for (Integer integer : row) {
        hash += integer;
      }
      rowColumnHashes.add(hash);
    }

    m = flipDiagonal(m);
    for (LinkedList<Integer> row : m) {
      int hash = 0;
      for (Integer integer : row) {
        hash += integer;
      }
      rowColumnHashes.add(hash);
    }

    Collections.sort(rowColumnHashes);
    return rowColumnHashes.hashCode();
  }



} // end of class
0
在你的示例矩阵中，旋转和平移等似乎涵盖了几乎所有内容，以至于你的算法会认为所有矩阵都是相等的。你能举一个不同的矩阵集合的例子吗？
此外，看起来你正在做类似于图像搜索的事情 - 用于识别可能缩放、旋转（可能是任意角度）、翻转等的相同图像的算法。我对这些东西不太了解，但也许你可以从那个研究领域寻找灵感。
另外，我记得向量微积分中有一些关于特征值的内容，你可能会觉得有用。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接