Función hash asociativa no conmutativa

Question

¿Hay una función hash con las siguientes propiedades?

• es asociativa
• no es conmutativa
• fácilmente implementable en 32 bits enteros: int32 hash(int32, int32)

Si estoy en lo correcto tal función, permite lograr objetivos siguientes

• cálculo de hash de cadena concatenada de hashes de subcadenas
de hash
• calcular simultáneamente
• cálculo de hash de la lista implementado en árbol binario - incluyendo el orden, pero excluyendo la forma de árbol está equilibrado

El mejor que he encontrado hasta ahora es la multiplicación de la matriz 4x4 de bits, pero eso es difícil de implementar y reduce el espacio a 16bits.

Estoy agradecido por cualquier ayuda.

Answer 1

Esto es lo que se me ocurrió (escrito en Java). La idea básica es dividir 32bit-int en 2 números. Sumas de bits más antiguas, incluido el efecto de multiplicación. Bits más jóvenes siguen ese efecto de multiplicación. Funciona. Tiene buena distribución, también contra argumentos comunes como (0, 1), (1, 0).

public class AssociativelyMergedIntegers { 
    /** biggest unsigned 16-bit prime */ 
    private static final int PRIME = 65521; 

    /** associative, not commutative hash function */ 
    public static int merged(int first, int second) { 
    int firstFactor = remainderOf(first & 0x0000FFFF); 
    int secondFactor = remainderOf(second & 0x0000FFFF); 
    int firstSum = remainderOf(first >>> 16 & 0x0000FFFF); 
    int secondSum = remainderOf(second >>> 16 & 0x0000FFFF); 
    int resultSum = remainderOf(firstSum + (long) firstFactor * secondSum); 
    int resultFactor = remainderOf((long) firstFactor * secondFactor); 
    return resultSum << 16^resultFactor; 
    } 

    private static int remainderOf(long number) { 
    int rest = (int) (number % PRIME); 
    return rest == 0 
     ? PRIME - 2 
     : rest; 
    } 
}