¿Cuántos caracteres puede tener una cadena Java?

157

Estoy tratando el problema The Next Palindrome de Sphere Online Judge (SPOJ) donde necesito encontrar un palindrome para un número entero de hasta un millón de dígitos. Pensé en usar las funciones de Java para revertir cadenas, pero ¿permitirían que una cadena sea tan larga?

java string andandandand
fuente
¿Está diciendo que necesita escribir una función que genere palíndromos, cuyo tamaño es especificado por el usuario y puede tener hasta 1 millón de caracteres de longitud?
Robert
3
El problema (de SPOJ) puede contener un archivo de 100 Gigabytes, ¿y le gustaría cargarlo en una cadena a la vez? En serio ... ¡usa un escáner!
Grim
Posible duplicado de la longitud máxima
call

Respuestas:

242

Deberías poder obtener una cadena de longitud

  1. Integer.MAX_VALUEsiempre 2.147.483.647 (2 31 - 1)
    (Definido por la especificación de Java, el tamaño máximo de una matriz, que la clase String usa para almacenamiento interno)
    O

  2. Half your maximum heap size(ya que cada carácter tiene dos bytes) el que sea más pequeño .

Bill el lagarto
fuente
43
... o su tamaño de
almacenamiento
2
@ ChssPly76: Sí, eso es correcto. Edité mi respuesta, gracias.
Bill the Lizard
2
¿Cómo puedo saber el tamaño máximo de almacenamiento dinámico? Además, no sé qué máquina virtual de Java está utilizando el juez para probar mi problema. ¿Es Integer.MAX_VALUE parte de la especificación de JVM dependiente?
andandandand
66
Integer.MAX_VALUE siempre es 2147483647 (2 ^ 31 - 1), eso es parte de la Especificación de Java.
cd1
44
Suponiendo una JVM de 64 bits, ya que necesitaría 8 GB de memoria virtual para almacenar una cadena de esa longitud.
Robert Fraser
21

Creo que pueden tener hasta 2 ^ 31-1 caracteres, ya que están en una matriz interna, y las matrices están indexadas por enteros en Java.

aperkins
fuente
La implementación interna es irrelevante; por ejemplo, no hay ninguna razón por la que los datos de los personajes no se puedan almacenar en una matriz de largos. El problema es que la interfaz usa ints para la longitud. getBytesy similares pueden tener problemas si intenta una cadena muy grande.
Tom Hawtin - tackline
Eso es cierto, estaba insinuando ese hecho. Culpa mía.
aperkins
15

Si bien, en teoría, puede caracteres Integer.MAX_VALUE, la JVM está limitada en el tamaño de la matriz que puede usar.

public static void main(String... args) {
    for (int i = 0; i < 4; i++) {
        int len = Integer.MAX_VALUE - i;
        try {
            char[] ch = new char[len];
            System.out.println("len: " + len + " OK");
        } catch (Error e) {
            System.out.println("len: " + len + " " + e);
        }
    }
}

en Oracle Java 8 actualización 92 impresiones

len: 2147483647 java.lang.OutOfMemoryError: Requested array size exceeds VM limit
len: 2147483646 java.lang.OutOfMemoryError: Requested array size exceeds VM limit
len: 2147483645 OK
len: 2147483644 OK

Nota: en Java 9, las cadenas utilizarán el byte [], lo que significa que los caracteres de varios bytes utilizarán más de un byte y reducirán aún más el máximo. Si tiene los cuatro puntos de código de byte, por ejemplo, emojis, solo obtendrá alrededor de 500 millones de caracteres

Peter Lawrey
fuente
2
Las cadenas compactas en Java 9 usan codificación Latin-1 o UTF-16. Sin codificación de longitud variable, es decir, sin caracteres de tres bytes.
Apangin
@apangin "No es un objetivo utilizar codificaciones alternativas como UTF-8" gracias por la corrección.
Peter Lawrey
5

¿Has considerado usar en BigDecimallugar de Stringmantener tus números?

Thorbjørn Ravn Andersen
fuente
1
Depende de lo que haga la aplicación con los números. Si solo va a hacer cosas textuales como encontrar palíndromos, contar dígitos (decimales), entonces una Cadena es mejor. Si va a hacer aritmética, un BigDecimal (o BigInteger) es mejor.
Stephen C
El problema es "Para cada K, genera el palíndromo más pequeño que K". (donde K es el número dado). Sería trivialmente simple generar el primer palíndromo más pequeño que K. Necesitas aritmética para encontrar uno más grande que K. Ejemplo: Encuentra el próximo palíndromo más grande que 999999999999, o el próximo palíndromo más grande que 12922.
Thorbjørn Ravn Andersen
4

Integer.MAX_VALUE es el tamaño máximo de la cadena + depende del tamaño de su memoria, pero el problema en el juez en línea de la esfera no tiene que usar esas funciones

Mite Mitreski
fuente
3

Java9 usa el byte [] para almacenar String.value, por lo que solo puede obtener cadenas de 1GB en Java9. Java8 por otro lado puede tener cadenas de 2GB.

Por carácter quiero decir "char", algunos caracteres no son representables en BMP (como algunos de los emojis), por lo que tomará más (actualmente 2) caracteres.

Revin
fuente
44
¿Podría adjuntar una referencia para Java-9 que limita el tamaño de la cadena a 1 GB de 2 GB
Aditya Gupta
-1

La parte del montón empeora, mis amigos. No se garantiza que UTF-16 esté limitado a 16 bits y puede expandirse a 32

Joe Plante
fuente
2
Excepto que el chartipo de Java es exactamente de 16 bits, por lo que la cantidad de bits que UTF-16 usa realmente no importa ...
awksp