• Post Reply Bookmark Topic Watch Topic
  • New Topic

Using Binary search trees to sort collision in hash function  RSS feed

 
Patty Lebowski
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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|
 
Norm Radder
Ranch Foreman
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is this a java programming problem?  Do you have java code you are having problems with?
Please post the code (in code tags) and ask any questions you have about the code.
 
Patty Lebowski
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Norm Radder wrote:Is this a java programming problem?  Do you have java code you are having problems with?
Please post the code (in code tags) and ask any questions you have about the code.


There is no code, it's just working out the logic of the problem on paper.
 
Norm Radder
Ranch Foreman
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Norm Radder
Ranch Foreman
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Campbell Ritchie
Marshal
Posts: 55772
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Knute Snortum
Sheriff
Posts: 4087
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 55772
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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] ...[/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   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.
 
Junilu Lacar
Sheriff
Posts: 11165
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!