一个简单而有用的数据结构

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