Boa função hash para strings

Eu estou tentando pensar em uma boa função de hash para strings. E eu estava pensando que seria uma boa idéia resumir os valores unicode para os cinco primeiros caracteres da string (supondo que ele possua cinco, caso contrário, pare onde termina). Seria uma boa ideia ou ruim?

Estou fazendo isso em Java, mas não imaginaria que isso faria muita diferença.

Geralmente, os hashes não fazem somas, caso contrário, stope potsterão o mesmo hash.

e você não o limitaria aos primeiros n caracteres porque, caso contrário, house e houses teriam o mesmo hash.

Geralmente, os hashs pegam valores e multiplicam-no 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 é algo de segurança, você pode usar criptografia Java:

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 deseja implementar o hashCode você mesmo:

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

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

Aqui está uma história de guerra parafraseada no hashCode String de " Java Efetivo ":

A função hash String implementada em todas as versões anteriores à 1.2 examinou no máximo dezesseis caracteres, espaçados uniformemente por toda a string, começando com o primeiro caractere. Para grandes coleções de nomes hierárquicos, como URLs, essa função de hash exibia um comportamento terrível.

Se você está fazendo isso em Java, por que está fazendo isso? Basta chamar .hashCode()a corda

O goiabaHashFunction ( javadoc ) fornece um hash decente não forte em criptografia.

Essa função fornecida por Nick é boa, mas se você usar a nova String (byte [] bytes) para fazer a transformação em String, ela falhará. Você pode usar esta função 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 que isso possa 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 função hash djb2 - SO

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

Para cadeias longas (com mais de, digamos, cerca de 200 caracteres), é possível obter um bom desempenho da função de hash MD4 . Como uma função criptográfica, ela foi quebrada cerca de 15 anos atrás, mas, para fins não criptográficos, ainda é muito boa e surpreendentemente rápida. No contexto de Java, você teria que converter os charvalores de 16 bits em palavras de 32 bits, por exemplo, agrupando esses valores em pares. Uma implementação rápida do MD4 em Java pode ser encontrada no sphlib . Provavelmente exagere no contexto de uma tarefa em sala de aula, mas vale a pena tentar.

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

"Os resumos de mensagens são funções de hash unidirecionais seguras que pegam dados de tamanho arbitrário e emitem um valor de hash de tamanho fixo".

aqui está um link que explica muitas funções hash diferentes, por enquanto eu prefiro a função hash ELF para o seu problema específico. Toma como entrada uma sequência de comprimento arbitrário.

sdbm: esse algoritmo foi criado para a biblioteca de banco de dados sdbm (uma reimplementação de domínio público do 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;
}

         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();
}

É uma boa idéia trabalhar com número ímpar ao tentar desenvolver uma boa função de hast para string. Essa função pega uma string e retorna um valor de índice, até agora funciona muito bem. e tem menos colisão. o índice varia de 0 a 300, talvez até mais do que isso, mas ainda não cheguei mais alto, 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<k; i++)
    {
        n = (int)key[i];
        u += 7*n%31;
    }
    return u%139;
}

Outra coisa que você pode fazer é multiplicar cada caractere analisado pelo índice, à medida que aumenta como a palavra "urso" (0 * b) + (1 * e) + (2 * a) + (2 * a) + (3 * r), o que lhe dará um valor int para brincar. a primeira função de hash acima colide em "aqui" e "ouça", mas ainda é ótima em fornecer bons valores exclusivos. o abaixo não colide com "aqui" e "ouve" porque eu multiplico cada caractere pelo índice à medida que aumenta.

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

    for (Uint i=0; i<k; i++)
    {
        n = (int)key[i];
        u += i*n%31;
    }
    return u%139;
}

Aqui está uma função de hash simples que eu uso para uma tabela de hash que criei. É basicamente para pegar um arquivo de texto e armazenar todas as palavras 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 sejam hash de acordo com a primeira letra. Assim, a palavra que começa com 'a' obteria uma chave de hash 0, 'b' obteria 1 e assim por diante e 'z' seria 25. Números e símbolos teriam uma chave de hash 26. Essa é uma vantagem oferecida ; Você pode calcular fácil e rapidamente onde uma determinada palavra seria indexada na tabela de hash, pois está tudo em ordem alfabética, algo como isto: Código pode ser encontrado aqui: https://github.com/abhijitcpatil/general

Entregando o seguinte texto: Atticus disse a Jem um dia: “Prefiro que você atire em latas no quintal, mas sei que você vai atrás de pássaros. Atire em todos os gaios azuis que você quiser, se conseguir atingi-los, mas lembre-se de que é pecado matar um pássaro zombeteiro. Foi a única vez que ouvi Atticus dizer que era pecado fazer alguma coisa, e perguntei a Miss Maudie sobre isso. "Seu pai está certo", disse ela. “Os zombadores não fazem uma coisa, exceto fazer música para nós apreciarmos. Eles não comem os jardins das pessoas, não se aninham nos berços de milho, eles não fazem uma coisa, mas cantam seus corações por nós. É por isso que é pecado matar um pássaro zombeteiro.

Esta seria a saída:

0 --> a a about asked and a Atticus a a 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

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

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