Maiuscole / minuscole stringa come chiave HashMap

Vorrei utilizzare la stringa senza distinzione tra maiuscole e minuscole come una chiave HashMap per i seguenti motivi.

  • Durante l’inizializzazione, il mio programma crea HashMap con String definito dall’utente
  • Durante l’elaborazione di un evento (traffico di rete nel mio caso), potrei ricevere String in un caso diverso, ma dovrei essere in grado di individuare la da HashMap ignorando il caso ricevuto dal traffico.

Ho seguito questo approccio

CaseInsensitiveString.java

  public final class CaseInsensitiveString { private String s; public CaseInsensitiveString(String s) { if (s == null) throw new NullPointerException(); this.s = s; } public boolean equals(Object o) { return o instanceof CaseInsensitiveString && ((CaseInsensitiveString)o).s.equalsIgnoreCase(s); } private volatile int hashCode = 0; public int hashCode() { if (hashCode == 0) hashCode = s.toUpperCase().hashCode(); return hashCode; } public String toString() { return s; } } 

LookupCode.java

  node = nodeMap.get(new CaseInsensitiveString(stringFromEvent.toString())); 

Per questo motivo, sto creando un nuovo object di CaseInsensitiveString per ogni evento. Quindi, potrebbe colpire le prestazioni.

C’è un altro modo per risolvere questo problema?

 Map nodeMap = new TreeMap(String.CASE_INSENSITIVE_ORDER); 

Questo è davvero tutto ciò di cui hai bisogno.

Come suggerito da Guido García nella loro risposta qui :

 import java.util.HashMap; public class CaseInsensitiveMap extends HashMap { @Override public String put(String key, String value) { return super.put(key.toLowerCase(), value); } // not @Override because that would require the key parameter to be of type Object public String get(String key) { return super.get(key.toLowerCase()); } } 

O

http://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/map/CaseInsensitiveMap.html

Un approccio consiste nel creare una sottoclass personalizzata della class AbstractHashedMap Apache Commons, sovrascrivendo i metodi hash e isEqualKeys per eseguire l’hashing insensibile alle maiuscole e il confronto delle chiavi. (Nota: non l’ho mai provato da solo …)

Ciò evita il sovraccarico di creazione di nuovi oggetti ogni volta che è necessario eseguire una ricerca o un aggiornamento della mappa. E le operazioni comuni sulla Map dovrebbero essere O (1) … proprio come una normale HashMap .

E se sei pronto ad accettare le scelte di implementazione che hanno fatto, Apache Commons CaseInsensitiveMap fa il lavoro di personalizzazione / specializzazione di AbstractHashedMap per te.


Ma se O (logN) get e put operazioni sono accettabili, una TreeMap con un comparatore di stringa senza TreeMap tra maiuscole e minuscole è un’opzione; ad es. usando String.CASE_INSENSITIVE_ORDER .

E se non ti dispiace creare un nuovo object String temporaneo ogni volta che fai un put o get , allora la risposta di Vishal va bene. (Anche se, noto che non avresti conservato la custodia originale dei tasti se l’avessi fatto …)

Sottoclassi HashMap e crea una versione che HashMap la chiave su put e get (e probabilmente sugli altri metodi orientati alla chiave).

Oppure HashMap una HashMap nella nuova class e deleghi tutto alla mappa, ma traduci le chiavi.

Se è necessario mantenere la chiave originale, è ansible mantenere due mappe o memorizzare la chiave originale insieme al valore.

Non sarebbe meglio “avvolgere” la stringa per memorizzare l’hashCode. Nella normale class String hashCode () è O (N) la prima volta e quindi è O (1) poiché è conservato per uso futuro.

 public class HashWrap { private final String value; private final int hash; public String get() { return value; } public HashWrap(String value) { this.value = value; String lc = value.toLowerCase(); this.hash = lc.hashCode(); } @Override public boolean equals(Object o) { if (this == o) return true; if (o instanceof HashWrap) { HashWrap that = (HashWrap) o; return value.equalsIgnoreCase(that.value); } else { return false; } } @Override public int hashCode() { return this.hash; } //might want to implement compare too if you want to use with SortedMaps/Sets. } 

Ciò consentirebbe di utilizzare qualsiasi implementazione di Hashtable in java e di avere O (1) hasCode ().

Puoi utilizzare una mappa basata su HashingStrategy dalle raccolte di Eclipse

 HashingStrategy hashingStrategy = HashingStrategies.fromFunction(String::toUpperCase); MutableMap node = HashingStrategyMaps.mutable.of(hashingStrategy); 

Nota: sono un collaboratore di Eclipse Collections.

Mi vengono in mente due scelte:

  1. È ansible utilizzare direttamente s.toUpperCase().hashCode(); come chiave della Map .
  2. È ansible utilizzare una TreeMap con un Comparator personalizzato che ignori il caso.

Altrimenti, se preferisci la tua soluzione, invece di definire un nuovo tipo di stringa, preferirei implementare una nuova mappa con la funzionalità di insensibilità del caso richiesta.

Sulla base di altre risposte, ci sono fondamentalmente due approcci: sottoclass HashMap o wrapping String . Il primo richiede un po ‘più di lavoro. Infatti, se si vuole farlo correttamente, è necessario sovrascrivere quasi tutti i metodi ( containsKey, entrySet, get, put, putAll and remove ).

Ad ogni modo, ha un problema. Se si desidera evitare problemi futuri, è necessario specificare un locale nelle operazioni caso di String . Quindi dovresti creare nuovi metodi ( get(String, Locale) , …). Tutto è più semplice e più trasparente. Stringa:

 public final class CaseInsensitiveString { private final String s; public CaseInsensitiveString(String s, Locale locale) { this.s = s.toUpperCase(locale); } // equals, hashCode & toString, no need for memoizing hashCode } 

E bene, riguardo alle tue preoccupazioni per le prestazioni: l’ottimizzazione prematura è la radice di tutto il male 🙂

Per una solida implementazione CaseInsensitiveMap / CaseInsensitiveSet, controlla java-util ( https://github.com/jdereg/java-util ).

Queste mappe eseguono il tempo di ricerca standard O (1), conservano il caso degli elementi aggiunti, supportano tutte le API Map come putAll (), retainAll (), removeAll () e consentono di inserire elementi eterogenei nel set di chiavi.

Inoltre, java.util.Set restituito da .keySet () e .entrySet () rende insensibilità alle maiuscole / minuscole (molte implementazioni non lo fanno). Infine, se si recupera la chiave dal set di chiavi / voci durante l’iterazione, si ottiene una stringa indietro, non una class wrapper CaseInsensitiveString.

Questo è un adattatore per HashMaps che ho implementato per un progetto recente. Funziona in un modo simile a quello che fa @SandyR, ma incapsula la logica di conversione in modo da non convertire manualmente le stringhe in un object wrapper.

Ho usato le funzionalità di Java 8 ma con alcune modifiche, è ansible adattarlo alle versioni precedenti. L’ho provato per gli scenari più comuni, ad eccezione delle nuove funzioni di streaming di Java 8.

Fondamentalmente avvolge una HashMap, ne indirizza tutte le funzioni durante la conversione di stringhe da / verso un object wrapper. Ma ho dovuto adattare anche KeySet e EntrySet perché inoltrano alcune funzioni alla mappa stessa. Così restituisco due nuovi Set per chiavi e voci che racchiudono in realtà i tasti keySet () e entrySet ().

Una nota: Java 8 ha cambiato l’implementazione del metodo putAll che non ho trovato un modo semplice per eseguire l’override. Pertanto, l’implementazione corrente potrebbe avere prestazioni ridotte, specialmente se si utilizza putAll () per un set di dati di grandi dimensioni.

Per favore fatemi sapere se trovate un bug o avete suggerimenti per migliorare il codice.

pacchetto webbit.collections;

 import java.util.*; import java.util.function.*; import java.util.stream.Collectors; import java.util.stream.Stream; import java.util.stream.StreamSupport; public class CaseInsensitiveMapAdapter implements Map { private Map map; private KeySet keySet; private EntrySet entrySet; public CaseInsensitiveMapAdapter() { } public CaseInsensitiveMapAdapter(Map map) { this.map = getMapImplementation(); this.putAll(map); } @Override public int size() { return getMap().size(); } @Override public boolean isEmpty() { return getMap().isEmpty(); } @Override public boolean containsKey(Object key) { return getMap().containsKey(lookupKey(key)); } @Override public boolean containsValue(Object value) { return getMap().containsValue(value); } @Override public T get(Object key) { return getMap().get(lookupKey(key)); } @Override public T put(String key, T value) { return getMap().put(lookupKey(key), value); } @Override public T remove(Object key) { return getMap().remove(lookupKey(key)); } /*** * I completely ignore Java 8 implementation and put one by one.This will be slower. */ @Override public void putAll(Map< ? extends String, ? extends T> m) { for (String key : m.keySet()) { getMap().put(lookupKey(key),m.get(key)); } } @Override public void clear() { getMap().clear(); } @Override public Set keySet() { if (keySet == null) keySet = new KeySet(getMap().keySet()); return keySet; } @Override public Collection values() { return getMap().values(); } @Override public Set> entrySet() { if (entrySet == null) entrySet = new EntrySet(getMap().entrySet()); return entrySet; } @Override public boolean equals(Object o) { return getMap().equals(o); } @Override public int hashCode() { return getMap().hashCode(); } @Override public T getOrDefault(Object key, T defaultValue) { return getMap().getOrDefault(lookupKey(key), defaultValue); } @Override public void forEach(final BiConsumer< ? super String, ? super T> action) { getMap().forEach(new BiConsumer() { @Override public void accept(CaseInsensitiveMapKey lookupKey, T t) { action.accept(lookupKey.key,t); } }); } @Override public void replaceAll(final BiFunction< ? super String, ? super T, ? extends T> function) { getMap().replaceAll(new BiFunction() { @Override public T apply(CaseInsensitiveMapKey lookupKey, T t) { return function.apply(lookupKey.key,t); } }); } @Override public T putIfAbsent(String key, T value) { return getMap().putIfAbsent(lookupKey(key), value); } @Override public boolean remove(Object key, Object value) { return getMap().remove(lookupKey(key), value); } @Override public boolean replace(String key, T oldValue, T newValue) { return getMap().replace(lookupKey(key), oldValue, newValue); } @Override public T replace(String key, T value) { return getMap().replace(lookupKey(key), value); } @Override public T computeIfAbsent(String key, final Function< ? super String, ? extends T> mappingFunction) { return getMap().computeIfAbsent(lookupKey(key), new Function() { @Override public T apply(CaseInsensitiveMapKey lookupKey) { return mappingFunction.apply(lookupKey.key); } }); } @Override public T computeIfPresent(String key, final BiFunction< ? super String, ? super T, ? extends T> remappingFunction) { return getMap().computeIfPresent(lookupKey(key), new BiFunction() { @Override public T apply(CaseInsensitiveMapKey lookupKey, T t) { return remappingFunction.apply(lookupKey.key, t); } }); } @Override public T compute(String key, final BiFunction< ? super String, ? super T, ? extends T> remappingFunction) { return getMap().compute(lookupKey(key), new BiFunction() { @Override public T apply(CaseInsensitiveMapKey lookupKey, T t) { return remappingFunction.apply(lookupKey.key,t); } }); } @Override public T merge(String key, T value, BiFunction< ? super T, ? super T, ? extends T> remappingFunction) { return getMap().merge(lookupKey(key), value, remappingFunction); } protected Map getMapImplementation() { return new HashMap<>(); } private Map getMap() { if (map == null) map = getMapImplementation(); return map; } private CaseInsensitiveMapKey lookupKey(Object key) { return new CaseInsensitiveMapKey((String)key); } public class CaseInsensitiveMapKey { private String key; private String lookupKey; public CaseInsensitiveMapKey(String key) { this.key = key; this.lookupKey = key.toUpperCase(); } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; CaseInsensitiveMapKey that = (CaseInsensitiveMapKey) o; return lookupKey.equals(that.lookupKey); } @Override public int hashCode() { return lookupKey.hashCode(); } } private class KeySet implements Set { private Set wrapped; public KeySet(Set wrapped) { this.wrapped = wrapped; } private List keyList() { return stream().collect(Collectors.toList()); } private Collection mapCollection(Collection< ?> c) { return c.stream().map(it -> lookupKey(it)).collect(Collectors.toList()); } @Override public int size() { return wrapped.size(); } @Override public boolean isEmpty() { return wrapped.isEmpty(); } @Override public boolean contains(Object o) { return wrapped.contains(lookupKey(o)); } @Override public Iterator iterator() { return keyList().iterator(); } @Override public Object[] toArray() { return keyList().toArray(); } @Override public  T[] toArray(T[] a) { return keyList().toArray(a); } @Override public boolean add(String s) { return wrapped.add(lookupKey(s)); } @Override public boolean remove(Object o) { return wrapped.remove(lookupKey(o)); } @Override public boolean containsAll(Collection< ?> c) { return keyList().containsAll(c); } @Override public boolean addAll(Collection< ? extends String> c) { return wrapped.addAll(mapCollection(c)); } @Override public boolean retainAll(Collection< ?> c) { return wrapped.retainAll(mapCollection(c)); } @Override public boolean removeAll(Collection< ?> c) { return wrapped.removeAll(mapCollection(c)); } @Override public void clear() { wrapped.clear(); } @Override public boolean equals(Object o) { return wrapped.equals(lookupKey(o)); } @Override public int hashCode() { return wrapped.hashCode(); } @Override public Spliterator spliterator() { return keyList().spliterator(); } @Override public boolean removeIf(Predicate< ? super String> filter) { return wrapped.removeIf(new Predicate() { @Override public boolean test(CaseInsensitiveMapKey lookupKey) { return filter.test(lookupKey.key); } }); } @Override public Stream stream() { return wrapped.stream().map(it -> it.key); } @Override public Stream parallelStream() { return wrapped.stream().map(it -> it.key).parallel(); } @Override public void forEach(Consumer< ? super String> action) { wrapped.forEach(new Consumer() { @Override public void accept(CaseInsensitiveMapKey lookupKey) { action.accept(lookupKey.key); } }); } } private class EntrySet implements Set> { private Set> wrapped; public EntrySet(Set> wrapped) { this.wrapped = wrapped; } private List> keyList() { return stream().collect(Collectors.toList()); } private Collection> mapCollection(Collection< ?> c) { return c.stream().map(it -> new CaseInsensitiveEntryAdapter((Entry)it)).collect(Collectors.toList()); } @Override public int size() { return wrapped.size(); } @Override public boolean isEmpty() { return wrapped.isEmpty(); } @Override public boolean contains(Object o) { return wrapped.contains(lookupKey(o)); } @Override public Iterator> iterator() { return keyList().iterator(); } @Override public Object[] toArray() { return keyList().toArray(); } @Override public  T[] toArray(T[] a) { return keyList().toArray(a); } @Override public boolean add(Entry s) { return wrapped.add(null ); } @Override public boolean remove(Object o) { return wrapped.remove(lookupKey(o)); } @Override public boolean containsAll(Collection< ?> c) { return keyList().containsAll(c); } @Override public boolean addAll(Collection< ? extends Entry> c) { return wrapped.addAll(mapCollection(c)); } @Override public boolean retainAll(Collection< ?> c) { return wrapped.retainAll(mapCollection(c)); } @Override public boolean removeAll(Collection< ?> c) { return wrapped.removeAll(mapCollection(c)); } @Override public void clear() { wrapped.clear(); } @Override public boolean equals(Object o) { return wrapped.equals(lookupKey(o)); } @Override public int hashCode() { return wrapped.hashCode(); } @Override public Spliterator> spliterator() { return keyList().spliterator(); } @Override public boolean removeIf(Predicate< ? super Entry> filter) { return wrapped.removeIf(new Predicate>() { @Override public boolean test(Entry entry) { return filter.test(new FromCaseInsensitiveEntryAdapter(entry)); } }); } @Override public Stream> stream() { return wrapped.stream().map(it -> new Entry() { @Override public String getKey() { return it.getKey().key; } @Override public T getValue() { return it.getValue(); } @Override public T setValue(T value) { return it.setValue(value); } }); } @Override public Stream> parallelStream() { return StreamSupport.stream(spliterator(), true); } @Override public void forEach(Consumer< ? super Entry> action) { wrapped.forEach(new Consumer>() { @Override public void accept(Entry entry) { action.accept(new FromCaseInsensitiveEntryAdapter(entry)); } }); } } private class EntryAdapter implements Map.Entry { private Entry wrapped; public EntryAdapter(Entry wrapped) { this.wrapped = wrapped; } @Override public String getKey() { return wrapped.getKey(); } @Override public T getValue() { return wrapped.getValue(); } @Override public T setValue(T value) { return wrapped.setValue(value); } @Override public boolean equals(Object o) { return wrapped.equals(o); } @Override public int hashCode() { return wrapped.hashCode(); } } private class CaseInsensitiveEntryAdapter implements Map.Entry { private Entry wrapped; public CaseInsensitiveEntryAdapter(Entry wrapped) { this.wrapped = wrapped; } @Override public CaseInsensitiveMapKey getKey() { return lookupKey(wrapped.getKey()); } @Override public T getValue() { return wrapped.getValue(); } @Override public T setValue(T value) { return wrapped.setValue(value); } } private class FromCaseInsensitiveEntryAdapter implements Map.Entry { private Entry wrapped; public FromCaseInsensitiveEntryAdapter(Entry wrapped) { this.wrapped = wrapped; } @Override public String getKey() { return wrapped.getKey().key; } @Override public T getValue() { return wrapped.getValue(); } @Override public T setValue(T value) { return wrapped.setValue(value); } } } 

Per questo motivo, sto creando un nuovo object di CaseInsensitiveString per ogni evento. Quindi, potrebbe colpire le prestazioni.

La creazione di wrapper o la conversione della chiave in lettere minuscole prima della ricerca creano entrambi nuovi oggetti. Scrivere la tua implementazione java.util.Map è l’unico modo per evitarlo. Non è troppo difficile, e IMO ne vale la pena. Ho trovato la seguente funzione di hash per funzionare abbastanza bene, fino a poche centinaia di chiavi.

 static int ciHashCode(String string) { // length and the low 5 bits of hashCode() are case insensitive return (string.hashCode() & 0x1f)*33 + string.length(); } 

Che ne dici di usare java 8 streams.

 nodeMap.entrySet().stream().filter(x->x.getKey().equalsIgnoreCase(stringfromEven.toString()).collect(Collectors.toList())