Is it possible to create a Map that has ArrayList properties with log(n) complexity?

Question

I am trying to build a generic data structure that needs to hold keys and values and in the same time keep track on the index's in which key's and values were put in like arraylist do just in a complexity of O(log n) or less.

I tryed to work around a solution to this problem and created various TreeMaps that has Integer - index's and valuse and vise-versa, and the same with keys.

Just to make it more clear, the Index's symbolize the insertion order from the user. so if I had 3 elements then their index's are 0 1 2 and if element 0 was deleted then I need to push 1 to 0 and 2 to 1 and a new element would be added with index 2.

My problem is when I remove a key and its value, if I want to insert the next key and value in the right index I have to make sure all the old ones were set back by 1. I don't know how to do it and not to fall into O(n) complexity.

My goal is to use existing data structure's and mixing them to get this result, please take a look at the methods I implemented as I need those.

I am adding my code for reference, any help would be much appreciated.

Thank you

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

Answer 1

This is an interesting conundrum. It feels like it should be possible, but the details are elusive. The problem is in the index update operation after a delete. If the indexes are stored in a tree node, for example, then on average n/2 indexes will have to be altered after a delete operation, which ruins the O(log n) property you are striving for.

If you store objects simultaneously in a tree and in an ArrayList, you still have the issue of locating an object in the ArrayList, which I can't get to work in a straightforward fashion in time less than O(n). Possibly there's some variation on an ArrayList, perhaps a custom construction, but that seems like a lot of work.

Instead, I suggest you consider a red-black tree or similar balanced tree with the modification noted at Red-black tree access by ordinal index: for each node of the tree, store also the count of nodes in the subtree with the given node as root. During insert and delete operations, you will have to update the count of all nodes affected by a rotation operation. That can still be done in O(log n) time, but it is complicated.

Then binary searches for the kth smallest (or largest) element will also run in O(log n) time, as usual, by the usual recursive algorithm.

Here are a few more references for the technique: 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. That should get you started.

Update: implementation details

What you will have to do is to create two trees. One could be an ordinary balanced tree (like a red-black tree) to hold references to your objects with key/value pairs. You could search on the key and get the corresponding value in O(log n); insertion and deletion would also be O(log n). In addition, nodes in this first tree would hold references to nodes in the second tree (below).

The second tree would also hold references to nodes in the first tree, but it would be an order statistic tree as in the discussion above. Insertions would always place new items at the right end of the tree.

An insert operation into this data structure would be an ordinary insert into the first tree by key, an insert into the right side of the order statistic tree, and the references in each inserted node would be updated to point to the appropriate location in the other tree.

A search operation could be done on the first tree for a given key in O(log n), which would return the appropriate value, and following a reference to the other tree, could be used to find the "order statistic" of the node in the second tree in O(log n) time by traversing up the tree to the root and performing a simple calculation.

A search operation could be done on the second tree in O(log n) time for the kth position in the queue, returning a reference to the second tree, which could be dereferenced to obtain the associated key/value pair.

Deletion in either tree would be preceded by deferencing the reference to the other tree, then deletion of the node in the first tree, followed by deletion of the corresponding node in the other tree, both O(log n) operations.

I think that's it. Everything can be done in O(log n) time. There is a minor cost in space for the second tree, but it just contains references; space is still O(n).

Does that work?