A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

What will be the size of the hash table in case of linear probing, if our hash function does something like this, value%20 ?

  • This Question is Closed
  1. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Can you be more specific? What language are you coding in? What are you trying to do?

  2. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i'm coding in C++ . I'm just preparing for my exam so i want to know that if the hash function does something of this sort, value%20 , then what should be the size of our hash table , if we are to insert and search the value using linear probing.

  3. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    %20 would generate values in between 0 and 19 , so should the size of the hash table be 20 or double of that, 40 ?

  4. shadowfiend
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    It depends on how you implement the linear probing and how many total items you want your hash table to hold. If you're implementing linear probing by basically leaving an empty spot adjacent to each spot you'll try to put an item in first, then yes, it'll have to be size 40. Also, if you want more than 40 items in the table, then you'll need your table to be bigger than 40 slots.

  5. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    It'll be of size 20, not 40. Having an array size of 40 when your hash function only hashes to slots 0-19 would be pointless. The only way linear probing affects this question is that you wouldn't have to worry about small array sizes as would be the cash with quadratic probing. Just remember, the point of a hash function is to distribute keys and evenly as possible. If you are hashing to slots 0-19 and used an array of size 40, the keys are on average only being distributed to the first half of all the available space, meaning more collisions and decreased performance

  6. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.