Hashing

[snowteo]

Hi,I have to do this exercises can you help me:
1)Write a program to implement exetendible hashing.If the table is small
enough to fin in main memory,how does its performance compare with open and
closed hasing?
2)A basic program consists of a series of statements,each of which is
numbered in ascending order.Control is passed by use of a goto or gosub and
a statement number.Write a program that reads in a legal BASIC program and
renumbers the statements so that the first starts at number f and each
statement has a number d higher than the previous statement.You may assume
an upper limit of n statements,but the statement numbers in the input might
be as large as a 32-bit integer.Your program must run in linear time.
Of it I have resolved many others,but these two I just do not succeed to
make them.Thank you very much

 

[Karl Heinz Buchegger]

Hi,I have to do this exercises can you help me:
1)Write a program to implement exetendible hashing.If the table is small
enough to fin in main memory,how does its performance compare with open and
closed hasing?
2)A basic program consists of a series of statements,each of which is
numbered in ascending order.Control is passed by use of a goto or gosub and
a statement number.Write a program that reads in a legal BASIC program and
renumbers the statements so that the first starts at number f and each
statement has a number d higher than the previous statement.You may assume
an upper limit of n statements,but the statement numbers in the input might
be as large as a 32-bit integer.Your program must run in linear time.
Of it I have resolved many others,but these two I just do not succeed to
make them.Thank you very much

Could you be more specific.
What is your problem *exactly* ?

For the 1) do you know what is 'extendible hashing'.
same for 'open hashing', 'closed hashing'.

The whole problem seems to be to know the theory behind
these concepts. Once this theory is understood, an implementation
should be no problem

For 2)
read the file and create a table with 2 columns, the first
column holds the line number in the original 'program', the
second column holds the modified line number (you get this
modified line number by using the given arguments)

Do a second pass through the program and replace the
original line number with the modified line number. At the
same time analyze the statement. Is it a goto or gosub, then
take the target line number, look it up in the table and
replace it with the modified line number.