firmado con hash positivo casi perfecto

Question

Tengo un tipo entero, digamos long, cuyos valores están entre Long.MIN_VALUE = 0x80...0 (-2^63) y Long.MAX_VALUE = 0x7f...f (2^63 - 1). Quiero ajustarlo con ~ 50% de colisión a un entero positivo del mismo tipo (es decir, entre 1 y Long.MAX_VALUE) de una manera limpia y eficiente.

Mis primeros intentos fueron algo así como:

• Math.abs(x) + 1
• (x & Long.MAX_VALUE) + 1

pero esos y similares enfoques siempre tienen problemas con ciertos valores, es decir, cuando x es 0/Long.MIN_VALUE/Long.MAX_VALUE. Por supuesto, la solución ingenua es usar 2 declaraciones if, pero estoy buscando algo más limpio/más corto/más rápido. ¿Algunas ideas?

Nota: Supongamos que estoy trabajando en Java donde no hay una conversión implícita a booleano y se define la semántica de cambio.

Answer 1

Solo para asegurarte, tienes un largo y quieres ajustarlo a un int?

Se podría hacer ...

(int) x     // This results in a meaningless number, but it works 
(int) (x & 0xffffffffl) // This will give you just the low order bits 
(int) (x >> 32)   // This will give you just the high order bits 
((Long) x).hashcode() // This is the high and low order bits XORed together 

Si desea mantener mucho que podría hacer ...

x & 0x7fffffffffffffffl // This will just ignore the sign, Long.MIN_VALUE -> 0 
x & Long.MAX_VALUE  // Should be the same I think 

Si conseguir un 0 no es bueno ...

x & 0x7ffffffffffffffel + 1 // This has a 75% collision rate. 

Sólo de pensar en voz alta ...

((x & Long.MAX_VALUE) << 1) + 1 // I think this is also 75% 

creo que va a necesitar, ya sea estar bien con el 75% o un poco fea:

(x > 0) ? x : (x < 0) ? x & Long.MAX_VALUE : 7 

Answer 2

Suponiendo que desea contraer todos los valores en el espacio positivo, ¿por qué no poner a cero el signo ¿poco?

Puede hacer esto con una sola operación en modo bit, aprovechando que MAX_VALUE es solo un bit de signo cero seguido de otros, p.

int positive = value & Integer.MAX_VALUE; 

O de largos:

long positive = value & Long.MAX_VALUE; 

Si desea un hash "mejor" con cualidades pseudo-aleatorios, es probable que quieren PSS el valor medio de otra función hash primero. Mis hashes rápidos favoritos son la familia XORshift de George Marsaglia. Éstos tienen la agradable propiedad de que mapean perfectamente todo el espacio de números enteros/largos sobre sí mismos, por lo que aún obtendrás exactamente el 50% de colisiones después de poner a cero el bit de signo.

He aquí una aplicación XORshift rápida en Java:

public static final long xorShift64(long a) { 
    a ^= (a << 21); 
    a ^= (a >>> 35); 
    a ^= (a << 4); 
    return a; 
} 

public static final int xorShift32(int a) { 
    a ^= (a << 13); 
    a ^= (a >>> 17); 
    a ^= (a << 5); 
    return a; 
} 

Answer 3

El enfoque más simple es poner a cero el bit de signo y luego asignar cero a algún otro valor:

Long y = x & Long.MAX_VALUE; 
return (y == 0)? 42: y; 

Esto es simple, utiliza solamente un operador si/ternario, y da ~ 50% de tasa de colisión en promedio. Hay una desventaja: asigna 4 valores diferentes (0, 42, MIN_VALUE, MIN_VALUE + 42) a un valor (42). Entonces, para este valor tenemos un 75% de colisiones, mientras que para otros valores, exactamente un 50%.

Puede ser preferible para distribuir de manera más uniforme colisiones:

return (x == 0)? 42: (x == Long.MIN_VALUE) ? 142: x & Long.MAX_VALUE; 

Este código da 67% colisiones para 2 valores y 50% para otros valores. No puede distribuir las colisiones más uniformemente, pero es posible elegir estos 2 valores más colisionantes. La desventaja es que este código usa dos operadores ifs/ternary.

Es posible evitar 75% colisiones en un solo valor, mientras que utilizando sólo uno si/operador ternario:

Long y = x & Long.MAX_VALUE; 
return (y == 0)? 42 - (x >> 7): y; 

Este código da 67% colisiones para 2 valores y un 50% de colisiones para otros valores. Hay menos libertad para elegir estos valores que colisionan: 0 mapas a 42 (y puede elegir casi cualquier valor en su lugar); MIN_VALUE mapea a 42 - (MIN_VALUE >> 7) (y puede cambiar MIN_VALUE por cualquier valor del 1 al 63, solo asegúrese de que A - (MIN_VALUE >> B) no se desborde).

---

Es posible obtener el mismo resultado (67% colisiones para 2 valores y un 50% de colisiones para otros valores) sin operadores condicionales (pero con código más complicado):

Long y = x - 1 - ((x >> 63) << 1); 
Long z = y + 1 + (y >> 63); 
return z & Long.MAX_VALUE; 

Esto da 67% de colisiones para los valores '1' y 'MAX_VALUE'. Si es más conveniente obtener la mayoría de las colisiones para otros valores, simplemente aplique este algoritmo al x + A, donde 'A' es cualquier número.

una variante mejorada de esta solución:

Long y = x + 1 + ((x >> 63) << 1); 
Long z = y - (y >> 63); 
return z & Long.MAX_VALUE; 

Answer 4

partir de la información vista teórico, que tienen 2^64 valores para trazar un mapa en 2^63-1 valores.

Como tal, la cartografía es trivial con el operador módulo, ya que siempre tiene un resultado no negativo:

y = 1 + x % 0x7fffffffffffffff; // the constant is 2^63-1 

Esto podría ser bastante caro, así que ¿qué más es posible?

La matemática simple 2^64 = 2 * (2^63 - 1) + 2 dice que tendremos dos mapeos de valores de fuente a un valor objetivo excepto en dos casos especiales, donde tres irán a uno. Piense en estos dos valores especiales de 64 bits, llámelos x1 y x2, que comparten un objetivo con otros dos valores fuente. En la expresión anterior mod, esto ocurre al "envolver". Los valores objetivo y=2^31-2 y y=2^31-3 tienen tres asignaciones. Todos los demás tienen dos.Dado que tenemos que usar algo más complejo que mod de todos modos, busquemos una forma de asignar los valores especiales donde queramos a bajo costo

Para la ilustración vamos a trabajar con el mapeo de un intde 4 bits en [-8 .. 7] a y en [1..7], en lugar del espacio de 64 bits.

un curso fácil es tener x valores en el mapa [1..7] a sí mismos, entonces el problema se reduce a la cartografía de x en [-8..0] para y en [1..7]. Tenga en cuenta que hay 9 valores de origen aquí y solo 7 objetivos como se discutió anteriormente.

Existen obviamente muchas estrategias. En este punto, probablemente puedas ver un gazzilion. Describiré solo uno que es particularmente simple.

Deje y = 1 - x para todos los valores excepto casos especiales x1 == -8 y x2 == -7. La función hash entera se convierte así en

y = x <= -7 ? S(x) : x <= 0 ? 1 - x : x; 

Aquí S(x) es una función simple que dice donde x1 y x2 se asignan. Elija S según lo que sabe sobre los datos. Por ejemplo, si cree que los valores de objetivo altos son poco probables, identifíquelos en 6 y 7 con S(x) = -1 - x.

La asignación final es:

-8: 7 -7: 6 -6: 7 -5: 6 -4: 5 -3: 4 -2: 3 -1: 2 
0: 1  1: 1  2: 2  3: 3  4: 4  5: 5  6: 6  7: 7 

Tomando esta lógica hasta el espacio de 64 bits, que tendría

y = (x <= Long.MIN_VALUE + 1) ? -1 - x : x <= 0 ? 1 - x : x; 

Muchos otros tipos de afinación son posibles dentro de este marco.

Answer 5

optaría por el más simple, pero no del todo momento la versión perder:

public static long postiveHash(final long hash) { 
    final long result = hash & Long.MAX_VALUE; 
    return (result != 0) ? result : (hash == 0 ? 1 : 2); 
} 

Esta aplicación paga una operación condicional para todos menos dos posibles entradas: 0 y MIN_VALUE. A esos dos se les asigna asignaciones de valores diferentes con la segunda condición. Dudo que obtenga una mejor combinación de (código) simplicidad y complejidad (computacional).

Por supuesto, si puede vivir con una peor distribución, es mucho más simple. Al restringir el espacio de 1/4 a 1/2 en lugar de -1 se puede obtener:

public static long badDistribution(final long hash) { 
    return (hash & -4) + 1; 
} 

Answer 6

Si el valor es positivo, es probable que se puede utilizar directamente, de lo contrario, invertir todos los bits:

x >= 0 ? hash = x : hash = x^Long.MIN_VALUE 

Sin embargo, debe codificar este valor un poco más si se correlacionan los valores de x (es decir: los objetos similares producen valores similares para x), tal vez con

hash = a * (hash + b) % (Long.MAX_VALUE) + 1 

para algunas constantes positivas a y b, donde a debe ser bastante grande y b impide que 0 siempre se correlacione con 1. Esto también asigna todo a [1, Long.MAX_VALUE] en lugar de [0, Long.MAX_VALUE].Al modificar los valores para a y b, también podría implementar funcionalidades hash más complejas como cooko hashing, que necesitan dos funciones hash diferentes.

Tal solución definitivamente debe ser preferida en lugar de una que ofrece "distribución de colisión extraña" para los mismos valores cada vez que se utiliza.

Answer 7

Puede hacerlo sin ningún tipo de condicionales y en una sola expresión utilizando el operador de desplazamiento sin signo:

public static int makePositive(int x) { 
    return (x >>> 1) + (~x >>> 31); 
} 

Answer 8

Esta parece ser la más sencilla de todas:

(x % Long.MAX_VALUE) + 1 

Yo estaría interesado en la velocidad comparaciones de todos los métodos dados

Answer 9

Solo Y su valor de entrada con Long.MAX_VALUE y O con 1. Nada más se necesita.

Ex:

long hash = (input & Long.MAX_VALUE) | 1;