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就行了。
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)。
说没反的没看懂吧，文中的两个公式明显一错一对，作者粗心了，奇怪的是为什么有人提醒还不改过来。
这个数据结构挺好的，看了很有收获。主要的改进就在于遍历的时间复杂度降到了最优，代价是需要一个长度为N的数组，这就要求N（数据范围）不能过大。与其说这是对哈希的改进，不如说是对编程珠玑里第一篇提到的位数组的改进，因为这两者才足够相似。而哈希对数据范围不敏感，这个数据结构则做不到。
赞，请教下：
1、变量值范围较大时（uint64_t），空间浪费较多，尤其是数组元素较少时更加严重，如何处理？
2、如果值不是整型，而是string、float等？
3、这个思想与Double Array Trie有些类似，通过双数组快速查找数据，适用范围更广。
JGDKFJADJFD
Write more, thats all I have to say. Literally, it seems as
though you relied on the video to make your point. You clearly know what
youre talking about, why throw away your intelligence on just posting videos to your blog when you could be giving us something enlightening to read?
Remarkable! Its genuinely awesome paragraph, I have got much clear idea regarding from
this piece of writing.
For example, when workkers come across themselves obsolete due to the automation of factories or the use
of artificial intelligence.
Feel free to visit myy blog; 이지알바
We heardd a mixture of pride and sadnes in the voices of most of our stay-at-dwelling moms.
Also visit my site; 밤알바
An intriguing discussion is definitely worth comment.
There’s no doubt that that you need to publish
more on this topic, it may not be a taboo subject but typically folks don’t speak about such topics.
To the next! Kind regards!!
Lunch will also be served in Harvest Dining Hall on Tuesdays, Saturday
and Sunday.
My web page: website
Wishket can be a incredibly useful tool for those seeking for
IT obs in South Korea.
Feel free to visit my page; 이지알바
In March,there were 13,860,800 peraons in the labour force (economists assume of the laboiur
fforce as the “provide of labour”).
My web page: 여자밤알바
The system operates about matching aspect-timers with deliveries close to their location.
my homepage; 룸 알바
You won’t have a payslip to prove your earnings,
but yyou can use your bank statements and/or your tax returns are proof of
revenue.
Feel free to surf to my wweb site … 정부지원대출
The app, available for iOS and Android, is easy to download and install.
My page … 토토사이트목록
Even so, if you spernd off the loan on time, it could outcome
in your crdit score getting negatively affected.
Herre is my web-site – 소액대출
The FanDuel Cassino promo code suply is a “Play It Again” up to $two,000 sign-up bonus.
Have a look at my web-site – 카지노
It’s very trouble-free to find out any topic on net as compared to textbooks, as I found this piece of writing at this web page.
The Fire use Ticketmaster SafeTix and have eliminated
alll PDFs and printed tickets.
my blog: site
I every time used to study piece of writing in news papers
but now as I am a user of net thus from now I am using net
for posts, thanks to web.
However, Australia’s credit laws still apply and the lender will still charge
you for borrowing money.
Keep this going please, great job!
bookmarked!!, I love your site!
powered by GoToTop.ee
https://ru.gototop.ee/
When someone writes an article he/she retains the plan of
a user in his/her mind that how a user can know it. So that’s why this piece of writing is amazing.
Thanks!
powered by GoToTop.ee
https://ru.gototop.ee/
It’s actually a great and helpful piece of info. I am glad
that you shared this helpful information with
us. Please keep us up to date like this. Thank you
for sharing.