是否有可能创建一个与日志（n）的复杂的ArrayList性质的地图？ [英] Is it possible to create a Map that has ArrayList properties with log(n) complexity?
问题描述
我想建立一个需要持有键和值的通用数据结构，并在同一时间跟踪在其中关键的和值分别投放如ArrayList指数的只是在一个复杂度O做（log n）的或更小。
我tryed变通解决这一问题，并创造了各种树状图有整型 - 指数的和valuse，反之亦然，并与按键相同
只是为了更清楚，该指数的象征从用户插入的顺序。所以，如果我有3个元素则其索引的是0 1 2，如果元素0被删除，然后我需要把1比0和2比1和一个新元素将与指数2加入。
我的问题是，当我删除键和它的价值，如果我想插入正确的索引我必须确保所有的旧分别设置回来1。我不知道怎么下键和值做到这一点，而不是陷入O（n）的复杂性。
我的目标是利用现有的数据结构的混合他们得到这样的结果，请看看我实现的方法，因为我需要这些。
我加入我的code，以供参考，任何帮助将是非常美联社preciated。
感谢您
汤姆
进口java.util.Collection中;
进口的java.util.HashMap;
进口java.util.TreeMap中;
进口的java.util.Map;公共类SuperStruct＆LT; K，V＆GT;
{
私人地图＆LT; K，V＆GT; mInternalKeyToValueMap; //所有键和它们的值
私人地图＆LT;整数，V＆GT; mIndexToValueMap; //指数对值根据入口以
私人地图＆LT; V，整数GT; mValueToIndexMap; //值及其指数的
私人地图＆LT;整数，K＆GT; mIndexToKeyMap; //指数的，并根据高考秩序钥匙
私人地图＆LT; K，整数GT; mKeyToIndexMap; //按键及其指数的
私人诠释mNextIndex;用于根据该命令数据的数据结构//索引由用户接收 公共SuperStruct（）{
mInternalKeyToValueMap =新TreeMap的＆LT; K，V＆GT;（）;
mIndexToValueMap =新TreeMap的＆LT;整数，V＆GT;（）;
mValueToIndexMap =新TreeMap的＆LT; V，整数GT;（）;
mIndexToKeyMap =新TreeMap的＆LT;整数，K＆GT;（）;
mKeyToIndexMap =新TreeMap的＆LT; K，整数GT;（）;
}
公共布尔的containsKey（对象键）{
布尔容纳的= mInternalKeyToValueMap.containsKey（键）;
返回容纳的;
} 公共布尔的containsValue（对象的值）{
布尔容纳的= mValueToIndexMap.containsKey（值）;
返回容纳的;
} 公共V的get（对象键）{
如果（mInternalKeyToValueMap.containsKey（键））{
V值= mInternalKeyToValueMap.get（键）;
返回值;
}
返回null;
} 公文集＆LT; K＆GT;键设置（）{ 返回mInternalKeyToValueMap.keySet（）;
}
/ **
*此方法是把钥匙，并在主TreeMap中mInternalKeyToValueMap的值，而在平均时间更新其他4树状图
*与关于在其中数据是从用户接收的索引数据。
*所有这一切的方法在6 *（O（log n）的），总结下来到0运行的复杂性（log n）的原因常量不整过计算
*计算的复杂性
*如果一个键已经有了一个映射到它，我们重写，我们将在11 *（O（log n）的）复杂运行值仍总结下降到O（log n）的
*原因常量不整过计算
* / 公共五世所说（K键，V值）{
如果（mValueToIndexMap.containsKey（值））//值preventing重复
返回值;
如果（mInternalKeyToValueMap.containsKey（键））{//当钥匙系统已经存在，我们要覆盖其值
INT indexToDelete = mKeyToIndexMap.get（关键）; //我们得到的值的指数，我们在写
V值1 = mIndexToValueMap.get（indexToDelete）; //使用这个指标，我们得到的价值
mValueToIndexMap.remove（值）; //我们删除的价值和它的索引
mIndexToValueMap.remove（indexToDelete）; //我们删除索引，并将其值
}
mInternalKeyToValueMap.put（键，值）; //将新的值在主TreeMap中的关键
mValueToIndexMap.put（值，mNextIndex）;值//填充TreeMap和其索引的 - 我们收到他们从用户的顺序
mIndexToValueMap.put（mNextIndex，价值）; //这个TreeMap的根据插入用户的订单中包含索引的每个值
mIndexToKeyMap.put（mNextIndex，键）; //这个TreeMap的根据插入用户的订单中包含索引的每个键
mKeyToIndexMap.put（键，mNextIndex）; //填充键TreeMap和其索引的 - 我们收到他们从用户的顺序
++ mNextIndex; //推进这标志着参数的插入顺序来组织索引
返回null; }
公共v卸下（对象键）{
如果（mInternalKeyToValueMap.containsKey（键）==真＆放大器;＆安培;！（mInternalKeyToValueMap.get（密钥）= NULL））
{
V值= mInternalKeyToValueMap.get（键）;
mInternalKeyToValueMap.remove（键）; //为值去除地图
INT mIndexToRemoveValue = mValueToIndexMap.get（价值）; //获得正确的索引删除值
mIndexToValueMap.remove（mIndexToRemoveValue）; //腾出该指数值
mIndexToKeyMap.remove（mIndexToRemoveValue）; //为腾出该指数的关键
mKeyToIndexMap.remove（键）; //删除在keyToIndex Map中的键和索引
mValueToIndexMap.remove（值）; //删除在ValueToIndex Map中的键和索引
返回值; }
返回null;
}
公文集＆LT; V＆GT;值（）{
返回mInternalKeyToValueMap.values（）;
} 公文集＆LT; V＆GT; getStrcutureSorted（）{
返回mValueToIndexMap.keySet（）;
} 公共V getValueByIndex（INT指数）{//返回其值在坐，指数如果没有present空
V值= mIndexToValueMap.get（指数）;
返回值;
} 公共整数getIndexByKey（K键）{
整数退货= mKeyToIndexMap.get（键）;
如果（可回收== NULL）
返回-1;
返回退回。
}
公共ķgetKeyByIndex（INT指数）{
返回mIndexToKeyMap.get（索引）;
}
}
这是一个有趣的难题。这感觉就像它应该是可能的，但细节难以捉摸。的问题是在索引更新操作之后的删除。如果索引存储在一个树节点，例如，然后在平均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/functional-red-black-tree-with-dynamic.html, http://en.wikipedia.org/wiki/Order_statistic_tree 。这应该让你开始。
更新：实施细节
你将要做的是创建两棵树。人们可以是一个普通的平衡树（如红黑树）将与键/值对你对象的引用。你可以搜索的关键的O得到相应的价值（log n）的;插入和删除也将是O（log n）的。此外，在此先树节点将举行第二树（下图）。
要参考节点第二棵树也将坚持节点引用的第一棵树，但是这将是一个顺序统计树如上面的讨论。插入将始终把新项目，在树的右端。
这是插入操作该数据结构将是一个普通的插入到由密钥对第一树，插入操作的次序统计树的右边，并且在每个插入节点的参考资料将被更新为指向到适当的位置在其他树。
一个搜索操作可以在第一树来完成对在O（log n）的一个给定的密钥，这将返回适当的值，和下面的其他树的引用，可以用来找到顺序统计在澳第二棵树的节点由树遍历到根目录并执行一个简单的计算（log n）的时间。
一个搜索操作可以在澳第二棵树来完成（log n）的时间，在队列中的第k个位置，返回到第二棵树，这可能是间接引用，以获得相应的键/值对的参考。
删除在任一树将是deferencing提及的其它树，则删除在所述第一树的节点中，接着在相应的节点的缺失在其他树pceded $ P $，两个O（log n）的操作。
我觉得就是这样。一切都可以在O完成（log n）的时间。有一个在第二棵树空间较小的成本，但它只是包含引用;空间仍然是O（n）。
运作的？
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);
}
}
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?
这篇关于是否有可能创建一个与日志（n）的复杂的ArrayList性质的地图？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
