Java是否具有反向查找的哈希图?
-
13-09-2019 - |
题
我的数据是以“键键”格式组织的,而不是“键值”。这就像一个哈希图,但我需要在两个方向上o(1)查找。是否有此类数据结构的名称,并且Java的标准库中是否包含类似的名称? (还是Apache Commons?)
我可以写自己的课程,该课程基本上使用了两个镜像地图,但是我宁愿不重新发明轮子(如果已经存在,但我只是不搜索正确的术语)。
解决方案
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);
}
}
如果没有发生冲突,您随时可以将两个方向添加到同一哈希图:-)
这是我的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;
}
当然,您必须具有具有唯一值的地图。否则,其中一个将被替换。
这里是一个古老的问题,但是如果其他人像我刚刚一样拥有大脑障碍,并偶然发现了这一点,希望这会有所帮助。
我也在寻找双向哈希图,有时这是最有用的答案中最简单的答案。
如果您不希望重新发明轮子,而不想在您的项目中添加其他库或项目,那么简单的并行阵列的实现(如果您的设计需要)如何实现。
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);
这是假设您使用的是适当的面向对象的结构,其中只有方法正在修改这些数组/阵列列表,那么保持它们并行非常简单。对于阵列列表而言,甚至更容易,因为只要您串联添加/删除阵列,您就不必重建阵列。
受到启发 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;
}
}
}