¿Matriz de cadenas como tecla de función hash?

Question

¿Es posible, en cualquier idioma (no importa), tener una función hash que utiliza una matriz de cadenas como claves?

quiero decir algo como esto:

hash(["word1", "word2", ...]) = "element" 

en lugar de la clásica:

hash("word") = "element" 

necesito algo por el estilo, ya que cada palabra de lo que le gustaría usar como clave podría cambiar la salida elemento de la función. Tengo una secuencia de palabras y quiero un resultado específico para esa secuencia (también el orden puede cambiar el resultado).

Answer 1

Sure. Cualquier estructura de datos puede ser hash. Solo necesita obtener una definición estricta de igualdad y luego asegurarse de que hash (A) == hash (B) si A == B. Suponga que su definición es que [s1, s2, ..., sm] == [t1, t2, ..., tn] si y solo si m == ny si == ti para i = 1..m y cadena adicional s == t si y solo si | s | == | t | y s [i] == t [i] para 0 < = i < | s |. Puede construir un hash de muchas maneras:

• Concatenar todas las cadenas en la lista y calcular el resultado con cualquier función de cadena de hash.
• Haz lo mismo, agregando separadores como comas (,)
• Hash cada cadena individualmente y xor los resultados.
• Hash eash cadena individualmente, cambie el valor hash anterior y xor el nuevo valor en el hash.
• Infinitamente muchas más posibilidades ...

definición Tigorous de la igualdad es importante. Si, por ejemplo, el orden no tiene importancia en las listas o la comparación de cadenas no distingue entre mayúsculas y minúsculas, la función hash aún debe diseñarse para garantizar hash (A) == hash (B) si A == B. Hacer esto mal hará que las búsquedas fallen.

Java es un lenguaje que le permite definir una función hash para cualquier tipo de datos. Y, de hecho, una lista de cadenas de bibliotecas funcionará muy bien como una clave que usa la función de hash predeterminada.

HashMap<ArrayList<String>, String> map = new HashMap<ArrayList<String>, String>(); 

ArrayList<String> key = new ArrayList<String>(); 
key.add("Hello"); 
key.add("World"); 

map.put(key, "It's me."); 
// map now contains mapping ["Hello", "World"] -> "It's me." 

Answer 2

Sí, es posible, pero en la mayoría de los casos tendrá que definir su propia función hash que traduce una matriz en una clave hash. Por ejemplo, en java, array.hashCode() se basa en la función Object.hashCode() que se basa en la propia referencia y no en los contenidos del objeto.

También puede consultar Arrays.deepHashCode() function in java si está interesado en una implementación de una función de hashing creada sobre una matriz.