Echando código: ¿Como crear una clave numérica de una palabra?

Suponga que tiene el siguiente problema: A usted le dan una lista de simbolos de la bolsa: SUNW, IBM, RHAT y le piden que los almacene internamente como una clave; Idealmente deberíamos generar un identificador único por cada palabra.

Bueno, en Java podemos llamar al método de la clase String llamado ‘hashcode’; Un hash no es más que una función de transformación que nos permite convertir una cosa en otra, usando un algoritmo conocido. En este caso logramos mapear nuestra cadena a un número único. Los Hashes no son perfectos, ya que pueden generar lo que se llaman colisiones (dos entradas producen el mismo hash) y es allí en donde entran varios algoritmos para manejar esos casos.

Aquí les dejo un código que utiliza la implementación interna de Java de ‘hashcode‘ y otro algoritmo el cual se aprovecha de la conversión de cada caracter en el objeto String a un char, para luego darle un peso dada su posición en la cadena (con lo cual obtenemos un número único).

Usted debe tener mucho cuidado al escoger una función Hash; Una buena función es aquella que tiene pocas colisiones, y sólo los matemáticos pueden demostrar con estadística si una función es buena. Yo en su caso mejor y utilizo un algoritmo que ya haya sido probado por alguien con anterioridad.

El código:

   1:/**
2: *
3: * You are given a list of Compay Ticker symbols. You want to save them as
4: * a unique code on a data structure.
5: * Hints: There are two solutions, one implies a hash and the other an array
6: * @author Jose V Nunez Z
7: * @version 0.1 - 02/28/2005
8: * License: GPL
9: * Blog: El Angel Negro - http://elangelnegro.blogspot.com
10: */
11:public class TickerCode {
12:
13: /**
14: * Command line entry point
15: * @param args - ignored
16: */
17: public static void main(String [] args) {
18: String [] symbols = {
19: "RHAT",
20: "IBM",
21: "SUNW",
22: "MSFT",
23: "TFSM"
24: };
25: int len = symbols.length;
26: for (int i = 0; i < len; i++) {
27: System.out.println(
28: "Code for symbol '" +
29: symbols[i] +
30: "'" +
31: " is " +
32: getCodeArray(symbols[i]) +
33: ", " +
34: getCodeHash(symbols[i])
35: );
36: }
37:
38: }
39:
40: /**
41: * The formula to get it using a Hash and a String:
42: *
43: * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
44: *
45: * Where s[n] is the char on the position 'n' for the String 's'
46: * 'n' is the length of the String 's'
47: * You repeat this process for all the chars on the String!
48: * @param symbol Simbol to convert
49: * @return int The code
50: */
51: private static int getCodeArray(String symbol) {
52: int code = 0;
53: char [] chars = symbol.toCharArray();
54: int len = chars.length;
55: for (int i = 0; i< len; i++) {
56: code += (chars[i]*31^(len-i));
57: }
58: return code;
59: }
60:
61: /**
62: * Uses the internal String hashcode
63: * @param symbol Simbol to convert
64: * @return int The code
65: */
66: private static int getCodeHash(String symbol) {
67: return symbol.hashCode();
68: }
69:
70:}

Una corrida de ejemplo:

[josevnz@XXX Ticker]$ javac TickerCode.java -d .
[josevnz@XXX Ticker]$ java TickerCode
Code for symbol ‘RHAT’ is 9391, 2514153
Code for symbol ‘IBM’ is 6690, 72276
Code for symbol ‘SUNW’ is 10313, 2556843
Code for symbol ‘MSFT’ is 9738, 2375924
Code for symbol ‘TFSM’ is 9730, 2572364

Y se lo puede bajar de aquí.