vulnerability - java hashtable

Buena función hash para cuerdas

Question

Estoy intentando pensar una buena función hash para cadenas. Y estaba pensando que podría ser una buena idea resumir los valores de Unicode para los primeros cinco caracteres de la cadena (suponiendo que tiene cinco, de lo contrario, se detiene donde termina). ¿Sería una buena idea, o es una mala idea?

Estoy haciendo esto en Java, pero no me imagino que eso marcaría una gran diferencia.

Answer 1

Aquí hay un enlace que explica muchas funciones hash diferentes, por ahora prefiero la función hash ELF para su problema particular. Toma como entrada una cadena de longitud arbitraria.

Answer 2

Aquí hay una función hash simple que utilizo para una tabla hash que construí. Básicamente es para tomar un archivo de texto y almacenar cada palabra en un índice que representa el orden alfabético.

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

Lo que básicamente hace es que las palabras se hereden según su primera letra. Entonces, la palabra que comienza con ''a'' obtendría una clave hash de 0, ''b'' obtendría 1 y así sucesivamente y ''z'' sería 25. Los números y símbolos tendrían una clave de hash de 26. Aquí hay una ventaja que proporciona ; Puede calcular de forma fácil y rápida dónde se indexaría una palabra dada en la tabla hash, ya que todo está en orden alfabético, algo como esto: El código se puede encontrar aquí: https://github.com/abhijitcpatil/general

Dando el siguiente texto como entrada: Atticus le dijo a Jem un día: "Prefiero que le disparas a latas en el patio trasero, pero sé que irás tras las aves". Dispara a todos los arrendajos azules que quieras, si puedes golpearlos, pero recuerda que es un pecado matar a un ruiseñor. "Esa fue la única vez que escuché a Atticus decir que era un pecado hacer algo, y le pregunté a la señorita Maudie sobre eso. "Tu padre tiene razón", dijo. "Los sinsontes no hacen otra cosa que hacer música para que la disfrutemos. No se comen los jardines de las personas, no anidan en cunas de maíz, no hacen otra cosa que cantar sus corazones por nosotros. Es por eso que es un pecado matar a un ruiseñor.

Este sería el resultado:

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

Answer 3

Es una buena idea trabajar con un número impar cuando se trata de desarrollar una buena función de hast para la cuerda. esta función toma una cadena y devuelve un valor de índice, hasta ahora su trabajo es bastante bueno. y tiene menos colisión. el índice va de 0 a 300 quizás incluso más que eso, pero hasta ahora no he obtenido nada más elevado, incluso con palabras largas como "ingeniería electromecá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;
}

Otra cosa que puedes hacer es multiplicar cada carácter int parse por el índice a medida que aumenta como la palabra "bear" (0 * b) + (1 * e) + (2 * a) + (3 * r) que te dará un valor int para jugar. la primera función hash anterior colisiona en "aquí" y "escucha" pero sigue siendo excelente para dar algunos buenos valores únicos. el siguiente no choca con "aquí" y "escuchar" porque multiplico cada carácter con el índice a 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;
}

Answer 4

Esta función provista por Nick es buena, pero si usa un nuevo String (byte [] bytes) para realizar la transformación a String, falló. Puedes usar esta función para hacer eso.

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

Puede ser que esto pueda ayudar a alguien

Answer 5

Esto evitará cualquier colisión y será rápido hasta que usemos el cambio en los cálculos.

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

Answer 6

Probablemente deberías usar String.hashCode() .

Si realmente desea implementar hashCode usted mismo:

No se sienta tentado a excluir partes significativas de un objeto del cómputo del código hash para mejorar el rendimiento: Joshua Bloch, Java efectivo

Usar solo los primeros cinco caracteres es una mala idea . Piense en los nombres jerárquicos, como las URL: todos tendrán el mismo código hash (porque todos comienzan con "http: //", lo que significa que están almacenados en el mismo cubo en un mapa hash, y muestran un rendimiento terrible.

Aquí hay una historia de guerra parafraseada en el String hashCode de " Effective Java ":

La función String hash implementada en todas las versiones anteriores a 1.2 examinó como máximo dieciséis caracteres, espaciados uniformemente a lo largo de la cadena, comenzando con el primer carácter. Para grandes colecciones de nombres jerárquicos, como URL, esta función hash muestra un comportamiento terrible.

Answer 7

Se rumorea que FNV-1 es una buena función hash para cadenas.

Para cadenas largas (más largas que, digamos, alrededor de 200 caracteres), puede obtener un buen rendimiento de la función hash MD4 . Como función criptográfica, se rompió hace unos 15 años, pero para fines no criptográficos, sigue siendo muy bueno y sorprendentemente rápido. En el contexto de Java, tendría que convertir los valores de caracteres de 16 bits en palabras de 32 bits, por ejemplo, agrupando dichos valores en pares. Se puede encontrar una implementación rápida de MD4 en Java en sphlib . Probablemente exagerado en el contexto de una tarea en el aula, pero por lo demás vale la pena intentarlo.

Answer 8

Si desea ver las implementaciones estándar de la industria, me java.security.MessageDigest en java.security.MessageDigest .

"Los resúmenes de mensajes son funciones hash de una vía seguras que toman datos de tamaño arbitrario y dan como resultado un valor hash de longitud fija".

Answer 9

Si estás haciendo esto en Java, ¿por qué lo haces? Simplemente llame a .hashCode() en la cadena

Answer 10

Si se trata de una cuestión de seguridad, podría usar Java crypto:

import java.security.MessageDigest;

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

Answer 11

Usualmente los hash no hacen sumas, de lo contrario se stop y los pots tendrán el mismo hash.

y no lo limitaría a los primeros n caracteres porque de lo contrario la casa y las casas tendrían el mismo hash.

En general, los hash toman valores y los multiplican por un número primo (lo que hace más probable generar hashes únicos). Así que podrías hacer algo como:

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

Answer 12

sdbm: este algoritmo se creó para la biblioteca de base de datos sdbm (una reimplementación de dominio 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;
}

Answer 13

La función HashFunction de Guava ( jsdoc ) proporciona hashing decente no jsdoc .

Answer 14

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

Answer 15

// 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;
}

source lógica detrás de la función de hash djb2 - SO