Java에는 역방향 조회가있는 해시 맵이 있습니까?

StackOverflow https://stackoverflow.com/questions/1670038

문제

"키 값"이 아닌 일종의 "키 키"형식으로 구성된 데이터가 있습니다. 해시 맵과 같지만 양방향으로 O (1) 조회가 필요합니다. 이러한 유형의 데이터 구조에 대한 이름이 있습니까? Java의 표준 라이브러리에 포함되어 있습니까? (또는 아마도 아파치 커먼즈?)

기본적으로 두 개의 미러지도를 사용하는 내 자신의 수업을 쓸 수 있었지만 바퀴를 재발 명하지 않을 것입니다 (이미 존재하지만 올바른 용어를 찾고 있지 않다면).

도움이 되었습니까?

해결책

Java API에는 그러한 수업이 없습니다. 당신이 원하는 Apache Commons 클래스는 Bidimap.

수학자로서, 나는 이런 종류의 구조를 biejection이라고 부를 것입니다.

다른 팁

Apache Commons 외에도 구아바 또한 Bimap.

다음은 내가이 작업을 수행하는 데 사용한 간단한 수업입니다 (또 다른 제 3 자 종속성을 갖고 싶지 않았습니다). 맵에서 사용할 수있는 모든 기능을 제공하지는 않지만 좋은 출발입니다. 

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

이것은 당신이 적절한 객체 지향 구조를 사용하고 있다고 가정합니다. 여기서 메소드만이 배열/어레이리스트를 수정하는 방법만이 그들을 평행하게 유지하는 것은 매우 간단합니다. 배열의 크기가 변경되면 재 구축 할 필요가 없으므로 arraylist의 경우 더 쉽습니다.

에서 영감을 받다 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;
        }
    }

}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top