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

我正在尝试构建一个通用数据结构，它需要保存键和值，同时跟踪索引，其中键和值被放入其中，就像 arraylist 那样，复杂度为 O(log n) 或更少。

我尝试解决这个问题，并创建了各种具有整数索引和值的 TreeMap，反之亦然，键也相同。

为了更清楚地说明，索引象征着用户的插入顺序。所以如果我有 3 个元素，那么它们的索引是 0 1 2，如果元素 0 被删除，那么我需要将 1 推到 0，将 2 推到 1，然后将添加一个索引为 2 的新元素。

我的问题是，当我删除一个键及其值时，如果我想在正确的索引中插入下一个键和值，我必须确保所有旧的键和值都被设置回 1。我不知道该怎么做并且不会陷入 O(n) 复杂度。

我的目标是使用现有的数据结构并将它们混合以获得此结果，请查看我在需要时实现的方法。

我添加我的代码以供参考，任何帮助将不胜感激。

谢谢

Tom

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

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

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

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

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

以下是该技术的更多参考：http://www.cs.usfca.edu/~galles/cs673/lecture/lecture8.pdf http://www.cs.usfca.edu/~galles/cs673/lecture/lecture8.pdf, http://fdatamining.blogspot.ca/2011/09/function-red-black-tree-with-dynamic.html http://fdatamining.blogspot.ca/2011/09/functional-red-black-tree-with-dynamic.html, http://en.wikipedia.org/wiki/Order_statistic_tree 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)。

那样有用吗？