Handling mismatches

[Anthony White]

If we were to insert a book with the same ID but the titles are
different, what would you like us to do? Or how about when the
situation is reversed and we have the same title but different ID?

[Justin Scott]

Another possible mismatch is when you try to check out a book that is
already checked out, or return a book that is already marked available.

[Lucas Hawk]

I am having a hard time understanding collisions in this specific hash table implementation.

 

How would there ever be a collision? If you take the IDmodSIZE hash function, and get some value X, that is just the base address for the linked list right? So it would just be added to a dynamic linked list? How would a collision ever happen, if the bucket never fills (memory limitations ignored...) ?

 

For example -

Suppose we have two books, and a hash table of size 5. One book is ID 06, and the other is ID 11. The first would be placed in bucket 1's linked list. The second would also be assigned to bucket 1, and would just get added to the linked list. How does a collision happen?

Even if it were the same exact book - unless you did a check through the linked list first to prevent duplicate entries, wouldn't it just get added to the list twice??

The only reason I ask is the HW assignment implies we would need to output "Collision" when one happens, but I dont understand how one would ever occur...

 

-Luke

 

 

On Mon, Nov 29, 2010 at 1:13 PM, Justin Scott <jsc...@gmail.com> wrote:

Another possible mismatch is when you try to check out a book that is
already checked out, or return a book that is already marked available.

--
Rev. Lucas A Hawk
W Dallas Universal Church of Life
2210 W Dallas
Houston, TX 77019

[Josh]

The collision occurs when your hash function h(x) returns the same
hash table index for different keys: you have multiple items being
stored in the same index of a hash table. In this assignment, we are
handling the collisions by using linked lists.

So, in your example, inserting book id 06 and book id 11 causes a
collision. However, you solve it by using a linked list instead of
storing the item directly in the array.

Josh

On Nov 29, 2:02 pm, Lucas Hawk <lukeh...@gmail.com> wrote:
> I am having a hard time understanding collisions in this specific hash table
> implementation.
>
> How would there ever be a collision? If you take the IDmodSIZE hash
> function, and get some value X, that is just the base address for the linked
> list right? So it would just be added to a dynamic linked list? How would a
> collision ever happen, if the bucket never fills (memory limitations
> ignored...) ?
>
> For example -
> Suppose we have two books, and a hash table of size 5. One book is ID 06,
> and the other is ID 11. The first would be placed in bucket 1's linked list.
> The second would also be assigned to bucket 1, and would just get added to
> the linked list. How does a collision happen?
> Even if it were the same exact book - unless you did a check through the
> linked list first to prevent duplicate entries, wouldn't it just get added
> to the list twice??
>
> The only reason I ask is the HW assignment implies we would need to output
> "Collision" when one happens, but I dont understand how one would ever
> occur...
>
> -Luke
>

[Lucas Hawk]

Oh.

 

So we would output "COLLISION" but this would not be an error, and everything would still work?

Would we output "COLLISION" and then "SUCCESSFUL"?

[Mario Navas]

Hi,

Yes, when you get a COLLISION, you still have an element inserted.

For the books, consider the ID as an unique identifier. You don't need
to check the name of the book. When you want to insert, whether the
book name is equal or not, if the id of the new item is already in the
list. It should not be inserted.

For trying to check out a book that is already checked out. Or return
a book that is already returned. We won't test this. However, just in
case your program didn't execute some command (Just assuming a bug in
your program), then if you try to check out a book already checked
out, it remains checked out. The same for available books, if they are
returned, they remain returned.

Let me know if there are further questions, We talked about all of
this on the class Tuesday. Sorry if it wasn't clear.

Regards,

Mario