Creo que sería una completa pérdida de tiempo utilizar cualquier forma de HashMap. Supongo que estás calculando hashes de múltiples bytes de varios datos, estos ya son hash es, no hay necesidad de realizar más hashing en ellos.
Aunque no lo diga, supongo que sus hashes son byte secuencias. Claramente, un trie o un dawg sería ideal para almacenarlos.
Sugiero que implemente un trie/dawg y lo use para almacenar todos los valores hash en la primera matriz. A continuación, puede utilizar toda su potencia de cálculo en paralelo para buscar cada elemento en su segunda matriz en este trie. No se requieren cerraduras.
Agregado
He aquí una sencilla aplicación Dawg Toqué juntos. Parece funcionar.
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"));
}
}
Agregado
Esto podría ser un buen comienzo en una versión concurrente sin bloqueo. Estas cosas son notoriamente difíciles de probar, así que no puedo garantizar que esto funcione, pero en mi opinión, sin duda debería hacerlo.
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"));
}
}
¿Los arreglos ya están ordenados? Si es así, una función de fusión de un solo paso encontrará duplicados. De lo contrario, podría ordenar array1 y array2 en paralelo y fusionar los resultados. – Ingo
Por hash de bytes ¿quiere decir que todos los hash están en el intervalo 0-255? – Tudor
Quise decir byte-secuencias, es decir 'byte []'. Son el resultado de una función hash como SHA o MD5. No, las matrices no están ordenadas. Ordenarlas y fusionarlas necesitaría O (n log n) para la clasificación y O (n + m) para la fusión. Esperaba una mayor eficiencia. –