2009-01-21 18:56| 
29 Comments | 本文内容遵从Hash表是一个很有用的数据结构，它用O(N)的空间描述一个元素在0到N-1范围内的集合，支持常数级别的添加、删除和查询。遗憾的是，Hash表不能在常数时间内批量删除元素，返回全部元素也需要O(N)的时间，而理论上说这几个操作可以做的更好。现在，你能否设计一个数据结构，它同样占用O(N)的空间，支持常数时间的添加、删除、查询、清空（删除所有元素）、势查询（返回元素个数），以及O(n)时间的元素遍历（其中n表示集合中的元素个数）。
这个数据结构包含一个整型变量n（表示当前元素个数），以及两个数组members和position，前者用来储存当前集合中的元素，后者是一个长度为N的数组，用来记录每个数在members数组中的什么位置（换句话说position[members[i]] == i总成立）。
想要查询m是否在当前集合内，只需要看看position[m]是不是在0到n-1的范围内，并且members[position[m]]是否也确实等于m。添加一个元素只需要把新元素放进members[n++]，并更新position的相应数据。删除一个元素只需要把该元素移到members队列末尾（让这个元素和members数组的第n个数对换一下位置），同时更新position的相应数据，然后n自减一。清空集合只需要直接令n等于0即可。遍历元素只需要扫描members数组中当前有效的那一段，这显然是O(n)的。变量n就是元素个数，需要查询元素个数时直接返回n就行了。
参考资料：http://www.onebadseed.com/blog/?p=80
position[members[i]] == i
我怎么觉得这个反了
bd
板凳～
没有反吧？
还是一个和下标有关的整数结构……
我怎么觉得这很像数组模拟链表。。。
这一篇怎么感觉有一点水……
的确反了，position记录元素在members数组中的什么位置，i是一个元素，那怎么也得是member[position[i]]==i……
TO 楼上：i代表的可以是地址……
怎么感觉和置换群有点类似？
如果在一个无序表中建立一个序，就得使用{...,{index, value},...}的这种形式吧。Mathematica里面Position和Part不就是干这个的？
恩……
嗯嗯...想不到只需要多维护一组下标就可以有那么多收获~
数据结构真是迷人~
用Hash表有什么意义, 这个结构在每一方面都比Hash表强...
哈~这篇文章的评论。。。挨着看下来，都是：“我怎么觉得……”“我怎么觉得……”“怎么感觉……”“怎么感觉……”
hash_map似乎是用的O(n)的空间，
而且时间复杂度和你给的这种结构一样。
这个结构存在一个问题，position[m]是什么复杂度的？作者没有说明白。
飘过～
哦,实用的hash表改进. 只是还没有解决position表的容量大小和冲突问题.
ls所言极是～～
我似乎用过类似的东西……
确实像数组模拟链表啊。。position模拟链表中内存自动分配
position[m]直接可以得到了？
那岂不是只能存正整数
ms实践中用过，缺点是N不能太大；但是hash表或者平衡树之类可以处理大N的情况。
21楼所说的N不能太大，大概N多大就影响性能？
to16楼 长途可以想类似于Hashmap的方法解决
但是如果事先不知道待处理元素的上界，N就没法确定，否则有得Hash到< N的区间
#include
这个数据结构比起hash表有相当的限制，
数据必须是0..N-1的整数
其实counting sort里面的那个数组就可以这个数据结构的功能了……
这篇的确水了,期待大牛能给Hash做个别样的序
还可以啊，只不过多使用一个数组，我觉得是以空间换时间了。
hash的目的在于把查找的时间复杂度降到O(n),关键在于构造一个数组下标和value之间的函数，可以用value来算下标。博主大部分博文都很好，这篇是低于平均水平了。
抱歉，上面第一行的时间复杂度应该是O(1)。