5
我想建立一个通用的数据结构，需要保存键和值，并在同一时间跟踪索引的哪些键和值放入像arraylist只做复杂的O（log n）或减。是否有可能创建具有log（n）复杂性的ArrayList属性的Map？
我尝试解决此问题的解决方案，并创建了具有整数的各种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);
}
}
https://stackoverflow.com/questions/44170832/access-tree-with-ordinal-index –