Mapeo de cadenas en enteros

Question

¿Cuál es la manera más fácil en Java para mapear cuerdas (Java String) a números enteros (positivos) (Java int), de manera que

• cuerdas iguales se asignan a la igualdad de números enteros, y
• cadenas de caracteres diferentes a diferentes enteros?

Por lo tanto, similar a hashCode() pero diferentes cadenas son necesarias para producir diferentes números enteros. Entonces, en cierto sentido, sería un hasCode() sin la posibilidad de colisión.

Una solución obvia mantendría una tabla de asignación de cadenas a enteros, y un contador para garantizar que a las nuevas cadenas se les asigna un nuevo entero. Me pregunto cómo este problema generalmente se resuelve. También sería interesante extenderlo a otros objetos aparte de las cadenas.

Answer 1

Esto es imposible de lograr sin restricciones, simplemente porque hay más cadenas posibles que enteros, por lo que eventualmente se le acabarán los números.

Una solución solo es posible si limita el número de cadenas utilizables. Entonces puedes usar un contador simple. Aquí hay una implementación simple donde se pueden usar todas (2^32 = 4294967296 cadenas diferentes). No importa que use mucha memoria.

import java.util.HashMap; 
import java.util.Map; 

public class StringToInt { 

    private Map<String, Integer> map; 

    private int counter = Integer.MIN_VALUE; 

    public StringToInt() { 
     map = new HashMap<String, Integer>(); 
    } 

    public int toInt(String s) { 
     Integer i = map.get(s); 
     if (i == null) { 
      map.put(s, counter); 
      i = counter; 
      ++counter; 
     } 
     return i; 
    } 
} 

Answer 2

No va a ser una solución fácil o completa. Usamos hash porque hay mucho más cadenas posibles que entradas. Las colisiones son solo una limitación de usar un número finito de bits para representar enteros.

Answer 3

¿Se puede usar un Mapa para indicar a qué cadenas ya le han asignado números enteros? Esa es una especie de solución de "base de datos", donde asigna cada cadena una "clave primaria" de una secuencia a medida que aparece. Luego, coloca el par de Cadenas y Entero en un Mapa para que pueda buscarlo nuevamente. Y si necesita la Cadena para un Entero dado, también puede poner el mismo par en un Mapa.

Answer 4

Dado que las cadenas en java no tienen límites de longitud, y cada carácter tiene 16 bits, y las entradas tienen 32 bits, solo se puede producir una asignación única de Cadenas a ints si las Cadenas tienen hasta dos caracteres. Pero se puede usar BigInteger para producir un mapeo único, con algo como:

String s = "my string"; 
BigInteger bi = new BigInteger(s.getBytes()); 

mapeo inverso:

String str = new String(bi.toByteArray()); 

Answer 5

que iba a tratar de hacerlo mediante la introducción de un objeto que sostiene Mapa y mapa. Agregar cadenas a ese objeto (o tal vez hacer que se creen a partir de dicho objeto) les asignará un valor entero. Solicitar un valor entero para una cadena ya registrada devolverá el mismo valor.

Inconvenientes: Lanzamientos diferentes producirán enteros diferentes para la misma cadena, dependiendo del orden, a menos que de alguna manera persista todo. Además, no está muy orientado a objetos y requiere un objeto especial para crear/registrar una Cadena. lado positivo: es bastante similar a la internalización de cadenas y es fácilmente comprensible. (Además, solicitó una forma fácil, no elegante.)

Para el caso más general, puede crear una subclase de alto nivel de Objeto, introducir un método "entero" allí y extender cada clase de eso. Creo que, sin embargo, ese camino lleva a las lágrimas.

Answer 6

Si por el número entero que quiere decir el tipo de datos, a continuación, como otros críticos han explicado esto es casi imposible, debido al hecho de que el tipo de datos entero es de tamaño fijo, y las cuerdas no están consolidadas.

Sin embargo, si simplemente quiere decir un número positivo, entonces teóricamente debería interpretar la cadena como si fuera un "entero" simplemente considerándola como una matriz de bytes (en una codificación consistente).También podría tratarlo como una matriz de enteros de longitud arbitraria, pero si puede hacerlo, ¿por qué no usar una cadena? :)

Implementación hablando, esto generalmente se "resuelve" usando un código hash y simplemente comprobando dos veces cualquier colisión, ya que es probable que no haya ninguna y en caso de que haya una colisión, todavía funciona ser tiempo constante. Sin embargo, si esto no es aplicable, no estoy seguro de cuál sería la mejor solución.

Interesante pregunta.

Answer 7

En la mayoría de las implementaciones de tipo hashcode(), las colisiones se aceptan como inevitables y se prueban.

Si absolutamente no debe haber colisiones, garantizado, la solución que perfilará funcionará.

Aparte de esto, hay funciones hash criptográficas como MD5 y SHA, donde las colisiones son extremadamente improbables (aunque con un gran esfuerzo puede forzarse). La arquitectura de criptografía Java tiene implementaciones de estos. Esos métodos tal vez sean más rápidos que una buena implementación de su solución para conjuntos muy grandes. También se ejecutarán en tiempo constante y darán el mismo código para la misma cadena, sin importar en qué orden se agreguen las cadenas. Además, no requiere almacenar cada cadena. Los resultados de hash Crypto se pueden considerar como enteros, pero no caben en un int java: se puede usar un BigInteger para mantenerlos como se sugiere en otra respuesta. Por cierto, si te molesta la idea de que una colisión sea "extremadamente improbable", es probable que haya una probabilidad similar de que un poco voltee aleatoriamente en la memoria de tu computadora o en tu disco duro y provoque que un programa se comporte de manera diferente a la tuya. espera :-)

Nota, también hay algunas debilidades teóricas en algunas funciones hash (por ejemplo, MD5) pero para sus propósitos probablemente no importe y podría usar la función más eficiente - esas debilidades son solo relevantes si alguien trata maliciosamente de encontrar cadenas que tengan el mismo código que otra cadena.

editar: Me acabo de dar cuenta en el título de su pregunta, parece que quiere un mapeo bidireccional, aunque en realidad no dice esto en la pregunta. No es posible (por diseño) pasar de un hash Crypto a la cadena original. Si realmente lo necesita, tendrá que almacenar un mapa que manipule los hashes nuevamente en cadenas.

Answer 8

Tenga una mirada en perfect hashing.

Answer 9

Como perfila, una tabla hash que resuelve las colisiones es una solución estándar. También puede usar un trie de búsqueda de estilo de Bentley/Sedgewick, que en muchas aplicaciones es más rápido que hashing.

Si sustituye 'puntero de búsqueda' para 'entero único' se puede ver Dave Hanson's solution to this problem in C. Esta es una bonita abstracción porque

• Los punteros se pueden seguir utilizando como cadenas de caracteres C.

• Equal Strings hash a igual punteros, por lo que strcmp se pueden prescindir a favor de la igualdad del puntero, y los punteros se pueden utilizar como claves en otras tablas hash.

Si Java ofrece una prueba de la identidad del objeto String de objetos, entonces se puede jugar al mismo juego allí.