双重搜索数据结构 [英] Dual search data structure
问题描述
大家好，
是否有人知道我可以搜索的任何数据结构
关键和价值同样快？虽然我可以使用哈希值，但是我可以只用键盘上的常量时间而不是值来搜索
。如果我想
搜索该值，那么我将不得不进行线性搜索。
我有的另一个相关问题是
1.是否任何人都知道一个不会导致冲突的哈希函数
以及时间复杂度是多少？
2.为什么增加哈希数组的大小呢？你需要
创建一个更大的数组然后重新散列旧数组中的键吗？在我的
视图中可能有更好的策略来增长数组，或者可能不是
只是增长数组而不是使用关联指针存储另一个
哈希数组，它也可以包含用完全不同的
哈希函数映射的键。这样，哈希的大小可以在没有太多内存开销的情况下增长，也不需要重新插入。我不是很好
确定这是否是标准做法。如果有人可以给我一些链接或类似文献的指示，那么它将会给我很多帮助。
任何帮助表示赞赏，
谢谢，
Divick
Hi all,
does any one know of any data structure in which I can search
the key and value equally fast? Though I could use hashes, but I can
only search in constant time on key but not on value. If I want to
search the value then I will have to do a linear search.
Another related questions I have are
1. Does any one know a hash function that does not lead to collisions
and what is it time complexity?
2. Why is it that to grow the size of an hash array do you need to
create a bigger array and then rehash the keys in the old array? In my
views there could be better strategies to grow the array, or may be not
just grow the array instead use associated pointers to store another
hash-array which can also contain keys mapped with totally different
hash function. This way the size of hash can be grown without much
memory overhead and also re-insertion is not needed. I am not very
sure that whether this is a standard practice or not. If somebody can
throw me some links or pointers to similar literature then it would
help me a lot.
Any help is appreciated,
Thanks,
Divick
推荐答案
Divick写道：
Divick wrote:
1.是否有人知道不会导致碰撞的哈希函数
以及时间复杂度是多少？
1. Does any one know a hash function that does not lead to collisions
and what is it time complexity?
哪有这回事。良好的哈希函数是那些以最快的方式查找碰撞是使用暴力的方法。对于实际的
目的，任何着名的都可以。
http://en.wikipedia.org/wiki/Cryptog..._hash_function
Ryan
There is no such thing. Good hash functions are those for which the
fastest way to find a collision is to use brute force. For practical
purposes, any of the famous ones are fine.
http://en.wikipedia.org/wiki/Cryptog..._hash_function
Ryan
Divick写道：
大家好，
任何人都知道我可以搜索任何数据结构的关键和价值同样快？虽然我可以使用哈希，但我只能在关键但不是在价值上搜索恒定时间。如果我想搜索该值，那么我将不得不进行线性搜索。
Hi all,
does any one know of any data structure in which I can search
the key and value equally fast? Though I could use hashes, but I can
only search in constant time on key but not on value. If I want to
search the value then I will have to do a linear search.
我不久前有类似的问题...我的解决方案是包装一个
std :: map< Key，Obj *>和std :: multiset< Obj *，ptr_less< Obj> >在我自己的
级。这笔交易是我可以从对象中获取Key，所以
multiset在地图上作为索引。
hth
~KS
I had a similar problem not too long ago... my solution was to wrap a
std::map<Key, Obj*> and a std::multiset<Obj*, ptr_less<Obj> > in my own
class. The deal was that I could get the Key from the object, so the
multiset worked as an index onto the map.
hth
~KS
Divick写道：
大家好，
任何人都知道任何数据结构在哪些方面我可以同样快速地搜索关键和价值？
如果你在说标准C ++，那么''std :: set''是唯一这样的结构
，因为值_is_是关键字它。如果你不是在谈论标准的C ++，那么你会在一个错误的新闻组中。一般编程问题应该是
可能是''comp.programming''。
[...]
Hi all,
does any one know of any data structure in which I can search
the key and value equally fast?
If you''re talking standard C++, then ''std::set'' is the only such structure
because the value _is_ the key in it. If you''re not talking standard C++,
then you''re in a wrong newsgroup. General programming questions should be
probably addressed to ''comp.programming''.
[...]
V
V
这篇关于双重搜索数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
