是否可以创建具有log(n)复杂性的ArrayList属性的Map？

Question

我正在尝试构建一个通用的数据结构,需要保存密钥和值,同时跟踪索引的关键字和值,就像arraylist一样,复杂度为O(log n)或更小.

我试图解决这个问题的解决方案,并创建了各种具有整数的TreeMaps - 索引和valuse,反之亦然,并且与密钥相同.

为了使其更清晰,索引符号表示来自用户的插入顺序.所以,如果我有3个元素,那么它们的索引是0 1 2,如果元素0被删除,那么我需要按1到0和2到1,并且新元素将添加索引2.

我的问题是当我删除一个键及其值时,如果我想在右侧索引中插入下一个键和值,我必须确保所有旧键都被设置为1.我不知道该怎么做而不是陷入O(n)复杂性.

我的目标是使用现有的数据结构并混合它们来获得这个结果,请看看我实现的方法,因为我需要这些.

我正在添加我的代码供参考,任何帮助将不胜感激.

谢谢

汤姆

import java.util.Collection;
import java.util.HashMap;
import java.util.TreeMap;
import java.util.Map;

public class SuperStruct<K,V> 
{
    private Map<K,V> mInternalKeyToValueMap;//all the keys and their values 
    private Map<Integer,V> mIndexToValueMap;//index's for values according to the entrance order to 
    private Map<V,Integer> mValueToIndexMap;//values and their index's
    private Map<Integer,K> mIndexToKeyMap;//index's and their keys according to entrance order
    private Map<K,Integer> mKeyToIndexMap;//keys and their index's
    private int mNextIndex;//index for the data structure according to the order data was received by user

    public SuperStruct(){
        mInternalKeyToValueMap = new TreeMap<K,V>();
        mIndexToValueMap = new TreeMap<Integer,V>();
        mValueToIndexMap = new TreeMap <V,Integer>();
        mIndexToKeyMap = new TreeMap <Integer, K>();
        mKeyToIndexMap = new TreeMap <K,Integer>();     
    }
    public boolean containsKey(Object key) {
        boolean containable = mInternalKeyToValueMap.containsKey(key);
        return containable;
    }

    public boolean containsValue(Object value) {
        boolean containable = mValueToIndexMap.containsKey(value);
        return containable;
    }

    public V get(Object key) {
        if(mInternalKeyToValueMap.containsKey(key)){
            V value = mInternalKeyToValueMap.get(key);
            return value;
        }
        return null;
    }



    public Collection<K> keySet() {

        return mInternalKeyToValueMap.keySet();
    }
    /**
     * This method is putting the key and the value in the main TreeMap "mInternalKeyToValueMap", while on the mean time updating 4 other TreeMaps
     * with data regarding to the index in which data was received from the user.
     * all in all this method runs in complexity of 6*(O(log n)) that sums down to O(log n) cause constants don't calculate over the whole 
     * Complexity calculation
     * In case that a key already had a mapping to it and we overwrite the value we will run in complexity of 11*(O(log n)) which still sums down to O(log n) 
     * cause constants don't calculate over the whole 
     */

    public V put(K key, V value) {
        if(mValueToIndexMap.containsKey(value))//preventing duplications of value
            return value;
            if(mInternalKeyToValueMap.containsKey(key)){//when a key already exist in system and we want to overwrite its value
                int indexToDelete = mKeyToIndexMap.get(key);//we get the index of the value we over-write
                V value1 = mIndexToValueMap.get(indexToDelete);//using this index we get the value
                mValueToIndexMap.remove(value1);//we remove the value and its index
                mIndexToValueMap.remove(indexToDelete);//we remove the index and its value
            }
            mInternalKeyToValueMap.put(key, value);//putting the new value for the key in the main TreeMap
            mValueToIndexMap.put(value, mNextIndex);//populating the TreeMap of values and their index's - the order we received them from the user
            mIndexToValueMap.put(mNextIndex, value);//This TreeMap holds the index's for each value according to the order of insertion by user
            mIndexToKeyMap.put(mNextIndex, key);//This TreeMap holds the index's for each key according to the order of insertion by user
            mKeyToIndexMap.put(key,mNextIndex);//populating the TreeMap of keys and their index's - the order we received them from the user
            ++mNextIndex;//advancing the index which mark the insertion order of arguments to structure
            return null;

    }


    public V remove(Object key) {   
        if(mInternalKeyToValueMap.containsKey(key)==true && (mInternalKeyToValueMap.get(key)!=null))
        {
            V value = mInternalKeyToValueMap.get(key);
            mInternalKeyToValueMap.remove(key);//removing map for the value 
            int mIndexToRemoveValue = mValueToIndexMap.get(value);//getting the right index to remove the value
            mIndexToValueMap.remove(mIndexToRemoveValue);//vacating the value for this index
            mIndexToKeyMap.remove(mIndexToRemoveValue);//vacating the key for this index
            mKeyToIndexMap.remove(key);//removing a key and index in the keyToIndex Map
            mValueToIndexMap.remove(value);//removing a key and index in the ValueToIndex Map
            return value;

        }
        return null;
    }


    public Collection<V> values() {     
        return mInternalKeyToValueMap.values();
    }

    public Collection<V> getStrcutureSorted(){
        return mValueToIndexMap.keySet();
    }

    public V getValueByIndex(int index){//return the index in which the value sits in, if not present null 
        V value = mIndexToValueMap.get(index);
            return value;
    }

    public Integer getIndexByKey(K key){
        Integer returnable = mKeyToIndexMap.get(key);
        if(returnable == null)
            return -1;
        return returnable;


    }
    public K getKeyByIndex(int index){
        return mIndexToKeyMap.get(index);
    }
    }

Answer 1

这是一个有趣的难题。感觉应该是可以的，但细节却难以捉摸。问题出在删除后的索引更新操作中。例如，如果索引存储在树节点中，则在删除操作后平均必须更改 n/2 个索引，这会破坏您所追求的 O(log n) 属性。

如果您同时将对象存储在树和 ArrayList 中，那么仍然存在在 ArrayList 中定位对象的问题，而我无法在小于 O(n) 的时间内以简单的方式完成工作。ArrayList 可能有一些变化，也许是自定义构造，但这似乎需要大量工作。

相反，我建议您考虑红黑树或类似的平衡树，并按序数索引进行红黑树访问中所述的修改：对于树的每个节点，还将给定节点的子树中的节点数存储为根。在插入和删除操作期间，您必须更新受旋转操作影响的所有节点的计数。这仍然可以在 O(log n) 时间内完成，但很复杂。

然后，像往常一样，通过通常的递归算法，对第 k 个最小（或最大）元素的二分搜索也将在 O(log n) 时间内运行。

以下是该技术的更多参考：http://www.cs.usfca.edu/~galles/cs673/lecture/lecture8.pdf、http : //fdatamining.blogspot.ca/2011/09/function-red -black-tree-with-dynamic.html，http://en.wikipedia.org/wiki/Order_statistic_tree。这应该可以帮助你开始。

更新：实施细节

您要做的就是创建两棵树。其中一个可以是普通的平衡树（如红黑树），用于保存对带有键/值对的对象的引用。您可以搜索键并在 O(log n) 中获取相应的值；插入和删除也将是 O(log n)。此外，第一棵树中的节点将保存对第二棵树（如下）中节点的引用。

第二棵树也将保存对第一棵树中节点的引用，但它将是一个顺序统计树，如上面讨论的那样。插入总是将新项目放置在树的右端。

对此数据结构的插入操作将是按键普通插入第一棵树，插入顺序统计树的右侧，并且每个插入节点中的引用将更新为指向另一个节点中的适当位置树。

可以在第一棵树上对给定键进行搜索操作，时间复杂度为 O(log n)，这将返回适当的值，并且在对另一棵树的引用之后，可用于查找节点的“顺序统计量”通过向上遍历树到根并执行简单的计算，可以在 O(log n) 时间内找到第二棵树。

可以在 O(log n) 时间内对第二棵树完成队列中第 k 个位置的搜索操作，返回对第二棵树的引用，可以取消引用该第二棵树以获得关联的键/值对。

在删除任一树中之前，都会先引用对另一棵树的引用，然后删除第一棵树中的节点，然后删除另一棵树中的相应节点，这两个操作都是 O(log n) 操作。

我想就是这样。一切都可以在 O(log n) 时间内完成。第二棵树的空间成本很小，但它只包含引用；空间仍然是 O(n)。

那样有用吗？