のどの形式を使用しても、完全に時間の無駄になると思いますHashMap。さまざまなデータのマルチバイト ハッシュを計算していると思いますが、これらは既にhashes であり、これ以上ハッシュを実行する必要はありません。
あなたはそれを述べていませんが、あなたのハッシュはbyteシーケンスであると推測しています。明らかに、これらを保管するには、トライまたはドーグのいずれかが理想的です。
したがって、 a を実装し、trie/dawgそれを使用してすべてのハッシュを最初の配列に格納することをお勧めします。次に、すべての計算能力を並行して使用して、 this の 2 番目の配列の各要素を検索できます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" ) );
}
}