¿Maneras de hash un vector numérico?

Question

¿Existen algoritmos hash conocidos que ingresan un vector de int y producen un int único que funciona de manera similar a un producto interno?

En otras palabras, estoy pensando en un algoritmo de hash que podría tener este aspecto en C++:

// For simplicity, I'm not worrying about overflow, and assuming |v| < 7. 
int HashVector(const vector<int>& v) { 
    const int N = kSomethingBig; 
    const int w[] = {234, 739, 934, 23, 828, 194}; // Carefully chosen constants. 
    int result = 0; 
    for (int i = 0; i < v.size(); ++i) result = (result + w[i] * v[i]) % N; 
    return result; 
} 

estoy interesado en esto porque estoy escribiendo un papel en un algoritmo que se beneficiarían de cualquier trabajo previo en hashes similares. En particular, sería genial si se conoce algo sobre las propiedades de colisión de un algoritmo hash como este.

El algoritmo en el que estoy interesado consistiría en hash vectores enteros, pero algo para los vectores float también sería genial.

Aclaración

El hash es para uso en una tabla hash para las búsquedas de clave/valor rápidas. No hay preocupación de seguridad aquí.

La respuesta deseada es algo así como un conjunto de constantes que probablemente funcionan especialmente bien para un hash como este, análogo a un multiplicador y módulo que funciona mejor que otros como un generador de números pseudoaleatorio.

Por ejemplo, algunas elecciones de constantes para un generador pseudoaleatorio congruente lineal son conocidas por proporcionar longitudes de ciclo óptimas y tener módulos fáciles de calcular. Tal vez alguien ha hecho una investigación para mostrar que un cierto conjunto de constantes multiplicativas, junto con una constante de módulo, en un hash vectorial puede reducir la posibilidad de colisiones entre los vectores enteros cercanos.

Answer 1

Hice algunos experimentos (inéditos, prácticos) con la prueba de una variedad de algoritmos hash de cadena. (Resulta que función hash por defecto de Java para cuerdas chupa.)

El experimento fácil es para discutir el diccionario Inglés y compara el número de colisiones que tiene en el algoritmo A vs algoritmo B.

Puede construir un similares experimento: genera al azar $ BIG_NUMBER de posibles vectores de longitud 7 o menos. Hash ellos en el algoritmo A, hash ellos en el algoritmo B, luego comparar el número y la gravedad de las colisiones.

Después de que sea capaz de hacer eso, puede utilizar el recocido simulado o técnicas similares para encontrar "números mágicos" que funcionan bien para usted. En mi trabajo, para vocabularios dados de interés y un tamaño hash estrictamente limitado, pudimos hacer que un algoritmo genérico funcionara bien para varios idiomas humanos al variar los "números mágicos".

Answer 2

Dependiendo del tamaño de las constantes, tendría que decir que el grado de caos en el vector de entrada tendrá un impacto en el resultado. Sin embargo, un análisis cualitativo rápido de su puesto sugeriría que usted tiene un buen comienzo:

• Sus entradas se multiplican, aumentando así el grado de separación entre los valores de entrada similares por iteración (por ejemplo, 65 + 66 es mucho más pequeño que 65 * 66), lo cual es bueno.
• Es determinista, a menos que su vector se deba considerar un conjunto y no una secuencia. Para mayor claridad, ¿debería v = {23, 30, 37} ser diferente de v = {30, 23, 37}?
• La uniformidad de la distribución se variará en función del rango y el caos de los valores de entrada en v. Sin embargo, eso también es cierto para un algoritmo de hash entero generalizado.

Por curiosidad, ¿por qué no simplemente usar un algoritmo hash para enteros y realizar algunos cálculos matemáticos interesantes sobre los resultados?

Answer 3

Mientras que yo podría ser mal entendido por completo, tal vez sea una buena idea para tratar un vector como un flujo de bytes y hacer un poco de hash conocimientos sobre el mismo, es decir SHA1 o MD5.

Solo para aclarar, se sabe que esos hashes tienen buenas propiedades de hash, y creo que no hay ninguna razón para reinventar una bicicleta e implementar un nuevo hash. Otra posibilidad es usar el angoritmo de CRC conocido.

Answer 4

Python utiliza para cifrar tuplas de esta manera (source):

class tuple: 
    def __hash__(self): 
     value = 0x345678 
     for item in self: 
      value = c_mul(1000003, value)^hash(item) 
     value = value^len(self) 
     if value == -1: 
      value = -2 
     return value 

En su caso, item sería siempre un número entero, que utiliza este algoritmo:

class int: 
    def __hash__(self): 
     value = self 
     if value == -1: 
      value == -2 
     return value 

Esto tiene nada para hacer con un producto interno, sin embargo ... así que tal vez no sea de mucha ayuda.