Boa function hash para seqüências de caracteres

Eu estou tentando pensar em uma boa function de hash para seqüências de caracteres. E eu estava pensando que seria uma boa idéia resumir os valores unicode para os primeiros cinco caracteres da string (assumindo que ela tenha cinco, caso contrário, pare onde ela termina). Isso seria uma boa ideia, ou é ruim?

Eu estou fazendo isso em Java, mas não imagino que faria muita diferença.

Normalmente hashes não fazem sums, caso contrário, stop e os pots terão o mesmo hash.

e você não o limitaria aos primeiros n caracteres porque de outra forma a casa e as casas teriam o mesmo hash.

Geralmente os hashs pegam valores e os multiplicam por um número primo (aumenta a probabilidade de gerar hashes exclusivos) Assim, você pode fazer algo como:

 int hash = 7; for (int i = 0; i < strlen; i++) { hash = hash*31 + charAt(i); } 

Se é uma coisa de segurança, você poderia usar o Java crypto:

 import java.security.MessageDigest; MessageDigest messageDigest = MessageDigest.getInstance("SHA-256"); messageDigest.update(stringToEncrypt.getBytes()); String encryptedString = new String(messageDigest.digest()); 

Você provavelmente deve usar String.hashCode () .

Se você realmente quiser implementar o hashCode você mesmo:

Não fique tentado a excluir partes significativas de um object da computação do código de hash para melhorar o desempenho – Joshua Bloch, Effective Java

Usar apenas os primeiros cinco caracteres é uma má ideia . Pense em nomes hierárquicos, como URLs: todos eles terão o mesmo código hash (porque todos começam com “http: //”, o que significa que eles são armazenados no mesmo intervalo em um mapa de hash, exibindo um desempenho péssimo.

Aqui está uma história de guerra parafraseada no String hashCode de ” Effective Java “:

A function de hash String implementada em todos os releases anteriores ao 1.2 examinava no máximo dezesseis caracteres, uniformemente espaçados em toda a string, começando com o primeiro caractere. Para grandes collections de nomes hierárquicos, como URLs, essa function hash exibe um comportamento terrível.

Se você está fazendo isso em Java, por que está fazendo isso? Apenas chame .hashCode() na string

O HashFunction ( javadoc ) do Guava fornece hashing decente e não criptografado.

Esta function fornecida por Nick é boa, mas se você usar new String (byte [] bytes) para fazer a transformação para String, ela falhou. Você pode usar essa function para fazer isso.

 private static final char[] hex = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' }; public static String byteArray2Hex(byte[] bytes) { StringBuffer sb = new StringBuffer(bytes.length * 2); for(final byte b : bytes) { sb.append(hex[(b & 0xF0) >> 4]); sb.append(hex[b & 0x0F]); } return sb.toString(); } public static String getStringFromSHA256(String stringToEncrypt) throws NoSuchAlgorithmException { MessageDigest messageDigest = MessageDigest.getInstance("SHA-256"); messageDigest.update(stringToEncrypt.getBytes()); return byteArray2Hex(messageDigest.digest()); } 

Pode ser isso pode ajudar alguém

 // djb2 hash function unsigned long hash(unsigned char *str) { unsigned long hash = 5381; int c; while (c = *str++) hash = ((hash < < 5) + hash) + c; /* hash * 33 + c */ return hash; } 

Lógica de origem por trás da function de hash djb2 - SO

Se você quiser ver as implementações padrão do setor, eu verificaria o java.security.MessageDigest .

“As compilações de mensagens são funções hash unidirecionais seguras que pegam dados de tamanho arbitrário e geram um valor de hash de comprimento fixo.”

Há rumores de que o FNV-1 é uma boa function de hash para strings.

Para strings longas (mais do que, digamos, cerca de 200 caracteres), você pode obter um bom desempenho da function hash MD4 . Como uma function criptográfica, ele foi quebrado há cerca de 15 anos, mas para fins não criptocharts, ainda é muito bom e surpreendentemente rápido. No contexto de Java, você teria que converter os valores de char 16 bits em palavras de 32 bits, por exemplo, agrupando esses valores em pares. Uma rápida implementação do MD4 em Java pode ser encontrada em sphlib . Provavelmente um exagero no contexto de uma tarefa em sala de aula, mas vale a pena tentar.

sdbm: este algoritmo foi criado para a biblioteca de database sdbm (uma reimplementação de domínio público de ndbm)

 static unsigned long sdbm(unsigned char *str) { unsigned long hash = 0; int c; while (c = *str++) hash = c + (hash < < 6) + (hash << 16) - hash; return hash; } 

aqui está um link que explica muitas funções hash diferentes, por enquanto eu prefiro a function hash ELF para o seu problema em particular. Toma como input uma string de comprimento arbitrário.

  public String hashString(String s) throws NoSuchAlgorithmException { byte[] hash = null; try { MessageDigest md = MessageDigest.getInstance("SHA-256"); hash = md.digest(s.getBytes()); } catch (NoSuchAlgorithmException e) { e.printStackTrace(); } StringBuilder sb = new StringBuilder(); for (int i = 0; i < hash.length; ++i) { String hex = Integer.toHexString(hash[i]); if (hex.length() == 1) { sb.append(0); sb.append(hex.charAt(hex.length() - 1)); } else { sb.append(hex.substring(hex.length() - 2)); } } return sb.toString(); } 

Isso evitará qualquer colisão e será rápido até usarmos o deslocamento nos cálculos.

  int k = key.length(); int sum = 0; for(int i = 0 ; i < k-1 ; i++){ sum += key.charAt(i)<<(5*i); } 

É uma boa ideia trabalhar com números ímpares quando se tenta desenvolver uma boa function hast para string. esta function pega uma string e retorna um valor de índice, até agora seu trabalho é muito bom. e tem menos colisão. o índice varia de 0 a 300, talvez até mais do que isso, mas eu não tenho sido tão alto até agora, mesmo com palavras longas como “engenharia eletromecânica”

 int keyHash(string key) { unsigned int k = (int)key.length(); unsigned int u = 0,n = 0; for (Uint i=0; i 

outra coisa que você pode fazer é multiplicar cada caractere int pelo índice, pois ele aumenta como a palavra "suportar" (0 * b) + (1 * e) + (2 * a) + (3 * r), que lhe dará um valor int para brincar. a primeira function de hash acima colide com "aqui" e "ouça", mas ainda assim é excelente em fornecer bons valores únicos. o que está abaixo não colide com "aqui" e "ouça" porque eu multiplico cada caractere pelo índice à medida que ele aumenta.

 int keyHash(string key) { unsigned int k = (int)key.length(); unsigned int u = 0,n = 0; for (Uint i=0; i 

Aqui está uma function hash simples que eu uso para uma tabela de hash que eu construí. É basicamente para pegar um arquivo de texto e armazena cada palavra em um índice que representa a ordem alfabética.

 int generatehashkey(const char *name) { int x = tolower(name[0])- 97; if (x < 0 || x > 25) x = 26; return x; } 

O que isso basicamente faz é que as palavras são divididas de acordo com a primeira letra. Então, a palavra começando com ‘a’ receberia uma chave de hash de 0, ‘b’ obteria 1 e assim por diante e ‘z’ seria 25. Números e símbolos teriam uma chave de hash de 26. Há uma vantagem que isso fornece ; Você pode calcular fácil e rapidamente onde uma determinada palavra seria indexada na tabela de hash, já que está tudo em ordem alfabética, algo assim: O código pode ser encontrado aqui: https://github.com/abhijitcpatil/general

Dando o seguinte texto como input: Atticus disse a Jem um dia: “Eu prefiro que você atire em latas no quintal, mas eu sei que você vai atrás dos pássaros. Atire em todos os gralhas azuis que você quiser, se você puder acertá-los, mas lembre-se que é pecado matar um tordo. Essa foi a única vez que ouvi Atticus dizer que era pecado fazer algo, e perguntei a Maudie sobre isto. “Seu pai está certo”, disse ela. “Mockingbirds não fazem uma coisa, exceto fazer música para nós curtirmos. Eles não comem os jardins das pessoas, não se aninham em berços de milho, eles não fazem uma coisa, mas cantam seus corações para nós. É por isso que é pecado matar um títere.

Esta seria a saída:

 0 --> aa about asked and a Atticus aa all after at Atticus 1 --> but but blue birds. but backyard 2 --> cribs corn can cans 3 --> do don't don't don't do don't do day 4 --> eat enjoy. except ever 5 --> for for father's 6 --> gardens go 7 --> hearts heard hit 8 --> it's in it. I it I it's if I in 9 --> jays Jem 10 --> kill kill know 11 --> 12 --> mockingbird. music make Maudie Miss mockingbird.” 13 --> nest 14 --> out one one only one 15 --> people's 16 --> 17 --> right remember rather 18 --> sin sing said. she something sin say sin Shoot shot said 19 --> to That's their thing they They to thing to time the That to the the tin to 20 --> us. up us 21 --> 22 --> why was was want 23 --> 24 --> you you you'll you 25 --> 26 --> “Mockingbirds ” “Your 'em “I'd