que - tipos de datos en java pdf

Asignación de cadenas a enteros

Question

¿Cuál es la forma más fácil en Java para asignar cadenas (Java String ) a enteros (positivos) (Java int ), de modo que

• el mapa de cadenas iguales para enteros iguales, y
• ¿diferentes cadenas se asignan a números enteros diferentes?

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

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

Answer 1

¿Puedes usar un mapa para indicar a qué cadenas ya tienes enteros asignados? 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 2

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 las entradas si las cadenas tienen hasta dos caracteres. Pero podría 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 3

Eche un vistazo al hashing perfecto .

Answer 4

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, está garantizado, la solución que describe funcionará.

Aparte de esto, existen 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 una 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 un poco cambie aleatoriamente la memoria de tu computadora o tu disco duro y provoque que un programa se comporte de forma diferente a la esperada :-)

Tenga en cuenta que también hay algunas debilidades teóricas en algunas funciones hash (p. Ej., MD5), pero para sus fines probablemente no importe y podría usar la función más eficiente, esas debilidades solo son relevantes si alguien trata maliciosamente de aparecer. con cadenas que tienen 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 5

No va a haber 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 6

Si se refiere al tipo de datos por entero, entonces como otros carteles han explicado esto es completamente imposible, debido al hecho de que el tipo de datos enteros es de tamaño fijo, y las cadenas están libres.

Sin embargo, si simplemente se refiere a un número positivo, 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? :)

En términos de implementación, esto generalmente se "resuelve" utilizando un código hash y simplemente revisando dos veces cualquier colisión, ya que es probable que no haya ninguna y, en caso de que se produzca una colisión, todavía funciona como un 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

Trataría de hacerlo introduciendo un objeto que contenga 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: diferentes lanzamientos arrojará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 fácilmente comprensible. (Además, pediste una manera fácil, no elegante).

Para el caso más general, puede crear una subclase de alto nivel de Object, introducir un método "integerize" allí y extender todas las clases desde allí. Creo que, sin embargo, ese camino lleva a las lágrimas.

Answer 8

A medida que describe, 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 "único puntero" por "único entero", puede ver la solución de Dave Hanson para este problema en C. Esta es una buena abstracción porque

• Los punteros aún se pueden usar como cadenas C.

• Equal Strings hash para punteros iguales, por strcmp se puede prescindir de strcmp a favor de la igualdad del puntero, y los punteros se pueden usar como claves en otras tablas hash.

Si Java ofrece una prueba de identidad de objetos en objetos String , entonces puedes jugar el mismo juego allí.

Answer 9

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

Una solución solo es posible cuando 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;
    }
}