Есть ли в Java HashMap с обратным поиском?
У меня есть данные, которые организованы в виде "ключ-ключ", а не "ключ-значение". Это похоже на HashMap, но мне понадобится поиск O(1) в обоих направлениях. Есть ли название для этого типа структуры данных, и есть ли что-нибудь подобное в стандартных библиотеках Java? (или, может быть, Apache Commons?)
Я мог бы написать свой собственный класс, который в основном использует две зеркальные карты, но я бы не стал изобретать велосипед (если он уже существует, но я просто не ищу правильный термин).
7 ответов
В Java API такого класса нет. Класс Apache Commons, который вы хотите, станет одной из реализаций BidiMap.
Как математик, я бы назвал такую структуру биекцией.
Вот простой класс, который я использовал, чтобы сделать это (я не хотел иметь еще одну стороннюю зависимость). Он не предлагает все функции, доступные в Картах, но это хорошее начало.
public class BidirectionalMap<KeyType, ValueType>{
private Map<KeyType, ValueType> keyToValueMap = new ConcurrentHashMap<KeyType, ValueType>();
private Map<ValueType, KeyType> valueToKeyMap = new ConcurrentHashMap<ValueType, KeyType>();
synchronized public void put(KeyType key, ValueType value){
keyToValueMap.put(key, value);
valueToKeyMap.put(value, key);
}
synchronized public ValueType removeByKey(KeyType key){
ValueType removedValue = keyToValueMap.remove(key);
valueToKeyMap.remove(removedValue);
return removedValue;
}
synchronized public KeyType removeByValue(ValueType value){
KeyType removedKey = valueToKeyMap.remove(value);
keyToValueMap.remove(removedKey);
return removedKey;
}
public boolean containsKey(KeyType key){
return keyToValueMap.containsKey(key);
}
public boolean containsValue(ValueType value){
return keyToValueMap.containsValue(value);
}
public KeyType getKey(ValueType value){
return valueToKeyMap.get(value);
}
public ValueType get(KeyType key){
return keyToValueMap.get(key);
}
}
Если столкновения не происходит, вы всегда можете добавить оба направления в один и тот же HashMap:-)
Вот мои 2 цента.
Или вы можете использовать простой метод с дженериками. Кусок пирога.
public static <K,V> Map<V, K> invertMap(Map<K, V> toInvert) {
Map<V, K> result = new HashMap<V, K>();
for(K k: toInvert.keySet()){
result.put(toInvert.get(k), k);
}
return result;
}
Конечно, вы должны иметь карту с уникальными значениями. В противном случае один из них будет заменен.
Вдохновленный ответом GETah, я решил написать нечто подобное с некоторыми улучшениями:
- Класс реализует
Map<K,V>-Интерфейс - Двунаправленность действительно гарантируется, если вы позаботитесь об этом при изменении значения на
put(по крайней мере, я надеюсь это гарантировать)
Использование аналогично карте нормалей, чтобы получить обратный взгляд на вызов отображения getReverseView(), Содержание не копируется, возвращается только представление.
Я не уверен, что это абсолютно надежно (на самом деле, вероятно, нет), поэтому не стесняйтесь комментировать, если вы заметите какие-либо недостатки, и я обновлю ответ.
public class BidirectionalMap<Key, Value> implements Map<Key, Value> {
private final Map<Key, Value> map;
private final Map<Value, Key> revMap;
public BidirectionalMap() {
this(16, 0.75f);
}
public BidirectionalMap(int initialCapacity) {
this(initialCapacity, 0.75f);
}
public BidirectionalMap(int initialCapacity, float loadFactor) {
this.map = new HashMap<>(initialCapacity, loadFactor);
this.revMap = new HashMap<>(initialCapacity, loadFactor);
}
private BidirectionalMap(Map<Key, Value> map, Map<Value, Key> reverseMap) {
this.map = map;
this.revMap = reverseMap;
}
@Override
public void clear() {
map.clear();
revMap.clear();
}
@Override
public boolean containsKey(Object key) {
return map.containsKey(key);
}
@Override
public boolean containsValue(Object value) {
return revMap.containsKey(value);
}
@Override
public Set<java.util.Map.Entry<Key, Value>> entrySet() {
return Collections.unmodifiableSet(map.entrySet());
}
@Override
public boolean isEmpty() {
return map.isEmpty();
}
@Override
public Set<Key> keySet() {
return Collections.unmodifiableSet(map.keySet());
}
@Override
public void putAll(Map<? extends Key, ? extends Value> m) {
m.entrySet().forEach(e -> put(e.getKey(), e.getValue()));
}
@Override
public int size() {
return map.size();
}
@Override
public Collection<Value> values() {
return Collections.unmodifiableCollection(map.values());
}
@Override
public Value get(Object key) {
return map.get(key);
}
@Override
public Value put(Key key, Value value) {
Value v = remove(key);
getReverseView().remove(value);
map.put(key, value);
revMap.put(value, key);
return v;
}
public Map<Value, Key> getReverseView() {
return new BidirectionalMap<>(revMap, map);
}
@Override
public Value remove(Object key) {
if (containsKey(key)) {
Value v = map.remove(key);
revMap.remove(v);
return v;
} else {
return null;
}
}
}
Здесь довольно старый вопрос, но если у кого-то еще есть мозговая блокада, как я только что сделал, и, надеюсь, это поможет.
Я тоже искал двунаправленный HashMap, иногда это самые простые ответы, которые являются наиболее полезными.
Если вы не хотите заново изобретать колесо и предпочитаете не добавлять другие библиотеки или проекты в свой проект, как насчет простой реализации параллельных массивов (или ArrayLists, если ваш дизайн требует этого).
SomeType[] keys1 = new SomeType[NUM_PAIRS];
OtherType[] keys2 = new OtherType[NUM_PAIRS];
Как только вы узнаете индекс 1 из двух ключей, вы можете легко запросить другой. Таким образом, ваши методы поиска могут выглядеть примерно так:
SomeType getKey1(OtherType ot);
SomeType getKey1ByIndex(int key2Idx);
OtherType getKey2(SomeType st);
OtherType getKey2ByIndex(int key2Idx);
Это предполагает, что вы используете правильные объектно-ориентированные структуры, где только методы модифицируют эти массивы /ArrayLists, было бы очень просто держать их параллельными. Еще проще для ArrayList, так как вам не придется перестраивать, если размер массивов изменяется, если вы добавляете / удаляете в тандеме.