使用哪种散列函数？ [英] Which hashing function to use?
问题描述
您好，
我需要对相对较短的字符串使用散列函数（大约16
字符或更少）。需要通过哈希访问的数据只是一个
simple int。我只需要在二维矩阵中查找值，每次我遇到一对这些字符串的时间。
我想保留代码为简单和标准，因为
可能，但同时要有一个合理的性能。
在查看我的系统上的文档时，我发现了一些不同的
实现：
- 来自< search.h>的研究
- 来自< search.h>的研究
- bsearch from< stdlib.h>
你会推荐哪一个？或者也许是完全不同的东西？
现在我只是使用Perl进行散列:-)这很好，但我会
喜欢小巧，高效， ANSI C程序。
问候，
1月
< blockquote> 11月16日下午3:42，1月Weiner< january.wei ... @ gmail.comwrote：
您好，
我需要对相对较短的字符串使用散列函数（大约16
字符或更少）。需要通过哈希访问的数据只是一个
simple int。我只需要在二维矩阵中查找值，每次我遇到一对这些字符串的时间。
我想保留代码为简单和标准，因为
可能，但同时要有一个合理的性能。
在查看我的系统上的文档时，我发现了一些不同的
实现：
- 来自< search.h>的研究
- 来自< search.h>的研究
- bsearch from< stdlib.h>
你会推荐哪一个？或者也许是完全不同的东西？
现在我只是使用Perl进行散列:-)这很好，但我会
喜欢小巧，高效， ANSI C程序。
你的帖子在新闻中更热门：comp.programming {follow-up set}。
我不认为你的问题还有答案。它将取决于
很多东西。
例如，字符串是否为永不改变的静态集？如果是这样，
那么你可以选择一个完美的哈希。
有一个字符串搜索算法比哈希表更快（参见
Sedgewick）。
你需要保存数据（例如在
磁盘上设置的键/值对）？
我需要一个哈希，我应该使用哪个？是一个如此开放的问题，任何
简单答案都可能缺乏。
user923005< dc ***** @ connx.comwrote ：
你的帖子在新闻中更热门：comp.programming {follow-up set}。
嗯，事实并非如此。不是100％。原因是我正在寻找
这是C标准的一部分，并且在C中使用很简单。
当我问一个问题时你会怎么想？这样的问题在
comp.programming中？有些聪明人会将Followup-To设置为comp.lang.c
:-P，这就是将要发生的事情。最后，原因是我不是一个计算机科学家，而且需要非常实用的建议。实用的建议
我总是在comp.lang.c上有很多东西:-)请注意，你会在这个常见问题解答中找到关于不同散列算法的讨论小组
- 但是，我并不完全理解它（否则我不会问问题是否是
）。
我认为您的问题还没有答案。它将取决于
很多东西。
例如，字符串是否为永不改变的静态集？如果是这样，
那么你可以选择一个完美的哈希。
有一个字符串搜索算法比哈希表更快（参见
Sedgewick）。
好吧，因为我不是计算机科学家，我会尝试在某个地方查找它。
同时，其中哪一个是标准C库的一部分？
您是否需要保留数据（例如在
磁盘上设置的键/值对）？
不，如果我需要，我会选择DBM或SQL。
我需要哈希，我应该使用哪个？是一个如此开放的问题，任何
简单的答案都可能缺乏。
我需要哈希，我应该使用标准C库中的哪一个
是一个更具体的问题，不是吗？
亲切的问候，
1月
1月Weiner写道：
user923005< dc ***** @ connx.comwrote：
> Your帖子在新闻中更为热门：comp.programming {follow-up set}。
[...]
> ;我需要一个哈希，我应该使用哪个？是一个如此开放的问题，任何简单的答案都可能缺乏。
我需要哈希，我应该使用标准C库中的哪一个
是一个更具体的问题，不是吗？
是的，确实如此。答案是，
标准C库中没有哈希函数。
-
Keith Thompson（The_Other_Keith ）< ks *** @ mib.org>
在圣地亚哥地区寻找软件开发工作。
我们必须做点什么。这是事情。因此，我们必须这样做。
- Antony Jay和Jonathan Lynn，是部长
Hello,
I need to use a hashing function for relatively short strings (roughly 16
characters or less). The data that needs to be accessed via hash is just a
simple int. I just need to look up values in two dimensional matrices each
time that I encounter a pair of these strings.
I would like to keep the code as simple and standard as
possible, but at the same time to have a reasonable performance.
While looking through the docs on my system I found a few different
implementations:
- hsearch from <search.h>
- tsearch from <search.h>
- bsearch from <stdlib.h>
Which one would you recommend? Or maybe something completly different?
Right now I just use Perl to do the hashing :-) this is nice, but I would
love to have a small, efficient, ANSI C program.
Regards,
January
On Nov 16, 3:42 pm, January Weiner <january.wei...@gmail.comwrote:Hello,
I need to use a hashing function for relatively short strings (roughly 16
characters or less). The data that needs to be accessed via hash is just a
simple int. I just need to look up values in two dimensional matrices each
time that I encounter a pair of these strings.
I would like to keep the code as simple and standard as
possible, but at the same time to have a reasonable performance.
While looking through the docs on my system I found a few different
implementations:
- hsearch from <search.h>
- tsearch from <search.h>
- bsearch from <stdlib.h>
Which one would you recommend? Or maybe something completly different?
Right now I just use Perl to do the hashing :-) this is nice, but I would
love to have a small, efficient, ANSI C program.Your post is more topical in news:comp.programming {follow-ups set}.
I do not think that your problem has an answer yet. It will depend on
lots of things.
For instance, are the strings a static set that never changes? If so,
then a perfect hash is your choice.
There are string searching algorithms faster than a hash table (See
Sedgewick).
Do you need to preserve the data (e.g in a key/value pair set on
disk)?
"I need a hash, which should I use?" is such an open question that any
simple answer will probably be lacking.
user923005 <dc*****@connx.comwrote:Your post is more topical in news:comp.programming {follow-ups set}.Well, it is not. Not 100%. The reason being that I am looking for
something that is part of the C standard and that is simple to use in C.
What do you think happens when I ask a question like that in
comp.programming? Some wise guy will set the Followup-To to comp.lang.c
:-P, that''s what would happen. Finally, the reason is that I am not a
computer scientist and need, hm, very practical advice. Practical advice
is something that I always got plenty on comp.lang.c :-) Note that you will
find a discussion on different hashing algorithms in the FAQ of this group
-- however, I do not fully understand it (otherwise I would not be asking
the questions).
I do not think that your problem has an answer yet. It will depend on
lots of things.
For instance, are the strings a static set that never changes? If so,
then a perfect hash is your choice.
There are string searching algorithms faster than a hash table (See
Sedgewick).OK, as I am not a computer scientist, I will try to look it up somewhere.
Meanwhile, which of that is a part of standard C libraries?
Do you need to preserve the data (e.g in a key/value pair set on
disk)?Nope, I would go for DBM or SQL if I needed that.
"I need a hash, which should I use?" is such an open question that any
simple answer will probably be lacking."I need a hash, which of the ones in the standard C libraries should I use"
is a more specific question, is it not?
Kind regards,
January
January Weiner wrote:user923005 <dc*****@connx.comwrote:>Your post is more topical in news:comp.programming {follow-ups set}.
[...]
>"I need a hash, which should I use?" is such an open question that any
simple answer will probably be lacking.
"I need a hash, which of the ones in the standard C libraries should I use"
is a more specific question, is it not?Yes, it is. And the answer is, there are no hash functions in the
standard C library.
--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Looking for software development work in the San Diego area.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
这篇关于使用哪种散列函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
