Optimiser l'utilisation de la mémoire d'une collection de chaînes en Java

Question

J'ai un grand nombre de paires nom-valeur (environ 100k) que je dois stocker dans une sorte de cache (disons une carte de hachage) où la valeur est une chaîne avec une taille moyenne d'environ 30 000 octets.

Maintenant, je sais pertinemment qu'un grand nombre de valeurs ont exactement les mêmes données de chaîne. Afin d'éviter d'avoir à allouer plusieurs fois les mêmes chaînes de caractères, j'aimerais réutiliser une chaîne précédemment allouée et donc consommer moins de mémoire. En outre, cela doit être raisonnablement rapide. c'est-à-dire que le balayage de toutes les valeurs précédemment attribuées, une par une, n'est pas une option.

Des recommandations sur la façon dont je pourrais résoudre ce problème?

Answer 1

Ne pas utilisation String.intern (il y a eu divers problèmes de mémoire liés à ce fil des années). à la place, créez votre propre cache, similaire à String.intern. Fondamentalement, vous voulez une carte, où chaque clé correspond à elle-même. puis, avant la mise en cache une chaîne, vous « stagiaire » il:

private Map<String,WeakReference<String>> myInternMap = new WeakHashMap<String,,WeakReference<String>>(); 
public String intern(String value) { 
    synchronized(myInternMap) { 
    WeakReference<String> curRef = myInternMap.get(value); 
    String curValue = ((curRef != null) ? curRef.get() : null); 
    if(curValue != null) { 
     return curValue; 
    } 

    myInternMap.put(value, new WeakReference<String>(value)); 
    return value; 
    } 
} 

note, vous utilisez WeakReferences pour les clés et valeurs afin que vous ne gardez pas les références pour les chaînes que vous ne l'utilisez plus.

Answer 2

String.intern() vous aidera ici (probablement). Il résoudra plusieurs instances du même chaîne jusqu'à une copie.

EDIT: J'ai suggéré que cela aiderait «le plus probable». Dans quels scénarios ne le sera-t-il pas? Les chaînes d'internement auront pour effet de stocker les représentations de chaînes internées en permanence. Si le problème est un processus ponctuel, cela peut ne pas poser de problème. S'il s'agit d'un processus de longue durée (comme une application Web), vous risquez d'avoir un problème.

Je hésite à dire jamais usage interner (je hesistate dire ne rien faire). Cependant, il existe des scénarios où ce n'est pas idéal.

Answer 3

String.intern est le choix évident comme le dit Brian. Mais si vous ne voulez pas internaliser toute la chaîne en mémoire, vous pouvez utiliser un ensemble pour voir d'abord si la valeur est présente. Voici du code non testé. Vous devrez travailler sur la suppression de la carte inversée lors du retrait de la principale

class Map2<K, V> implements Map<K, V> 
    { 
    Map<K, V> _map = Maps.newHashMap(); 
    Set<V, V> _rev = Maps.newHashMap(); 

    V put(K k, V v) { 
     if (_rev.containsKey(v)) { 
     V prev = _rev.get(v); 
     return _map.put(k, prev); 
     } else { 
     _rev.put(v, v); 
     return _map.put(k,v); 
     } 
    } 

Answer 4

Cela dépend en quelque sorte de la façon dont vous créez le String.

Une possibilité est d'utiliser TreeSet qui utilise un Comparator qui peut se comparer existant String s et la source de votre nouvelle String. Utilisez SortedSet.tailSet et Iterator pour trouver un String existant. Ou alternativement NavigableSet.ceiling/floor ou un avec une configuration similaire.

J'ai écrit un weblog entry sur une autre technique pour mettre en cache des objets immuables (en particulier des chaînes de caractères), mais cela est plus approprié pour les objets plus petits.

String.intern a des problèmes de performances.

Answer 5

D'accord avec d'autres pour ne pas utiliser String.intern(): une fois que vous avez placé une chaîne, elle ne disparaîtra jamais.Regardez les premières révisions de Xerces pour savoir pourquoi c'est une mauvaise idée.

Une meilleure solution est d'utiliser un WeakHashMap, enveloppant la valeur dans une WeakReference:

private Map<String,WeakReference<String>> _map 
    = new WeakHashMap<String,WeakReference<String>>(); 

public synchronized String intern(String str) 
{ 
    WeakReference<String> ref = _map.get(str); 
    String s2 = (ref != null) ? ref.get() : null; 
    if (s2 != null) 
     return s2; 
    str = new String(str); 
    _map.put(str, new WeakReference(str)); 
    return str; 
} 

Ce code est d'un article that I wrote sur les objets de référence Java. Vous trouverez l'explication ici.

EDIT: besoin de créer une nouvelle chaîne ici (et je mettrai à jour l'article) parce que l'original pourrait être une sous-chaîne d'un tableau de caractères beaucoup plus grand. Je pensais que c'était corrigé autour de JDK 1.3, mais apparemment pas (du moins pas dans 1.5).

Answer 6

Vous pouvez compresser les chaînes. Une chaîne de 30K devrait avoir un bon taux de compression. J'ai écrit un hack pour compresser une grande chaîne comme un exercice, mais vous pouvez utiliser un octet [] des données compressées pour stocker la chaîne.

Une chaîne de caractères de 30 Ko utilisera environ 60 Ko (2 octets par caractère), donc même l'utilisation de getBytes() est susceptible d'être une amélioration.

Answer 7

Est-ce que vous avez réellement besoin Strings, ou avez-vous juste besoin d'une vieille CharSequence? Si ce n'est pas le cas, pensez à implémenter un "compact" CharSequence tel que celui que je suggère dans le lien.