Вопрос: String.intern () против ручного сопоставления строк и идентификаторов?


Я помню, что видел пару строковых программ, которые выполняют много строкового сравнения, но относительно немного строковых манипуляций, и которые использовали отдельную таблицу для сопоставления строк для идентификаторов для эффективного равенства и уменьшения объема памяти, например:

public class Name {
    public static Map<String, Name> names = new SomeMap<String, Name>();
    public static Name from(String s) {
        Name n = names.get(s);
        if (n == null) {
            n = new Name(s);
            names.put(s, n);
        }
        return n;
    }
    private final String str;
    private Name(String str) { this.str = str; }
    @Override public String toString() { return str; }
    // equals() and hashCode() are not overridden!
}

Я уверен, что одна из этих программ была javac из OpenJDK, поэтому не какое-нибудь игрушечное приложение. Конечно, фактический класс был более сложным (и также я думаю, что он реализовал CharSequence), но вы поняли, что вся программа была замусорена Name в любом месте, которое вы ожидаете String, а в редких случаях, когда нужна обработка строк, она преобразуется в строки и затем кэширует их снова, концептуально вроде:

Name newName = Name.from(name.toString().substring(5));

Я думаю, что я понимаю суть этого - особенно когда есть много одинаковых строк вокруг и много сравнений, но не может быть достигнуто путем использования обычных строк и internих? документация для String.intern() прямо говорит:

...
  Когда вызывается метод intern, если пул уже содержит строку, равную этому объекту String, как определено методом equals (Object), возвращается строка из пула. В противном случае этот объект String добавляется в пул и возвращается ссылка на этот объект String.

Из этого следует, что для любых двух строк s и t s.intern () == t.intern () истинно тогда и только тогда, когда s.equals (t) истинно.
  ...

Так, каковы преимущества и недостатки ручного управления Name-подобный класс против использования intern()?

То, о чем я думал до сих пор, было:

  • Ручное управление средством карты с использованием обычной кучи, intern() использует permgen.
  • При ручном управлении картой вам нравится проверка типов, которая может проверить, что это Name, в то время как интернированная строка и строка без интернетов имеют один и тот же тип, поэтому в некоторых местах можно забыть о интернировании.
  • Полагаясь на intern() означает повторное использование существующего, оптимизированного, проверенного и проверенного механизма без кодирования каких-либо дополнительных классов.
  • Ручное управление результатами карты приводит к тому, что код становится более запутанным для новых пользователей, а строгие операции становятся более громоздкими.

... но я чувствую, что мне здесь что-то не хватает.


4


источник


Ответы:


К сожалению, String.intern() может быть медленнее, чем простой синхронизированный HashMap. Это не должно быть настолько медленным, но на сегодняшний день в Oracle JDK он медленный (вероятно, из-за JNI)

Другое дело: вы пишете парсер; вы собрали несколько символов в char[], и вам нужно сделать String из них. Поскольку строка, вероятно, является общей и может использоваться совместно, мы хотели бы использовать пул.

String.intern() использует такой пул; но для поиска вам понадобится String. Поэтому нам нужно new String(char[],offset,length) первый.

Мы можем избежать этих накладных расходов в пользовательском пуле, где поиск может выполняться непосредственно на основе char[],offset,length, Например, пул является Trie , Строка, скорее всего, находится в пуле, поэтому мы получим строку без выделения памяти.

Если мы не хотим писать собственный пул, но используем старый добрый HashMap, нам все равно нужно создать ключевой объект, который обертывает char[],offset,length (что-то вроде CharSequence). Это еще дешевле, чем новая строка, поскольку мы не копируем символы.


2



Я всегда буду идти с Картой, потому что intern()  имеет  для выполнения (возможно, линейного) поиска во внутреннем пуле строк String. Если вы делаете это довольно часто, это не так эффективно, как Map-Map для быстрого поиска.


1



каковы преимущества и недостатки ручного управления классом, подобным имени, с использованием intern ()

Проверка типов является серьезной проблемой, но инвариантное сохранение  также вызывает серьезную озабоченность.

Добавление простой проверки на Name конструктор

Name(String s) {
  if (!isValidName(s)) { throw new IllegalArgumentException(s); }
  ...
}

может гарантировать *, что нет Name экземпляры, соответствующие недопустимым именам, например "12#blue,," что означает, что методы, которые принимают Names как аргументы и которые потребляют Names, возвращенные другими методами, не нужно беспокоиться о том, где недействителен Nameможет закрасться.

Чтобы обобщить этот аргумент, представьте, что ваш код - это замок со стенами, предназначенный для защиты от недействительных входов. Вы хотите, чтобы некоторые входы прошли, чтобы вы устанавливали ворота с охранниками, которые проверяют входные данные по мере их прохождения. Name конструктор - пример охранника.

Разница между String а также Name в том, что Strings не может быть защищен. Любая часть кода, злонамеренная или наивная, внутри или вне периметра, может создавать любое строковое значение. детская коляска String код манипуляции аналогичен зомби-вспышке внутри замка. Охранники не могут защитить инвариантов, потому что зомби не должны проходить мимо них. Зомби просто распространяют и коррумпируют данные по мере их поступления.

То, что значение "является" String удовлетворяет меньшим количеством полезных инвариантов, чем значение "является" Name,

Видеть строгий ввод  для другого способа взглянуть на ту же тему.

* - обычная оговорка о десериализации Serializable позволяя обход конструктора.


1



String.intern () в Java 5.0 и 6 использует пространство perm gen, которое обычно имеет низкий максимальный размер. Это может означать, что вам не хватает места, хотя есть много свободной кучи.

Java 7 использует свою обычную кучу для хранения intern () ed Strings.

Сравнение строк довольно быстро, и я не думаю, что есть много преимуществ в сокращении времени сравнения, когда вы рассматриваете накладные расходы.

Другая причина, по которой это может быть сделано, - это много повторяющихся строк. Если есть достаточное дублирование, это может сэкономить массу памяти.

Более простой способ кэширования строк - использовать кеш LRU, например LinkedHashMap

private static final int MAX_SIZE = 10000;
private static final Map<String, String> STRING_CACHE = new LinkedHashMap<String, String>(MAX_SIZE*10/7, 0.70f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > 10000;
    }
};

public static String intern(String s) {
    // s2 is a String equals to s, or null if its not there.
    String s2 = STRING_CACHE.get(s);
    if (s2 == null) {
        // put the string in the map if its not there already.
        s2 = s;
        STRING_CACHE.put(s2,s2);
    }
    return s2;
}

Вот пример того, как это работает.

public static void main(String... args) {
    String lo = "lo";
    for (int i = 0; i < 10; i++) {
        String a = "hel" + lo + " " + (i & 1);
        String b = intern(a);
        System.out.println("String \"" + a + "\" has an id of "
                + Integer.toHexString(System.identityHashCode(a))
                + " after interning is has an id of "
                + Integer.toHexString(System.identityHashCode(b))
        );
    }
    System.out.println("The cache contains "+STRING_CACHE);
}

печать

String "hello 0" has an id of 237360be after interning is has an id of 237360be
String "hello 1" has an id of 5736ab79 after interning is has an id of 5736ab79
String "hello 0" has an id of 38b72ce1 after interning is has an id of 237360be
String "hello 1" has an id of 64a06824 after interning is has an id of 5736ab79
String "hello 0" has an id of 115d533d after interning is has an id of 237360be
String "hello 1" has an id of 603d2b3 after interning is has an id of 5736ab79
String "hello 0" has an id of 64fde8da after interning is has an id of 237360be
String "hello 1" has an id of 59c27402 after interning is has an id of 5736ab79
String "hello 0" has an id of 6d4e5d57 after interning is has an id of 237360be
String "hello 1" has an id of 2a36bb87 after interning is has an id of 5736ab79
The cache contains {hello 0=hello 0, hello 1=hello 1}

Это гарантирует, что кеш intern () ed Strings будет ограничен числом.

Более быстрый, но менее эффективный способ - использовать фиксированный массив.

private static final int MAX_SIZE = 10191;
private static final String[] STRING_CACHE = new String[MAX_SIZE];

public static String intern(String s) {
    int hash = (s.hashCode() & 0x7FFFFFFF) % MAX_SIZE;
    String s2 = STRING_CACHE[hash];
    if (!s.equals(s2))
        STRING_CACHE[hash] = s2 = s;
    return s2;
}

Тест выше работает одинаково, за исключением того, что вам нужно

System.out.println("The cache contains "+ new HashSet<String>(Arrays.asList(STRING_CACHE)));

распечатать содержимое, которое показывает следующее: nullдля пустых записей.

The cache contains [null, hello 1, hello 0]

Преимуществом этого подхода является скорость и что его можно безопасно использовать несколькими потоками без блокировки. то есть не имеет значения, имеют ли разные потоки разные виды STRING_CACHE.


1



Итак, каковы преимущества и недостатки ручного управления   Класс, подобный имени, с использованием intern ()?

Одно из преимуществ:

Из этого следует, что для любых двух строк s и t s.intern () == t.intern ()   истинно тогда и только тогда, когда s.equals (t) истинно.

В программе, где часто нужно сравнивать много маленьких струн, это может окупиться. Кроме того, это экономит место в конце. Рассмотрим исходную программу, которая использует имена типа AbstractSyntaxTreeNodeItemFactorySerializer довольно часто. С помощью intern () эта строка будет храниться один раз, и это все. Все остальное, если только ссылки на это, но ссылки у вас есть в любом случае.


0