In this task we will get first experience with Linear Hashing. We want to store a sequence of elements into a hash-structure and afterwards delete some of the entries. Before you start, you have to add another index at the end of the list. Convert your own birthday into an index, by building the checksum between day, month and year, where you add the day, the month and the checksum of the year like it is shown in the 3 examples below:

f(27.01.2021) := 27 + 01 + 2 + 0 + 2 + 1 = 33

f(01.10.1995) := 01 + 10 + 1 + 9 + 9 + 5 = 35

f(31.12.2000) := 31 + 12 + 2 + 0 + 0 + 0 = 45

Afterwards add the new created index to the end of the following sequence: 22, 8, 17, 55, 65, 78, 23, 30, 1 Hint: If the index of your birthday is the same as an already existing value in the sequence, you can add 1 until you get a new value!

(a) Explain why using the scheme described in task 1 could lead to errors, when calculating the index value for different birthdays!

(b) Start with M = 2 and level = 0 and use the hash function h0(k) = k% M, to insert the sequence into a linear hash structure: Show the hash structure after each insertion!

(c) Delete the following sequence of indexes from your hash structure:

, 17, 22, 30

Show the hash structure after each deletion!

Task 2

(a) Give respectively 2 advantages and disadvantages between linear hashing and extendible hashing.

(b) Explain in your own words, how a search operation is done in a linear hashing structure.

(c) Give an explicit example of when to use linear hashing over extendible hashing. Be specific about performance and storage regarding the inserting, deleting and searching operations.