php 数据结构 hash表

这个数据结构包含一个整型变量n（表示当前元素个数），以及两个数组members和position，前者用来储存当前集合中的元素，后者是一个长度为N的数组，用来记录每个数在members数组中的什么位置（换句话说members[position[i]] == i总成立）。 想要查询m是否在当

这个数据结构包含一个整型变量n（表示当前元素个数），以及两个数组members和position，前者用来储存当前集合中的元素，后者是一个长度为N的数组，用来记录每个数在members数组中的什么位置（换句话说members[position[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就行了。