Uma function hash mais rápida

Estou tentando implementar minha própria function hash, eu adiciono os números ASCII de cada string, usando java. Eu encontro o código hash encontrando o mod do tamanho da tabela de hash e a sum. tamanho% sum Eu queria saber se havia uma maneira de usar o mesmo processo, mas reduzir colisões, ao procurar pela string?

Desde já, obrigado.

Eu olharia o código para String e HashMap, pois eles têm uma baixa taxa de colisão e não usam % e lidam com números negativos.

Da fonte para String

 public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; } 

Da fonte para o HashMap

 /** * Retrieve object hash code and applies a supplemental hash function to the * result hash, which defends against poor quality hash functions. This is * critical because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ final int hash(Object k) { int h = 0; if (useAltHashing) { if (k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h = hashSeed; } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 

Como o HashMap é sempre uma potência de 2 em tamanho, você pode usar

  hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); 

e

 /** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); } 

Usar & é muito mais rápido que % e somente retornar números positivos, pois o tamanho é positivo.

O Java String.hashcode () faz uma troca entre ser uma function hash realmente boa e ser o mais eficiente possível. Simplesmente sumr os valores de caractere em uma string não é uma function hash confiável.

Por exemplo, considere as duas cadeias dog e god . Uma vez que ambos contêm um ‘d’, ‘g’ e um ‘o’, nenhum método envolvendo apenas a adição resultará em um código hash diferente.

Joshua Bloch , que implementou boa parte do Java, discute o método String.hashCode () em seu livro Effective Java e fala sobre como, nas versões do Java anteriores a 1.3, a function String.hashCode () costumava considerar apenas 16 caracteres em uma determinada String. Isso ficou um pouco mais rápido do que a implementação atual, mas o resultado é um desempenho surpreendentemente ruim em determinadas situações.

Em geral, se o seu dataset específico é muito bem definido e você poderia explorar alguma exclusividade nele, você provavelmente poderia fazer uma function hash melhor. Para fins gerais Strings, boa sorte.