Question about linear hashing

quan zhang

unread,

May 6, 2021, 10:16:29 AM5/6/21

to COMP9311-21T1

Hi tutors,

Sorry to bother you. I have a question about linear hashing. For example, I want to insert 43, as shown in the first picture.

For second and third picture, which is right? And why?

Kind regards,

Quan

Victoria Ho

unread,

May 6, 2021, 10:33:53 AM5/6/21

to COMP9311-21T1

Both are, in a sense. But it depends on what the value of n ('next') is. Once n reaches the bucket with that overflow page containing 43, it'll split into what's shown.

2021年5月7日金曜日 0:16:29 UTC+10 quan.z...@gmail.com:

Victoria Ho

unread,

May 6, 2021, 10:37:55 AM5/6/21

to COMP9311-21T1

Also, unlike with extendable hashing, you won't be doubling directories off a split. With linear hashing you can only add one bucket at time, so it will have to be assumed, in your case, that there were extra insertions after 43.

2021年5月7日金曜日 0:33:53 UTC+10 Victoria Ho:

quan zhang

unread,

May 6, 2021, 1:33:43 PM5/6/21

to COMP9311-21T1

Sorry, I still have a confusion. If I only insert 43, what is the final value of next? Is 3?

Victoria Ho

unread,

May 7, 2021, 2:19:44 AM5/7/21

to COMP9311-21T1

You always start from the top and work your way to the last overflow. If you only insert 43, then your last n will be 3 (we start from n = 0).

2021年5月7日金曜日 3:33:43 UTC+10 quan.z...@gmail.com:

Reply all

Reply to author

Forward