hashtabe，hashmap ...为什么他们使用哈希算法 [英] hashtabe,hashmap...why they use Hash algorithm

问题描述

如果是二分法生成一个整数，那么每个字符实际上对应一个assiic



如

ac = 6163

bb = 6262

所以即使没有散列哈希算法也不会重复。而且，哈希算法不能保证不会发生冲突。那种情况，为什么要使用哈希呢???寻求了解原因。


谢谢

If it is for dichotomy to generate an integer，then each character actually corresponding to a assiic

Such as
ac = 6163
bb = 6262
So even without hash hashing algorithm it will not repeat. Moreover, hash algorithm can not guarantee that no collision. That case, why use hash it??? Seek to understand the reasons.

THANKS

推荐答案

这是一个缩小搜索范围的优化。它的作用与现实生活中的普通词典相同。字典制作者可以在书中添加单词，因为它们没有任何顺序。这使得很难找到单词，因为您需要从前到后进行线性搜索。相反，他们按照所有词典的方式进行，按字母顺序对单词进行排序，字母表中的每个字母都有自己的部分。例如，以S开头有多个单词，但您可以跳过除S以外的所有单词。你必须承认这会使它变得更好。然后你去那里。这同样如此。它是一个存储桶列表，在碰撞时在同一存储桶中存储多个值。但这并不重要，因为只需要搜索存储桶而不是所有项目的数组。希望我的例子能让它更加清晰。



祝你好运！

It is an optimization to narrow down the search field. It works just the same as a normal dictionary in real life. Dictionary makers could add words to the book as they go without any order what so ever. This makes it hard to find words because you would need to do a linear search from front to back. Instead they did as it is done in all dictionaries, they alphabetically sorted the words and each letter in the alphabet got its own section. There is more than one word starting with an "S" for example, but you can skip all the words starting with anything other than an "S". You must admit that makes it a whole lot better. You then go from there. The same goes here. It is a bucket list that stored multiple values in the same bucket on collisions. But that doesn't matter because then only the bucket needs to be searched instead of an array of all the items. Hopefully my example makes it more clear.

Good luck!

Hashing用于在数组桶中分配值，每个桶包含一个条目。选择哈希算法（或者应该）来提供在整个桶范围内分配条目的好机会，并且根据可用的桶的数量而变化。



在你的例子中只有两个字符，根本不用哈希值似乎很傻 - 但如果你不这样做，那么你需要的桶数足以容纳几乎所有可能的条目：64K。这很愚蠢，因为你不太可能产生那么多的字符串。如果您使用原始哈希，例如将两个字节加在一起并获取结果的低八位，那么您可以只分配256个桶，从而节省大量内存。



除此之外还有很多东西要散列，而且要覆盖太多，所以我建议你从Wiki开始：http://en.wikipedia.org/wiki/Hash_table [ ^ ]提供了很好的概述。

Hashing is used to distribute values across an "array of buckets", with each "bucket" containing a single entry. Hashing algorithms are (or should be) selected to give a good chance of distributing entries across the whole range of "buckets" and will vary according to teh number of such buckets available.

In your example with just two characters, it seems silly to hash the value at all - but if you don't then the number of buckets you need is enough to hold nearly all the possible entries: 64K. Which is silly, because it is very unlikely that you will generate that number of strings. If instead you use a primitive hash such as adding the two bytes together and taking the low eight bits of the result, then you can allocate just 256 buckets, saving a huge amount of memory.

There is a lot, lot more to hashing than this, and much too much to cover here, so I would suggest you start with Wiki: http://en.wikipedia.org/wiki/Hash_table[^] which provides a good overview.

由于算法的组合爆炸。

这篇关于hashtabe，hashmap ...为什么他们使用哈希算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！