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

Question

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

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

为了更清楚，索引象征着来自用户的插入顺序。所以如果我有 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 可能有一些变化，也许是自定义构造，但这似乎需要做很多工作。

相反，我建议您考虑使用红黑树或类似的平衡树，并在 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://fdatamining.blogspot.ca/2011/09/functional-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) 时间的第二棵树中，通过向上遍历树到根并执行简单计算。

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

在任何一棵树中的删除都将先推迟对另一棵树的引用，然后删除第一棵树中的节点，然后删除另一棵树中的相应节点，都是 O(log n) 操作。

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

那样有用吗？