هل جافا لديها hashmap مع البحث العكسي؟

Question

لدي بيانات يتم تنظيمها في نوع "مفتاح المفتاح"، بدلا من "القيمة الرئيسية". إنه مثل Hashmap، لكنني سأحتاج إلى O (1) بحثا في كلا الاتجاهين. هل هناك اسم لهذا النوع من هيكل البيانات، وهو أي شيء مثل هذا مدرج في المكتبات القياسية ل Java؟ (أو ربما المشاع أباش؟)

يمكنني كتابة صفي الخاص الذي يستخدمه أساسا اثنين من الخرائط المتقدمة، لكنني أفضل عدم إعادة اختراع العجلة (إذا كان هذا موجودا بالفعل، لكنني لا أبحث عن المصطلح الصحيح).

Answer 1

لا توجد فئة من هذا القبيل في api java. فئة المشاعهات Apache التي تريدها ستكون واحدة من تطبيقات BIDIMAP..

كعلاج عالمي، أود أن أسمي هذا النوع من هيكل الهيكل.

Answer 2

بالإضافة إلى المشاعات Apache، جوجا أيضا لديه بيماب.

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

Answer 4

إذا لم تحدث أي تصادم، فيمكنك دائما إضافة كلا الاتجاهين إلى نفس hashmap :-)

Answer 5

هنا بلدي 2 سنتا.

أو يمكنك استخدام طريقة بسيطة مع Generics. قطعة من الكعك.

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

بالطبع يجب أن يكون لديك خريطة مع قيم فريدة من نوعها. خلاف ذلك، سيتم استبدال واحد منهم.

Answer 6

سؤال كبير جدا هنا، ولكن إذا كان شخص آخر لديه كتلة في المخ مثل أنا فقط فعلت ويتعثر على هذا، نأمل أن يساعد ذلك.

كنت أيضا أبحث عن Hashmap ثنائية الاتجاه، في بعض الأحيان هو أبسط الإجابات التي هي الأكثر فائدة.

إذا كنت لا ترغب في إعادة اختراع العجلة وتفضل عدم إضافة مكتبات أو مشاريع أخرى لمشروعك، فماذا التنفيذ البسيط للمصفيفات الموازية (أو المستقلين إذا طلب تصميمك).

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

هذا يفترض أنك تستخدم هياكل ذات موجهة للكائنات المناسبة، حيث تعدل الطرق الوحيدة هذه الصفيفات / المرضيات، سيكون من السهل جدا الاحتفاظ بها بالتوازي. حتى أسهل للحصول على قائمة صفيف نظرا لأنك لن تضطر إلى إعادة البناء إذا تغير حجم الصفائف، طالما قمت بإضافة / إزالة في جنبا إلى جنب.

Answer 7

مستوحاة من إجابة 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;
        }
    }

}