String insensível a maiúsculas e minúsculas como chave HashMap

Eu gostaria de usar a string case insensitive como uma chave HashMap pelos seguintes motivos.

  • Durante a boot, meu programa cria o HashMap com uma String definida pelo usuário
  • Ao processar um evento (tráfego de rede no meu caso), eu poderia receber String em um caso diferente, mas eu deveria ser capaz de localizar o do HashMap ignorando o caso que recebi do tráfego.

Eu segui essa abordagem

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())); 

Por causa disso, estou criando um novo object de CaseInsensitiveString para cada evento. Então, isso pode afetar o desempenho.

Existe alguma outra maneira de resolver este problema?

 Map nodeMap = new TreeMap(String.CASE_INSENSITIVE_ORDER); 

Isso é realmente tudo que você precisa.

Como sugerido por Guido García em sua resposta aqui :

 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()); } } 

Ou

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

Uma abordagem é criar uma subclass personalizada da class Apache Commons AbstractHashedMap , sobrescrevendo os methods hash e isEqualKeys para executar hashing e comparação de chaves sem isEqualKeys entre maiúsculas e minúsculas. (Nota – eu nunca tentei isso sozinho …)

Isso evita a sobrecarga de criar novos objects sempre que você precisar fazer uma pesquisa ou atualização de mapa. E as operações comuns do Map devem ser O (1) … como um HashMap comum.

E se você está preparado para aceitar as escolhas de implementação que eles fizeram, o Apache Commons CaseInsensitiveMap faz o trabalho de customizar / especializar o AbstractHashedMap para você.


Mas, se as operações O (logN) get e put forem aceitáveis, um TreeMap com um comparador de cadeia insensível a maiúsculas e minúsculas é uma opção; por exemplo, usando String.CASE_INSENSITIVE_ORDER .

E se você não se importa em criar um novo object temporário String cada vez que fizer um put ou get , então a resposta de Vishal é ótima. (Embora, eu note que você não estaria preservando o caso original das chaves, se você fez isso …)

Subclass HashMap e crie uma versão que abaixa a chave em put e get (e provavelmente os outros methods orientados a chave).

Ou HashMap um HashMap na nova class e delega tudo ao mapa, mas traduz as chaves.

Se você precisar manter a chave original, poderá manter mapas duplos ou armazenar a chave original junto com o valor.

Não seria melhor “embrulhar” o String para memorizar o hashCode. Na class String normal, hashCode () é O (N) na primeira vez e, em seguida, é O (1), uma vez que é mantido para 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. } 

Isso permitiria usar qualquer implementação de Hashtable em java e ter O (1) hasCode ().

Você pode usar um mapa baseado em HashingStrategy a partir de collections do Eclipse

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

Nota: Eu sou um colaborador do Eclipse Collections.

Duas escolhas vêm à minha mente:

  1. Você pode usar diretamente o s.toUpperCase().hashCode(); como a chave do Map .
  2. Você poderia usar um TreeMap com um Comparator personalizado que ignora o caso.

Caso contrário, se você preferir sua solução, em vez de definir um novo tipo de String, prefiro implementar um novo Map com a funcionalidade de insensibilidade de caso necessária.

Com base em outras respostas, existem basicamente duas abordagens: subsorting de HashMap ou quebra HashMap String . O primeiro requer um pouco mais de trabalho. De fato, se você quiser fazer isso corretamente, você deve sobrescrever quase todos os methods ( containsKey, entrySet, get, put, putAll and remove ).

De qualquer forma, isso tem um problema. Se você quiser evitar problemas futuros, deverá especificar uma Locale em operações de caso de String . Então você criaria novos methods ( get(String, Locale) , …). Tudo é mais fácil e mais claro quebra automática de string:

 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 bem, sobre suas preocupações com o desempenho: a otimização prematura é a raiz de todo o mal 🙂

Para uma implementação robusta de CaseInsensitiveMap / CaseInsensitiveSet, verifique o java-util ( https://github.com/jdereg/java-util ).

Esses Mapas são executados no tempo de pesquisa padrão O (1), retêm o caso dos itens adicionados, suportam todas as APIs de Mapa como putAll (), retainAll (), removeAll () e permitem que itens heterogêneos sejam colocados no conjunto de chaves.

Além disso, o java.util.Set retornado por .keySet () e .entrySet () honra a insensibilidade de maiúsculas e minúsculas (muitas implementações não). Por fim, se você buscar a chave da chave / input definida durante a iteração, receberá uma string de volta, não uma class de invólucro CaseInsensitiveString.

Este é um adaptador para HashMaps que eu implementei para um projeto recente. Funciona de uma maneira semelhante ao que o @SandyR faz, mas encapsula a lógica de conversão para que você não converta manualmente as strings em um object de wrapper.

Eu usei resources do Java 8, mas com algumas mudanças, você pode adaptá-lo às versões anteriores. Eu testei para os cenários mais comuns, exceto as novas funções de stream do Java 8.

Basicamente, ele envolve um HashMap, direciona todas as funções para ele enquanto converte strings de / para um object wrapper. Mas eu também tive que adaptar KeySet e EntrySet porque eles encaminham algumas funções para o próprio mapa. Então eu retornei dois novos conjuntos para chaves e inputs que realmente envolvem o keySet () e entrySet () original.

Uma nota: o Java 8 mudou a implementação do método putAll, que não consegui encontrar uma maneira fácil de replace. Portanto, a implementação atual pode ter degradado o desempenho, especialmente se você usar putAll () para um grande dataset.

Por favor, deixe-me saber se você encontrar um bug ou tiver sugestões para melhorar o código.

package 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 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 action) { getMap().forEach(new BiConsumer() { @Override public void accept(CaseInsensitiveMapKey lookupKey, T t) { action.accept(lookupKey.key,t); } }); } @Override public void replaceAll(final BiFunction 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 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 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 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 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 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 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 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> 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> 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> 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); } } } 

Por causa disso, estou criando um novo object de CaseInsensitiveString para cada evento. Então, isso pode afetar o desempenho.

Criar invólucros ou converter a chave em minúscula antes da pesquisa cria novos objects. Escrever sua própria implementação de java.util.Map é a única maneira de evitar isso. Não é muito difícil, e o IMO vale a pena. Eu encontrei a seguinte function hash para funcionar muito bem, até algumas centenas de chaves.

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

Que tal usar o java 8 streams.

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