programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Tim Cooke
• Campbell Ritchie
• Paul Clapham
• Ron McLeod
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• Rob Spoor
• Bear Bibeault
Saloon Keepers:
• Jesse Silverman
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• Carey Brown
Bartenders:
• Piet Souris
• Al Hobbs
• salvin francis

# Using Binary search trees to sort collision in hash function

Greenhorn
Posts: 7
• Number of slices to send:
Optional 'thank-you' note:
This is the original problem:

Given a hash function h(x) = x mod 3, insert entries with keys 13, 22, 8, 16, 33, 52, 43, 28, 45, 23, 11, 15, 9, 2, 20, 30, 19, 50 to the hash table. Use binary search trees to solve hash collision, where each cell of the hash table stores the root of a binary search tree. Also draw the trees after removing keys 43, 30 and 2.

I'm unsure if I have the correct answer to this Homework problem. If I'm wrong please direct me in the right direction.

|0  |1  |2 | 3 | 4|  5| 6 | 7 |8| 9 |10|11|12|13|14 |15|16|17|

|45|13|22|16|52|43|28|19|8|33|23|11|2 |20|50 |15|9|30|

Master Rancher
Posts: 4509
38
• Number of slices to send:
Optional 'thank-you' note:
Is this a java programming problem?  Do you have java code you are having problems with?

Patty Lebowski
Greenhorn
Posts: 7
• Number of slices to send:
Optional 'thank-you' note:

Norm Radder wrote:Is this a java programming problem?  Do you have java code you are having problems with?

There is no code, it's just working out the logic of the problem on paper.

Master Rancher
Posts: 4509
38
• Number of slices to send:
Optional 'thank-you' note:
ok, I was just confused.  This section of the forum is for beginning java programmers that have problems with their code.  So naturally I was looking for your code that needed help.

I don't know what section of the forum this question would fit in better.

Patty Lebowski
Greenhorn
Posts: 7
• Number of slices to send:
Optional 'thank-you' note:

Norm Radder wrote:ok, I was just confused.  This section of the forum is for beginning java programmers that have problems with their code.  So naturally I was looking for your code that needed help.

I don't know what section of the forum this question would fit in better.

I ran into the same issue. I posted it here because I figured it would be the 'best' fit

Master Rancher
Posts: 4509
38
• Number of slices to send:
Optional 'thank-you' note:
I still don't understand how your question is related to java programming.   If you are not planning to write a java program to solve the problem, why ask questions in a java programming section?

Marshal
Posts: 74384
334
• Number of slices to send:
Optional 'thank-you' note:
Let's have a bit more explanation of the problem. Maybe it can go into the General computing forum later.
PL: please tell us what sort of algorithm you are going to use to fill your trees.

Patty Lebowski
Greenhorn
Posts: 7
• Number of slices to send:
Optional 'thank-you' note:
I should have pointed out I'm in a java programming class, this is the logic for an assignment to be done on paper. There is no code yet. I would like to make sure I understand how to do the logic of two data structures combined into one.

I'm very new here so I apologize for the mistakes I've made.

I just wanted to see if I could understand this better before I go to my professors office hours.

Sheriff
Posts: 7111
184
• Number of slices to send:
Optional 'thank-you' note:
I don't think the output is the what is needed so much as the logic behind the output.  Without writing code, what would be the logical steps you would take to produce the correct output?

Campbell Ritchie
Marshal
Posts: 74384
334
• Number of slices to send:
Optional 'thank-you' note:
Start trying it out with the following has function:
h = x
Nice and simple. You now have thirty‑something numbers each with a hash. Put each into a tree and see what sort of tree you get. Show us the results. You will find it easier if you wrap the output in [code=text]&nbsp;...[/code] tags. Use the /|\ keys for the branches of the tree and spaces to move to the right. Use Text in the dropdown list next to the code button and write &nbsp; by hand on the first line only.
I'll give you a startNow use the hash function you were given and try it for these numbers: 13, 22. You will have to consider what algorithm you are going to use because 13 and 22 will return the same hash.

And, to General Computing we shall go.

Sheriff
Posts: 16675
278
• Number of slices to send:
Optional 'thank-you' note:

Patty Lebowski wrote:
I'm unsure if I have the correct answer to this Homework problem. If I'm wrong please direct me in the right direction.

|0  |1  |2 | 3 | 4|  5| 6 | 7 |8| 9 |10|11|12|13|14 |15|16|17|

|45|13|22|16|52|43|28|19|8|33|23|11|2 |20|50 |15|9|30|

That doesn't look right to me.

Self-check:
1. What does a hash table look like? Does your answer look like one?
2. What does a binary search tree look like? Does your answer look like it's using binary search trees?
3. How many unique hash codes will you get if the hash function is h(x) = x mod 3?  Does your answer show this many hash codes? What are those hash codes? (HINT: the given hash function produces less than 5 unique hash codes)

You should be able to tell whether or not your answer is correct based on these self-check questions.

 You showed up just in time for the waffles! And this tiny ad: Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton