algorithm - perdón - Formas de hash un vector numérico?

ha*ash perdón, perdón

Question

¿Hay algún algoritmo hash conocido que ingrese un vector de int y genere un int único que funcione de manera similar a un producto interno?

En otras palabras, estoy pensando en un algoritmo hash que podría verse así 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 artículo sobre un algoritmo que se beneficiaría 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 sería hash vectores enteros, pero algo para vectores flotantes también sería genial.

Aclaración

El hash está destinado a ser utilizado en una tabla hash para búsquedas rápidas de clave / valor. No hay preocupación de seguridad aquí.

La respuesta deseada es algo así como un conjunto de constantes que probablemente funcionan particularmente 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, se sabe que algunas elecciones de constantes para un generador pseudoaleatorio congruente lineal dan longitudes de ciclo óptimas y tienen 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

Aunque podría malinterpretarlo por completo, tal vez sea una buena idea tratar un vector como un flujo de bytes y hacer algo de hash, es decir, SHA1 o MD5 .

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

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 publicación sugiere que tenga un buen comienzo:

• Sus entradas se multiplican, lo que aumenta el grado de separación entre valores de entrada similares por iteración (por ejemplo, 65 + 66 es mucho más pequeño que 65 * 66), lo que es bueno.
• Es determinista, a menos que su vector se considere 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 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 de entero generalizado.

Por curiosidad, ¿por qué no simplemente usar un algoritmo hash existente para enteros y realizar algunas matemáticas interesantes sobre los resultados?

Answer 3

Hice algunos experimentos (inéditos, prácticos) con la prueba de una variedad de algoritmos hash de cadena. (Resulta que la función hash predeterminada de Java para Strings es una mierda).

El experimento más sencillo es analizar el diccionario de inglés y comparar cuántas colisiones tiene en el algoritmo A frente al algoritmo B.

Puede construir un experimento similar: generar aleatoriamente $ 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 puedas hacer eso, puedes utilizar el recocido simulado o técnicas similares para encontrar "números mágicos" que te funcionen bien. 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 4

Python solía copiar tuplas de esta manera ( fuente ):

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, el item siempre será un entero, que utiliza este algoritmo:

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

Sin embargo, esto no tiene nada que ver con un producto interno ... así que tal vez no sea de mucha ayuda.