Hashtable Hashtable evitar el hashcode negativo

Question

Me pregunto por qué el Hashtable evita el uso de hashcode negativo?

int hash = key.hashCode(); 
int index = (hash & 0x7FFFFFFF) % tab.length; 

Dónde (hash & 0x7FFFFFFF) hace que el bit de signo que se va a 0 positivo, pero ¿por qué nosotros no pudimos tratar el entero de 32 bits sin signo como? o incluso utilizar los trucos modulares para que sea positivo. Por ejemplo,

public static long int_mod(int hashcode, int tab_length){ 
    return (hashcode % tab_length + tab_length) % tab_length; 
} 

Answer 1

El valor tiene que ser entre 0 y tab.length - 1 porque se utiliza como un índice en una matriz interna (tab en este caso) el almacenamiento de los valores (y elementos de desbordamiento). Por lo tanto, no puede ser negativo.

Asumo (hash & 0x7FFFFFFF) % tab.length se utiliza de preferencia de (hashcode % tab.length + tab.length) % tab.length porque es más rápido sin aumentar excesivamente el riesgo de colisiones, pero se tendría que encontrar un documento de diseño o hablar con los desarrolladores originales de saber con seguridad.

Answer 2

... pero ¿por qué no nos ...

Estás preguntando por qué se eligió una implementación particular. Nadie puede decirte eso, excepto tal vez el autor original del código, si él o ella lo recuerda.

Siempre hay varias formas de implementar una idea en el código. La persona que está escribiendo el código tiene que elegir uno de ellos. No tiene mucho sentido preguntar, después del hecho, por qué no se eligió otra implementación particular.

Answer 3

Java no tiene un tipo nativo sin signo. Si el hashCode tuviera valores negativos, entonces tendremos que aplicar dichos trucos de enmascaramiento dondequiera que usemos hashCode como un índice en el conjunto.

Answer 4

Nadie puede hablar de por qué el autor original eligió esa implementación, excepto a sí mismo (y tal vez a sus colegas). Realmente no importa de todos modos porque funciona bien.

Acerca de la implementación propuesta: Probablemente no haga lo que piensa que debería estar haciendo. Debe actualizar lo que el operador% en java realmente hace: For example here. Agregue un desbordamiento de enteros en la mezcla y su expresión propuesta puede dar como resultado valores negativos ...

Answer 5

Existe una razón ostensiblemente grande por la que no podemos tratar el int firmado como unsigned: los desarrolladores originales de Java pensaban que el soporte sin firma era un complicación innecesaria, ya que la aritmética sin signo puede ser confusing. Esto no ha sido un problema lo suficientemente grande como para que Java aborde desde entonces.

Como verdesmerald mentioned, ya que no hay un registro claro de por qué (hash & 0x7FFFFFFF) % tab.length fue elegido sobre algo en el sentido de que su modding inteligente, aunque podemos encontrar justificaciones para la decisión, en última instancia, sólo podemos especular acerca de por qué se hizo.

Un último punto de semántica, que probablemente no es tan importante: no es tanto que Hashtable no esté utilizando códigos de hash negativos, sino que los hashcodes se están "traduciendo" a un formulario no negativo para el índice.

Answer 6

Si mantiene su capacidad de una potencia de 2,

private static final int CAPACITY = 64; 
private static final int HASH_MASK = CAPACITY - 1; 

final int index = obj.hashCode() & HASH_MASK; 

Básicamente, enmascarar todos menos los bits inferiores en los que está interesado. Suponiendo que los N bits inferiores tienen una distribución parecida a la del código hash completo.