如何同时找到两个数组中相同的byte [] - 对象？

Question

我正在尝试对哈希实施碰撞攻击(我正在访问课程'加密').因此,我有两个哈希数组(=字节序列byte[]),并希望找到两个数组中都存在的哈希值.经过一些研究和大量思考后,我确信单核机器上的最佳解决方案是HashSet(添加第一个数组的所有元素,并检查contains第二个数组的元素是否已经存在).

但是,我想实现并发解决方案,因为我可以访问具有8个内核和12 GB RAM的计算机.我能想到的最好的解决方案是ConcurrentHashSet,可以通过它创建Collections.newSetFromMap(new ConcurrentHashMap<A,B>()).使用这个数据结构,我可以并行地添加第一个数组的所有元素,并且 - 在添加了所有元素之后 - 我可以同时检查via contains以获得相同的哈希值.

所以我的问题是:你知道为这个确切问题设计的算法吗？如果没有,您是否有使用此类ConcurrentHashSet有关问题和有效运行时复杂性的经验？或者你能推荐另一个可以帮助我的预建数据结构吗？

PS:如果有人对细节感兴趣:我打算使用Skandium来并行化我的程序.

Answer 1

我认为使用任何形式的完全浪费时间HashMap.我猜你正在计算各种数据的多字节哈希值,这些已经是hashes,没有必要对它们执行任何更多哈希.

虽然你没有陈述,但我猜你的哈希是byte序列.显然,trie或dawg都是理想的存储方式.

因此我建议你实现一个trie/dawg并使用它来存储第一个数组中的所有哈希值.然后,您可以并行使用所有计算能力来查找第二个阵列中的每个元素trie.不需要锁.

添加

这是一个简单的Dawg实现,我敲了一起.它似乎工作.

public class Dawg {
  // All my children.
  Dawg[] children = new Dawg[256];
  // Am I a leaf.
  boolean isLeaf = false;

  // Add a new word.
  public void add ( byte[] word ) {
    // Finds its location, growing as necessary.
    Dawg loc = find ( word, 0, true );
    loc.isLeaf = true;
  }

  // String form.
  public void add ( String word ) {
    add(word.getBytes());
  }

  // Returns true if word is in the dawg.
  public boolean contains ( byte [] word ) {
    // Finds its location, no growing allowed.
    Dawg d = find ( word, 0, false );
    return d != null && d.isLeaf; 
  }

  // String form.
  public boolean contains ( String word ) {
    return contains(word.getBytes());
  }

  // Find the Dawg - growing the tree as necessary if requested.
  private Dawg find ( byte [] word, int i, boolean grow ) {
    Dawg child = children[word[i]];
    if ( child == null ) {
      // Not present!
      if ( grow ) {
        // Grow the tree.
        child = new Dawg();
        children[word[i]] = child;
      }
    }
    // Found it?
    if ( child != null ) {
      // More to find?
      if ( i < word.length - 1 ) {
        child = child.find(word, i+1, grow);
      }
    }
    return child;
  }

  public static void main ( String[] args ) {
    Dawg d = new Dawg();
    d.add("H");
    d.add("Hello");
    d.add("World");
    d.add("Hell");
    System.out.println("Hello is "+(d.contains("Hello")?"in":"out"));
    System.out.println("World is "+(d.contains("World")?"in":"out"));
    System.out.println("Hell is "+(d.contains("Hell")?"in":"out"));
    System.out.println("Hal is "+(d.contains("Hal")?"in":"out"));
    System.out.println("Hel is "+(d.contains("Hel")?"in":"out"));
    System.out.println("H is "+(d.contains("H")?"in":"out"));
  }
}

添加

这可能是并发无锁版本的良好开端.众所周知这些东西很难测试,所以我不能保证这会起作用,但在我看来它肯定应该.

import java.util.concurrent.atomic.AtomicReferenceArray;


public class LFDawg {
  // All my children.
  AtomicReferenceArray<LFDawg> children = new AtomicReferenceArray<LFDawg> ( 256 );
  // Am I a leaf.
  boolean isLeaf = false;

  // Add a new word.
  public void add ( byte[] word ) {
    // Finds its location, growing as necessary.
    LFDawg loc = find( word, 0, true );
    loc.isLeaf = true;
  }

  // String form.
  public void add ( String word ) {
    add( word.getBytes() );
  }

  // Returns true if word is in the dawg.
  public boolean contains ( byte[] word ) {
    // Finds its location, no growing allowed.
    LFDawg d = find( word, 0, false );
    return d != null && d.isLeaf;
  }

  // String form.
  public boolean contains ( String word ) {
    return contains( word.getBytes() );
  }

  // Find the Dawg - growing the tree as necessary if requested.
  private LFDawg find ( byte[] word, int i, boolean grow ) {
    LFDawg child = children.get( word[i] );
    if ( child == null ) {
      // Not present!
      if ( grow ) {
        // Grow the tree.
        child = new LFDawg();
        if ( !children.compareAndSet( word[i], null, child ) ) {
          // Someone else got there before me. Get the one they set.
          child = children.get( word[i] );
        }
      }
    }
    // Found it?
    if ( child != null ) {
      // More to find?
      if ( i < word.length - 1 ) {
        child = child.find( word, i + 1, grow );
      }
    }
    return child;
  }

  public static void main ( String[] args ) {
    LFDawg d = new LFDawg();
    d.add( "H" );
    d.add( "Hello" );
    d.add( "World" );
    d.add( "Hell" );
    System.out.println( "Hello is " + ( d.contains( "Hello" ) ? "in" : "out" ) );
    System.out.println( "World is " + ( d.contains( "World" ) ? "in" : "out" ) );
    System.out.println( "Hell is " + ( d.contains( "Hell" ) ? "in" : "out" ) );
    System.out.println( "Hal is " + ( d.contains( "Hal" ) ? "in" : "out" ) );
    System.out.println( "Hel is " + ( d.contains( "Hel" ) ? "in" : "out" ) );
    System.out.println( "H is " + ( d.contains( "H" ) ? "in" : "out" ) );
  }
}