Databases
StackOverflow2013
Postsdbo
POHow to get the optimal number to use in hashtable?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to get the optimal number to use in hashtable?
    primarykey
    data
    text
    <p>As the question states, how calculate the optimal number to use and how to motivate it?</p> <p>If we are going to build an hashtable which uses the following hash function:</p> <p>h(k) = k mod m, k = key</p> <p>So some sources tells me: </p> <ol> <li>to use the number of elements to be inserted as the value of m</li> <li>to use a close prime to m</li> <li>that java simply use 31 as their value of m</li> <li>And some people tell me to use the closed prime to 2^n as m</li> </ol> <p>I'm so confused at this point that I don't know what value to use for m. Like for instance if we use the table size for m then what happens if we want to expand the table size? Will I then have to rehash all the values with the new value of m. If so why does Java use simply 31 as prime value for m.</p> <p>I've also heard that the table size should be two times bigger then the total elements in the hashtable, that's for each time it rehashes. But how come we for instance use m=10 for a table of 10 elements when it should be m=20 to create that extra empty space?</p> <p>Can someone please help me understand how to calculate the value of m to use based on different scenarios like when we want to have a static (where we know that we will only insnert like 10 elements) or dynamic (rehash after a certain limit) hashtable.</p> <h2>Lets illustrate my problem by the following examples:</h2> <p>I got the values {1,2,...,n}</p> <p>Question: What would be a optimized value of m if I must use the division by mod in my hashfunction?</p> <p><strong>Senario 1: n = 100?</strong></p> <p><strong>Senario 2: n = 5043?</strong></p> <p><strong>Addition question:</strong> Would the m value hashfunction be different if we used a open or closed hashtable?</p> <p>Note that i'm now not in need to understand hashtable for java but hashtable in general where I must use a divsion mod hashfunction.</p> <p>Thank you for your time!</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USAlexander
    1. USAlexander
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow to get the optimal number to use in hashtable?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow to get the optimal number to use in hashtable?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COJava uses whatever you tell it to by overriding `hashCode`. The typical idiom involves iterated *multiplication* by 31 when combining the hashcodes of individual object attributes, and doesn't use modulus at all.
      singulars
      1. POHow to get the optimal number to use in hashtable?
      1. USMarko Topolnik
    2. COYes, that answers that question but how about if we make it more generalised in the context of hashfunction with division of mod. Would 31 be an ideal prime number to use for an n < 31, if so what if the size of n is larger the 31 what will it then be?
      singulars
      1. POHow to get the optimal number to use in hashtable?
      1. USAlexander
    3. COThe hash function itself has nothing to do with the size of the hashtable. Its main desirable characteristic is that it disperses the values well. Note that in Java, the hash function belongs to the key object, whereas the hashtable size is obviously encapsulated in a totally different, independent class. You can't optimize hashCode for a specific hashtable size.
      singulars
      1. POHow to get the optimal number to use in hashtable?
      1. USMarko Topolnik
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload