0
$\begingroup$

What is numerically the best value or range of values used as a reference for the load factor used in the hash table? What is the pseudo-code of the “rehashing” method, which is applied when many elements are added to a hash table and the load factor increases and the best value used as a reference is exceeded.

$\endgroup$
2
  • 2
    $\begingroup$ Welcome to Computer Science! Please ask one question per on post. You are also expected to show what research you have done and what are your thoughts or what you have done. That also help draw more better answers faster. $\endgroup$
    – John L.
    Apr 23, 2022 at 13:47
  • $\begingroup$ Partly related question: cs.stackexchange.com/questions/149496/… $\endgroup$
    – Pseudonym
    Sep 23, 2022 at 6:40

2 Answers 2

0
$\begingroup$

I’ll suggest to do some work yourself.

When you look up, or add, or remove a value from the hash table, what operations would be performed with different load factors, with which probability, what the cost of these operations is, and what the memory usage would be on average.

That should give you some idea, which you then confirm with actual measurements.

You will also have a hysteresis: You have one load factor that is considered "too high" and another that is considered "too low". You resize the hash table if your load factor is too high or too low. Having only one load factor has the risk that you resize the hash table if the load factor becomes too high, then you remove one item and resize again because it is too low, add one item and resize and so on. You'd pick the new table size so that the load factor is somewhere in the middle, so you'd have to add or remove many many items before you want to resize again.

Last thing: Some hash tables have an interface where you can set the size beforehand. Say you have 10,000 items, then you create the hash table, big enough to have a good load factor if filled with 10,000 items, and add the items, so you avoid multiple resizing operations. Typically implementations assume that you will add a few more items than planned and are careful with resizing.

Important note: You don't write code for hash tables just for fun. For example, if you write code for MacOS or iOS using hash tables, there is ONE implementation that you will use, provided by the OS, and written by someone who knows a lot more about optimal implementations of hash tables than I ever will. Sure, you can write an implementation for educational reasons, but you won't come near a good implementation.

$\endgroup$
-1
$\begingroup$

According to this, Python doubles the hash table when the load factor reaches $2/3$. This mentions the probe sequence used by Python for implementing dictionaries using hash tables.

$\endgroup$
2
  • 2
    $\begingroup$ Thanks for you recent answers! On the other hand, please consider not encouraging posts that do not demonstrate reasonable search and/or research attempt. The goal of this site is to build a good question and answer knowledgebase instead of repeating/linking to answers that can be found elsewhere easily. This answer means, to me mostly, that the OP is unable to search the internet and that you are good at searching. $\endgroup$
    – John L.
    Apr 23, 2022 at 18:17
  • $\begingroup$ Note: Immediately after resizing, your load factor is 1/3rd. If you remove items, you will want to reduce the size if the load factor is much less than 1/3rd. $\endgroup$
    – gnasher729
    Oct 17, 2023 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.