Hash Table Size

How to choose size of hash table?

Suppose I have 200.000 of words.

A good rule of thumb is to keep the load factor at 75% or less (some will say 70%) to maintain (very close to) O(1) lookup. Assuming you have a good hash function.

Based on that, you would want a minimum of about 266,700 buckets (for 75%), or 285,700 buckets for 70%. That's assuming no collisions.

266,700 = 200000 x 100/75

285,700 = 200000 x 100/70

Hash table size

• By "size" of the hash table we mean how many slots or buckets it has
• Choice of hash table size depends in part on choice of hash function, and collision resolution strategy
• But a good general “rule of thumb” is:
• The hash table should be an array with length about 1.3 times the maximum number of keys that will actually be in the table, and
• Size of hash table array should be a prime number
• So, let M = the next prime larger than 1.3 times the number of keys you will want to store in the table, and create the table as an array of length M
• (If you underestimate the number of keys, you may have to create a larger table and rehash the entries when it gets too full; if you overestimate the number of keys, you will be wasting some space)

How to find whether a given number is prime or not?

A number is greater than 1 is called a prime number, if it has only two factors, namely 1 and the number itself.

Prime numbers up to 100 are:2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Procedure to find out the prime number

Suppose A is given number.

Step 1: Find a whole number nearly greater than the square root of A. K ¿ square root(A) Step 2: Test whether A is divisible by any prime number less than K. If yes A is not a prime number. If not, A is prime number.

Example:

Find out whether 337 is a prime number or not?

Step 1: 19 ¿ square root (337) Prime numbers less than 19 are 2, 3, 5, 7, 11, 13, 17 Step 2: 337 is not divisible by any of them

Therefore 337 is a prime number

int prime(int n) {
int i;
        // Corner cases
if(n<=1)
return 0;
if(n<= 3)
return 1;

if(n%2 == 0 || n%3 == 0 || n%5 == 0) {
return 0;
}

for(i=5;i*i <=n;i++) {
if(n%i == 0)
return 0;
}

return 1;
}