不区分大小写的字符串作为HashMap键

出于以下原因，我想使用不区分大小写的字符串作为HashMap键。

  • 在初始化过程中，我的程序用用户定义的字符串创建HashMap
  • 在处理一个事件(在我的情况下是网络流量)时，我可能会在不同的情况下收到字符串，但我应该能够从HashMap中定位<key, value>，忽略我从流量中收到的情况。

我采用了这种方法

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

因此，我为每个事件创建了CaseInsensitiveString的新对象。因此，它可能会影响性能。

有没有其他办法解决这个问题?

169649 次浏览
小开

子类HashMap并创建一个在put和get(可能还有其他面向键的方法)上小写键的版本。

或者将HashMap组合到新类中，并将所有内容委托给映射，但转换键。

如果需要保留原始键，可以维护双映射，或者将原始键与值一起存储。

小开

我想到了两个选择:

  1. 你可以直接使用s.toUpperCase().hashCode();作为Map的键。
  2. 你可以使用TreeMap<String>和自定义的Comparator来忽略大小写。

否则，如果您更喜欢自己的解决方案，我宁愿不定义一种新的String，而是实现一个具有所需的大小写不敏感功能的新Map。

小开

一种方法是创建Apache Commons AbstractHashedMap类的自定义子类，覆盖hash和isEqualKeys方法来执行不区分大小写的散列和键的比较。(注:我自己从来没有试过……)

这避免了每次需要执行映射查找或更新时创建新对象的开销。常见的Map操作应该O(1)…就像一个普通的HashMap。

如果你准备接受他们所做的实现选择，Apache Commons CaseInsensitiveMap会为你定制/专门化AbstractHashedMap。

但如果O(logN) get和put操作是可接受的，则可以选择带有不区分大小写的字符串比较器的TreeMap;例如使用String.CASE_INSENSITIVE_ORDER。

如果你不介意每次执行put或get时创建一个新的临时String对象，那么Vishal的答案就很好。(不过，我注意到，如果你这样做，你就不会保留键的原始大小写…)

小开

正如Guido García在他们的答案是中所建议的:

import java.util.HashMap;


public class CaseInsensitiveMap extends HashMap<String, String> {


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

或

https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/map/CaseInsensitiveMap.html

小开

为了记住hashCode，“包装”字符串不是更好吗?在普通的String类中，hashCode()第一次是O(N)，然后是O(1)，因为它是为将来使用而保留的。

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.
}

这将允许您在java中使用哈希表的任何实现，并具有O(1) hasCode()。

小开

根据其他答案，基本上有两种方法:子类化HashMap或包装String。第一个需要多做一些工作。事实上，如果你想正确地做它，你必须重写几乎所有的方法(containsKey, entrySet, get, put, putAll and remove)。

不管怎样，它有一个问题。如果你想避免未来的问题，你必须在String大小写操作中指定Locale。因此，您将创建新方法(get(String, Locale)，…)。一切都更简单，更清晰的包装字符串:

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
}

好吧，关于你对性能的担忧:过早的优化是万恶之源:)

小开 
Map<String, String> nodeMap =
new TreeMap<>(String.CASE_INSENSITIVE_ORDER);

这就是你所需要的。

小开

你可以从Eclipse集合中使用基于Map的HashingStrategy

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

注意:我是Eclipse Collections的贡献者。

小开

这是我为最近的一个项目实现的HashMaps适配器。工作方式类似于@SandyR，但封装了转换逻辑，因此您不必手动将字符串转换为包装器对象。

我使用了Java 8的特性，但是做了一些更改，您可以使它适应以前的版本。除了新的Java 8流函数之外，我对大多数常见场景进行了测试。

基本上，它包装了一个HashMap，将所有函数指向它，同时将字符串转换为包装器对象。但是我还必须调整KeySet和EntrySet，因为它们将一些函数转发给映射本身。因此，我返回两个用于键和项的新set，它们实际上包装了原始的keySet()和entrySet()。

注意:Java 8已经改变了putAll方法的实现，我无法找到一种简单的方法来覆盖它。因此，当前的实现可能会降低性能，特别是在对大型数据集使用putAll()时。

请让我知道，如果你发现一个错误或有改进代码的建议。

包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<T> implements Map<String,T>
{
private Map<CaseInsensitiveMapKey,T> map;
private KeySet keySet;
private EntrySet entrySet;




public CaseInsensitiveMapAdapter()
{
}


public CaseInsensitiveMapAdapter(Map<String, T> 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<String> keySet()
{
if (keySet == null)
keySet = new KeySet(getMap().keySet());
return keySet;
}


@Override
public Collection<T> values()
{
return getMap().values();
}


@Override
public Set<Entry<String, T>> 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<CaseInsensitiveMapKey, T>()
{
@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<CaseInsensitiveMapKey, T, T>()
{
@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<CaseInsensitiveMapKey, T>()
{
@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<CaseInsensitiveMapKey, T, T>()
{
@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<CaseInsensitiveMapKey, T, T>()
{
@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<CaseInsensitiveMapKey,T> getMapImplementation() {
return new HashMap<>();
}


private Map<CaseInsensitiveMapKey,T> 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<String> {


private Set<CaseInsensitiveMapKey> wrapped;


public KeySet(Set<CaseInsensitiveMapKey> wrapped)
{
this.wrapped = wrapped;
}




private List<String> keyList() {
return stream().collect(Collectors.toList());
}


private Collection<CaseInsensitiveMapKey> 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<String> iterator()
{
return keyList().iterator();
}


@Override
public Object[] toArray()
{
return keyList().toArray();
}


@Override
public <T> 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<String> spliterator()
{
return keyList().spliterator();
}


@Override
public boolean removeIf(Predicate<? super String> filter)
{
return wrapped.removeIf(new Predicate<CaseInsensitiveMapKey>()
{
@Override
public boolean test(CaseInsensitiveMapKey lookupKey)
{
return filter.test(lookupKey.key);
}
});
}


@Override
public Stream<String> stream()
{
return wrapped.stream().map(it -> it.key);
}


@Override
public Stream<String> parallelStream()
{
return wrapped.stream().map(it -> it.key).parallel();
}


@Override
public void forEach(Consumer<? super String> action)
{
wrapped.forEach(new Consumer<CaseInsensitiveMapKey>()
{
@Override
public void accept(CaseInsensitiveMapKey lookupKey)
{
action.accept(lookupKey.key);
}
});
}
}


private class EntrySet implements Set<Map.Entry<String,T>> {


private Set<Entry<CaseInsensitiveMapKey,T>> wrapped;


public EntrySet(Set<Entry<CaseInsensitiveMapKey,T>> wrapped)
{
this.wrapped = wrapped;
}




private List<Map.Entry<String,T>> keyList() {
return stream().collect(Collectors.toList());
}


private Collection<Entry<CaseInsensitiveMapKey,T>> mapCollection(Collection<?> c) {
return c.stream().map(it -> new CaseInsensitiveEntryAdapter((Entry<String,T>)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<Map.Entry<String,T>> iterator()
{
return keyList().iterator();
}


@Override
public Object[] toArray()
{
return keyList().toArray();
}


@Override
public <T> T[] toArray(T[] a)
{
return keyList().toArray(a);
}


@Override
public boolean add(Entry<String,T> 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<String,T>> 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<Entry<String,T>> spliterator()
{
return keyList().spliterator();
}


@Override
public boolean removeIf(Predicate<? super Entry<String, T>> filter)
{
return wrapped.removeIf(new Predicate<Entry<CaseInsensitiveMapKey, T>>()
{
@Override
public boolean test(Entry<CaseInsensitiveMapKey, T> entry)
{
return filter.test(new FromCaseInsensitiveEntryAdapter(entry));
}
});
}


@Override
public Stream<Entry<String,T>> stream()
{
return wrapped.stream().map(it -> new Entry<String, T>()
{
@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<Map.Entry<String,T>> parallelStream()
{
return StreamSupport.stream(spliterator(), true);
}


@Override
public void forEach(Consumer<? super Entry<String, T>> action)
{
wrapped.forEach(new Consumer<Entry<CaseInsensitiveMapKey, T>>()
{
@Override
public void accept(Entry<CaseInsensitiveMapKey, T> entry)
{
action.accept(new FromCaseInsensitiveEntryAdapter(entry));
}
});
}
}


private class EntryAdapter implements Map.Entry<String,T> {
private Entry<String,T> wrapped;


public EntryAdapter(Entry<String, T> 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<CaseInsensitiveMapKey,T> {


private Entry<String,T> wrapped;


public CaseInsensitiveEntryAdapter(Entry<String, T> 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<String,T> {


private Entry<CaseInsensitiveMapKey,T> wrapped;


public FromCaseInsensitiveEntryAdapter(Entry<CaseInsensitiveMapKey, T> 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);
}
}




}
小开

因此，我为每个事件创建了CaseInsensitiveString的新对象。因此，它可能会影响性能。

创建包装器或在查找前将键转换为小写都会创建新对象。编写自己的java.util.Map实现是避免这种情况的唯一方法。这并不难，而且在我看来是值得的。我发现下面的哈希函数工作得很好，最多几百个键。

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

我喜欢使用ICU4J的CaseInsensitiveString包装Map键，因为它照顾哈希\等于和问题，它适用于unicode\i18n。

HashMap<CaseInsensitiveString, String> caseInsensitiveMap = new HashMap<>();
caseInsensitiveMap.put("tschüß", "bye");
caseInsensitiveMap.containsKey("TSCHÜSS"); # true
小开

而不是创建自己的类来验证和存储大小写不敏感的字符串作为HashMap键，你可以使用:

  1. LinkedCaseInsensitiveMap包装了一个LinkedHashMap，它是一个基于哈希表和链表的Map。与LinkedHashMap不同，它不允许插入空键。LinkedCaseInsensitiveMap保留了键的原始顺序和原始大小写，同时允许使用任何大小写调用get和remove等函数。

例如:

Map<String, Integer> linkedHashMap = new LinkedCaseInsensitiveMap<>();
linkedHashMap.put("abc", 1);
linkedHashMap.put("AbC", 2);


System.out.println(linkedHashMap);

输出:AbC = {2}

Mvn依赖性:

Spring Core是一个Spring框架模块，它还提供实用工具类，包括LinkedCaseInsensitiveMap。

<dependency>
<groupId>org.springframework</groupId>
<artifactId>spring-core</artifactId>
<version>5.2.5.RELEASE</version>
</dependency>
  1. CaseInsensitiveMap是一个基于哈希的Map，它在添加或检索键之前将键转换为小写。与TreeMap不同，CaseInsensitiveMap允许插入空键。

例如:

Map<String, Integer> commonsHashMap = new CaseInsensitiveMap<>();
commonsHashMap.put("ABC", 1);
commonsHashMap.put("abc", 2);
commonsHashMap.put("aBc", 3);


System.out.println(commonsHashMap);

输出:abc = {3}

依赖:

<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-collections4</artifactId>
<version>4.4</version>
</dependency>
  1. TreeMap是NavigableMap的实现，这意味着它总是在插入条目后根据给定的比较器对条目进行排序。此外，TreeMap使用Comparator来查找插入的键是重复的还是新的。

因此，如果我们提供一个不区分大小写的String Comparator，我们将得到一个不区分大小写的TreeMap。

例如:

Map<String, Integer> treeMap = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
treeMap.put("ABC", 1);
treeMap.put("ABc", 2);
treeMap.put("cde", 1);
        

System.out.println(treeMap);

输出:{ABC=2, cde=1}

小开

你可以使用CollationKey对象来代替字符串:

Locale locale = ...;
Collator collator = Collator.getInstance(locale);
collator.setStrength(Collator.SECONDARY); // Case-insensitive.
collator.setDecomposition(Collator.FULL_DECOMPOSITION);


CollationKey collationKey = collator.getCollationKey(stringKey);
hashMap.put(collationKey, value);
hashMap.get(collationKey);

使用Collator.PRIMARY忽略重音差异。

CollationKey API并不保证实现了hashCode()和equals()，但实际上你将使用RuleBasedCollationKey，它实现了这些。如果你很偏执，你可以使用TreeMap代替，它保证以O(log n)时间而不是O(1)的代价工作。

小开

我发现需要你改变键的解决方案(例如，toLowerCase)非常不受欢迎，需要TreeMap的解决方案也不受欢迎。

由于TreeMap改变了时间复杂度(与其他__abc1相比)，我认为简单地使用O(n)的实用方法更可行:

public static <T> T getIgnoreCase(Map<String, T> map, String key) {
for(Entry<String, T> entry : map.entrySet()) {
if(entry.getKey().equalsIgnoreCase(key))
return entry.getValue();
}
return null;
}

这就是那个方法。由于牺牲性能(时间复杂度)看起来是不可避免的，至少不需要更改底层映射以适应查找。


提交答案