一个哈希表问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

一个哈希表问题

一个哈希表问题# Programming - 葵花宝典

t*s2007-02-01 08:02

1 楼

下面的问题我想用哈希表解决，可不符合要求。怎么才能使时间为常数并不依赖集合的
大小呢？
Design an efficient data structure for representing a subset S of the
integers from 1 to n. The operations we wish to perform are these:
1. Select an integer i from the set and delete it.
2. Add an integer i to the set.
A mechanism must be provided to ignore a request to add integer i to S in
the case where S alrady contains i. The data structure must be such that the
time to select and delete an element and the time to add an element are
consta

S*n2007-02-01 08:02

2 楼

为什么hash table不符合要求？

the

【在 t**********s 的大作中提到】

: 下面的问题我想用哈希表解决，可不符合要求。怎么才能使时间为常数并不依赖集合的
: 大小呢？
: Design an efficient data structure for representing a subset S of the
: integers from 1 to n. The operations we wish to perform are these:
: 1. Select an integer i from the set and delete it.
: 2. Add an integer i to the set.
: A mechanism must be provided to ignore a request to add integer i to S in
: the case where S alrady contains i. The data structure must be such that the
: time to select and delete an element and the time to add an element are
: consta

t*s2007-02-01 08:02

3 楼

以为哈希表查找时有冲突，所以查找的时间不为常量啊

【在 S*****n 的大作中提到】

: 为什么hash table不符合要求？
:
: the

S*n2007-02-01 08:02

4 楼

建个n大小的hash table, 用==做hash函数。
有冲突就是存在啊。

【在 t**********s 的大作中提到】

: 以为哈希表查找时有冲突，所以查找的时间不为常量啊

t*s2007-02-01 08:02

5 楼

你是说哈希表的大小就是1...n的大小，就是subset S包含了所有1到n?
不是说哈希表是一个大集合影射到一个小集合上吗？

【在 S*****n 的大作中提到】

: 建个n大小的hash table, 用==做hash函数。
: 有冲突就是存在啊。

t*t2007-02-01 08:02

6 楼

没说小集合一定比大集合小啊

【在 t**********s 的大作中提到】

: 你是说哈希表的大小就是1...n的大小，就是subset S包含了所有1到n?
: 不是说哈希表是一个大集合影射到一个小集合上吗？

t*s2007-02-01 08:02

7 楼

那么下面的mechanism又是什么呢？
A mechanism must be provided to ignore a request to add integer i to S in
the case where S alrady contains i.
是不是这样就可以了：
if A(h(i))!=empty then return error
如果小集合与大集合相等，那么这个哈希表的具体实现就用arrar怎么样？

【在 t****t 的大作中提到】

: 没说小集合一定比大集合小啊

t*t2007-02-01 08:02

8 楼

how about bitset?

S*n2007-02-01 08:02

9 楼

一般的说，算法这个东西就是时间和空间搞trade-off, 在这个例子里，你想达到
常数时间的速度，你就的在空间上做牺牲，用足够大的空间。

【在 t**********s 的大作中提到】

: 那么下面的mechanism又是什么呢？
: A mechanism must be provided to ignore a request to add integer i to S in
: the case where S alrady contains i.
: 是不是这样就可以了：
: if A(h(i))!=empty then return error
: 如果小集合与大集合相等，那么这个哈希表的具体实现就用arrar怎么样？

S*n2007-02-01 08:02

10 楼

bitset太language specific了，只适用于C/C++。算法的东西，稍微general一点好。

【在 t*******t 的大作中提到】

: how about bitset?

t*t2007-02-01 08:02

11 楼

bitset is used in java too