我的数据是以“key-key”格式组织的,而不是“key-value”。它就像一个hashmap,但是我需要在两个方向上进行o(1)查找。这种类型的数据结构是否有一个名称,类似的内容是否包含在java的标准库中(或者apache commons?)我可以编写我自己的类,基本上使用两个镜像Map,但我不想重新发明轮子(如果这已经存在,但我只是没有寻找正确的术语)。
33qvvth11#
这里有一个简单的类,我用它来完成这个任务(我不想有另一个第三方依赖)。它并没有提供Map上的所有功能,但这是一个很好的开始。
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); } }
blmhpbnm2#
受到盖塔答案的启发,我决定自己写一些类似的东西,并做了一些改进:类正在实现 Map<K,V> -接口双向性实际上是通过在改变一个值时注意它来保证的 put (至少我希望能保证)用法就像一个普通的Map,在Map调用上获得一个反向视图 getReverseView() . 不复制内容,只返回一个视图。我不确定这是完全傻瓜证明(实际上,它可能不是),所以请随意评论,如果你注意到任何缺陷,我会更新答案。
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; } } }
r1zk6ea13#
这是一个很老的问题,但如果有人像我一样有大脑障碍,并无意中发现了这个问题,希望这会有所帮助。我也在寻找一个双向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);
这是假设您使用的是正确的面向对象结构,其中只有方法修改这些数组/数组列表,保持它们的并行将非常简单。对于arraylist来说更容易,因为如果数组的大小发生变化,只要您同时添加/删除,就不必重新生成。
kxe2p93d4#
这是我的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; }
当然,必须有一个具有唯一值的Map。否则,其中一个将被替换。
4jb9z9bj5#
如果没有发生冲突,则始终可以将两个方向添加到同一hashmap:-)
smdncfj36#
javaapi中没有这样的类。您想要的apachecommons类将是bidimap的实现之一。作为数学家,我把这种结构称为双射。
gstyhher7#
除了apachecommons,guava还有一个bimap。
7条答案
按热度按时间33qvvth11#
这里有一个简单的类,我用它来完成这个任务(我不想有另一个第三方依赖)。它并没有提供Map上的所有功能,但这是一个很好的开始。
blmhpbnm2#
受到盖塔答案的启发,我决定自己写一些类似的东西,并做了一些改进:
类正在实现
Map<K,V>
-接口双向性实际上是通过在改变一个值时注意它来保证的
put
(至少我希望能保证)用法就像一个普通的Map,在Map调用上获得一个反向视图
getReverseView()
. 不复制内容,只返回一个视图。我不确定这是完全傻瓜证明(实际上,它可能不是),所以请随意评论,如果你注意到任何缺陷,我会更新答案。
r1zk6ea13#
这是一个很老的问题,但如果有人像我一样有大脑障碍,并无意中发现了这个问题,希望这会有所帮助。
我也在寻找一个双向hashmap,有时它是最简单的答案,是最有用的。
如果您不想重新发明轮子,也不想将其他库或项目添加到您的项目中,那么简单地实现并行数组(如果您的设计需要,可以使用arraylists)怎么样。
一旦知道两个键中的1的索引,就可以轻松地请求另一个键。因此,查找方法可能类似于:
这是假设您使用的是正确的面向对象结构,其中只有方法修改这些数组/数组列表,保持它们的并行将非常简单。对于arraylist来说更容易,因为如果数组的大小发生变化,只要您同时添加/删除,就不必重新生成。
kxe2p93d4#
这是我的2美分。
或者你可以使用一个简单的泛型方法。小菜一碟。
当然,必须有一个具有唯一值的Map。否则,其中一个将被替换。
4jb9z9bj5#
如果没有发生冲突,则始终可以将两个方向添加到同一hashmap:-)
smdncfj36#
javaapi中没有这样的类。您想要的apachecommons类将是bidimap的实现之一。
作为数学家,我把这种结构称为双射。
gstyhher7#
除了apachecommons,guava还有一个bimap。