2

I am implementing the hash table for load at the moment, but I don't know how I should figure out how many buckets I should be using. Is there a 'rule' for this when creating hash functions, or is it just the more, the faster? If it is case 2, what would be a good amount that would have fast loading times?

1 Answer 1

6

It depends. There are a lot of factors involved. Does the hash function have a limited number of possible values (like 26 if it's based on the first letter)? How much data are you processing? How much memory is available to store these hash table elements? etc.

If you have a hash function that is capable of an unlimited number of hash values (as a practical matter), then it becomes more of a case of available resources and diminishing returns.

For available resources, you have to consider how much memory the hash table will consume. Essentially, you're looking at (sizeof(pointer) * number of hash values) + (number of nodes * sizeof(node) ). The first part of this could potentially go way beyond the second part in trying to improve efficiency. You need to make sure that the memory resources are available to support this, as well as whatever else the computer is doing.

Then, the law of diminishing returns comes into play. Ideally, each word would get a unique hash value. The problem there is that it is practically impossible to have a hash that generates a perfect hash table where every word has a unique hash value and there are no gaps or empty hash values in the table. That means that, from a practical standpoint, there will be empty hashes. So here's the issue. The goal is to have the length of each and every linked list as short as possible. To get this, the number of hashes has to go up. The larger it gets, the more efficient the search process gets, but the amount of improvement gets smaller and the number of unused hashes gets linearly larger. At the same time, memory resource usage gets less and less efficient as the number of unused hashes goes up. Eventually, the loss in resource efficiency outweighs the gains in search efficiency and the gain in performance is no longer worth the resources used.

Because of this, it's usually just a matter of testing various values until you arrive at a happy medium that gives the efficiency desired, but doesn't needlessly waste resources. Each situation is different, but you should consider 2 to 3 times the number of data elements to be hashed as a thumbnail starting target and test in both directions - larger and smaller - and see what happens.

That's it in a nutshell. Does this help?

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

1
  • I'll add this. Is the goal maximum speed, maximum efficiency in memory usage, or a balance? And which factor does this lean towards? If the goal is flat out speed at the expense of memory, then crank the number up until the max length of any linked list is 3 or less. If max memory efficiency is the goal, then the number of buckets is tuned so that there are no empty buckets, or maybe just a few. Most of the time, it's about getting the speed up to an acceptable level and keeping down the wasted memory devoted to empty buckets. Then, it's a judgement call on where to balance these factors.
    – Cliff B
    Jun 14, 2020 at 2:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .