Javaには逆ルックアップ付きのハッシュマップがありますか?
-
13-09-2019 - |
質問
「キーバリュー」ではなく、「キーキー」形式のようなデータが編成されているデータがあります。それはハッシュマップのようなものですが、両方向にO(1)の検索が必要です。このタイプのデータ構造の名前はありますか?また、Javaの標準ライブラリにこのようなものが含まれていますか? (または多分アパッチコモンズ?)
基本的に2つのミラー化されたマップを使用している自分のクラスを書くことができますが、ホイールを再発明することはむしろ(これが既に存在しますが、適切な用語を検索していない場合です)。
解決
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;
}
もちろん、一意の値のマップが必要です。それ以外の場合は、そのうちの1つが交換されます。
ここにはかなり古い質問がありますが、他の誰かが私のように脳のブロックを持っているなら、これにつまずいた場合、うまくいけばこれが役立つでしょう。
私も双方向のハッシュマップを探していましたが、最も便利な回答の最も単純なものです。
ホイールを再発明したくない場合、プロジェクトに他のライブラリやプロジェクトを追加したくない場合は、並列配列(またはデザインが要求する場合は配列リスト)の簡単な実装についてはどうですか。
SomeType[] keys1 = new SomeType[NUM_PAIRS];
OtherType[] keys2 = new OtherType[NUM_PAIRS];
2つのキーのうち1つのインデックスを知るとすぐに、他のキーを簡単にリクエストできます。したがって、あなたのルックアップ方法は次のように見えるかもしれません:
SomeType getKey1(OtherType ot);
SomeType getKey1ByIndex(int key2Idx);
OtherType getKey2(SomeType st);
OtherType getKey2ByIndex(int key2Idx);
これは、これらの配列/アレイリストを変更している方法のみがそれらを並列に保つことが非常に簡単になる場合、適切なオブジェクト指向構造を使用していることを前提としています。アレイリストのサイズが変更された場合、タンデムを追加/削除する限り、アレイリストの方がさらに簡単です。
に触発された ゲタの答え 私はいくつかの改善で自分で似たようなものを書くことにしました:
- クラスは実装しています
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;
}
}
}