Coste de búsqueda de la cadena de prácticas y declaración de cadenas literales

Question

Dos preguntas.

1. Cuando declaramos cadenas literales, buscamos si hay la misma cadena en el grupo de cadenas de heap. ¿Es esto también una pasantía (pasante de método de la clase String)?

2. En mi pensamiento, cada declaración de cadena literal necesita una búsqueda binaria o algo por lo que cuesta al menos log (n) cuando n es el número de cadenas existentes en la piscina. Y si hay muchas cadenas en el conjunto, puede ser de alto costo. (¿tal vez la compensación de los costos de búsqueda y la memoria?) Desde este punto de vista, podría ser peligroso declarar cadenas literales mant. Cuán significativo es este costo de búsqueda y por qué java está diseñado de esta manera (grupo de búsqueda cuando se declaran cadenas literales).

A continuación se detalla lo que he mencionado.

---

Los JavaDoc for the java.lang.String class estados:

Strings son constantes; sus valores no se pueden cambiar después de que se crean. Los búferes de cadena admiten cadenas mutables. Debido a que los objetos String son inmutables, se pueden compartir.

http://www.janeg.ca/scjp/lang/strLiteral.html comentarios:

En otras palabras, debido a que el compilador sabe las cadenas de valor original no se puede cambiar una vez que se ha creado se puede utilizar de forma segura los datos existentes y evitar llenar la memoria con duplicados.

Answer 1

Estás confundiendo la complejidad del tiempo de compilación con la complejidad del tiempo de ejecución.

Cuando se carga la clase, sí hace una búsqueda para ver si cada literal ya existe (aunque me imagino que usaría un hashmap para O (1) búsqueda en lugar de su propuesta).

Cuando se ejecuta el código, tiene la referencia a la cadena en la memoria por lo que no hay un costo adicional que no sea literal.

Así que sí, los literales están internados. De acuerdo con Javadoc for String,

Un grupo de cadenas, inicialmente vacío, se mantiene en privado por la clase String.

Puede invocar intern() en una cadena para agregarlo a este grupo. De ello se deduce lógicamente que si a.equals(b) luego a.intern() == b.intern(), desde .intern(), se garantiza el retorno desde un grupo único.

Ejemplo:

class InternTest { 
    // assuming InternTest is the only class, internPool.size = 0 
    String x = "ABC"; // interned at class load, internPool.size = 1 
    String y = "DEF"; // interned at class load, internPool.size = 2 
    String z = "ABC"; // interned at class load, but match found - size = 2 still 

    void foo() { 
     // random int is just a mechanism to get something that I know won't 
     // be interned at loadtime - could have loaded from file or database too 
     int i = (new java.util.Random()).nextInt(1000) + 100; 
     int j = i; 
     String s = String.valueOf(i); // not yet interned, size = 2 still 
     String t = String.valueOf(j); // not yet interned, size = 2 still 

     String sIntern = s.intern(); // manually interned, size = 3 now 
     String tIntern = t.intern(); // manually interned, match found, size = 3 still 

     System.out.println("equals: " + (s.equals(t))); // should be true 
     System.out.println("== raw: " + (s == t)); // should be false, different variables 
     System.out.println("== int: " + (sIntern == tIntern)); // should be true, from unique pool 

     System.out.println("x and z: " + (x == z)); // should be true, interned at class load 
    } 

    public static void main(String[] args) { 
     (new InternTest()).foo(); 
    } 

} 

resultados cuando es ejecutado:

C:\Documents and Settings\glowcoder\My Documents>java InternTest 
equals: true 
== raw: false 
== int: true 
x and z: true 

Debo señalar que el supuesto nunca será verdadera. El lenguaje Java en sí tiene muchos String s que serían internados antes de que nuestro String haya tenido la oportunidad de ver la luz del día. Sin embargo, suponiendo que todo se carga secuencialmente, si solo considera el delta de Strings siendo internado, y no supone colisiones con internos existentes (todos sabemos que los internos pueden ser exigentes y llenos de drama, ¿no? snicker), entonces los números sí indique el delta del tamaño del grupo de cadenas.

Answer 2

1 - Cuando declaramos cadenas literales, buscamos si hay la misma cadena en el grupo de cadenas de heap. ¿Esto también es una pasantía (método interno de la clase String)?

Sí. Este proceso se llama internamiento. Sin embargo, sucede solo una vez ... cuando se carga la clase que contiene el literal.

2 - En mi opinión, cada declaración de cadena literal necesita una búsqueda binaria o algo por lo que cuesta al menos log (n) cuando n es el número de cadenas existentes en la agrupación.

No, no lo hace. El grupo es una tabla hash.

... Y si hay muchas cadenas en la piscina, puede ser un alto costo.

No, no lo hará. El costo de una búsqueda en la tabla hash del grupo de cadenas es O(1).

... En este punto de vista, podría ser peligroso declarar muchas cadenas literales.

El costo no es significativo en comparación con los otros costos de carga y luego JIT compila un archivo de clase. No existe un "peligro" relacionado con el rendimiento al declarar muchas cadenas literales.

Obviamente, los objetos String correspondientes a los literales de cadena ocupan la memoria "permanentemente", y generalmente no desea perder memoria innecesariamente. Pero si necesita usar esas cadenas constantes, tienen que ser representadas de alguna manera. Y otras maneras de representarlos usan la memoria de otras maneras o involucran otros costos de tiempo de ejecución; p.ej. los costos de leerlos desde un archivo o recuperarlos de la base de datos.

El beneficio de los literales de cadena de interning es que el montón no se llena de copias múltiples de la misma cadena literal. Esto probablemente no sea significativo para las aplicaciones SE/EE típicas, pero para las plataformas ME la memoria de almacenamiento dinámico es escasa, y sería una mala idea desperdiciarla.

---

@RENO pregunta sobre el número de veces que las cadenas se internan.Hay dos casos:

• llamadas explícitas a String.intern() suceder tantas (o tan pocos) momentos en que la aplicación decide hacer.

• Para los literales de cadena, el compilador javac se asegurará de que un archivo .class determinado no contenga copias múltiples de cualquier literal String en su conjunto constante. Esto significa que una clase que tiene un literal dado en muchos lugares solo dará como resultado que el literal sea internado una vez cuando se cargue la clase. Sin embargo, si tiene dos clases con la misma cadena literal en su respectivo código fuente, ambas tendrán el valor de la cadena en sus respectivas agrupaciones constantes, y ambas internarán la cadena cuando se carguen las clases respectivas.