1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
baherus [9]
3 years ago
12

Show the array that results from the following sequence of key insertions using a hashing system under the given conditions: 5,

205, 406, 5205, 8205, 307 (you can simply list the non-null array slots and their contents)
a. array size is 100, linear probing used.
b. array size is 100, quadratic probing used.
Computers and Technology
1 answer:
sergejj [24]3 years ago
3 0

Answer:

a) Linear probing is one of the hashing technique in which we insert values into the hash table indexes based on hash value.

Hash value of key can be calculated as :

H(key) = key % size ;

Here H(key) is the index where the value of key is stored in hash table.

----------

Given,

Keys to be inserted are : 5 , 205, 406,5205, 8205 ,307

and size of the array : 100.

First key to be inserted is : 5

So, H(5) = 5%100 = 5,

So, key 5 is inserted at 5th index of hash table.

-----

Next key to inserted is : 205

So, H(205) = 205%100 = 5 (here collision happens)

Recompute hash value as follows:

H(key) =(key+i) % size here i= 1,2,3...

So, H(205) =( 205+1)%100 = 206%100 = 6

So, key 205 is inserted in the 6th index of the hash table.

----------

Next Key to be inserted : 406

H(406) = 406%100 = 6(collision occurs)

H(406) =(406+1) %100 = 407%100 = 7

So, the value 406 is inserted in 7the index of the hash table.

-----------------

Next key : 5205

H(5205) = 5205%100 = 5(collision)

So, H(5205) = (5205+1)%100 = 6( again collision)

So, H(5205) = 5205+2)%100 = 7(again collision)

So, H(5205) = (5205+3)%100 = 8 ( no collision)

So, value 5205 is inserted at 8th index of the hash table.

-------------

Similarly 8205 is inserted at 9th index of the hash table because , we have collisions from 5th to 8th indexes.

-------------

Next key value is : 307

H(307) = 307%100 = 7(collision)

So, (307+3)%100 = 310%100 = 10(no collision)  

So, 307 is inserted at 10th index of the hash table.

So, hash table will look like this:

Key       index

5         5

205         6

406         7

5205 8

8205 9

307         10

b) Quadratic probing:

Quadratic probing is also similar to linear probing but the difference is in collision resolution. In linear probing in case of collision we use : H(key) = (key+i)%size but here we use H(key) =( key+i^2)%size.

Applying Quadratic probing on above keys:.

First key to be inserted : 5.

5 will go to index 5 of the hash table.

-------

Next key = 205 .

H(205) = 205%100 = 5(collision)

So. H(key)= (205+1^2)%100 = 6(no collision)

So, 205 is inserted into 6th index of the hash table.

--------

Next key to be inserted 406:

So, 406 %100 = 6 (collision)

(406+1^2)%100 = 7(no collision)

So, 406 is moved to 7th index of the hash table.

----------

Next key is : 5205

So, 5205%100 = 5 (collision)

So, (5205+1^2)%100 = 6 ( again collision)

So, (5205+2^2)%100 = 9 ( no collision)

So, 5205 inserted into 9th index of hash table.

-----------

Next key is 8205:

Here collision happens at 5the , 6the , 9th indexes,

So H(8205) = (8205+4^2)%100 = 8221%100 = 21

So, value 8205 is inserted in 21st index of hash table.

--------

Next value is 307.

Here there is collision at 7the index.

So, H(307) = (307+1^2)%100 = 308%100= 8.

So, 307 is inserted at 8the index of the hash table.

Key           Index

5                  5

205                  6

406                  7

5205                9

8205               21

307                   8

You might be interested in
Please help me on this I don't know which one they are​
Nutka1998 [239]
Hi, the photo doesn’t show the question on what to answer, all I see are empt boxes, if you message me the question I will answer it for you!
7 0
3 years ago
Read 2 more answers
A general rule for adding text to a slide is ____.
Rama09 [41]

A general rule for adding text to a slide is to use not more than two fonts in a presentation and vary the font size. Furthermore, to make a slide legible, in addition to the point size, attention must be paid to the word count per slide, the choice of typeface, and the visual balance of  space to text.

4 0
3 years ago
Read 2 more answers
Assume that a file contains students' ids, full names, and their scores (Assignments grade, quizzes grade,
elixir [45]

Answer:

اope its heمحبعم

Explanation:

3 0
3 years ago
Is techonology better? Lot of votes needed.
Nataliya [291]
In some ways yes but others... not so much. we have access to amazing things that can help so many people and some are tearing people apart or are used for illegal things. its really everyone's own opinion because of some interactions (positive or negative) that can influence them.
5 0
3 years ago
A(n) ________________ takes place when an unauthorized person gains access to a digital device by using an internet connection a
nordsb [41]
It's called an attack
4 0
3 years ago
Other questions:
  • Which of the following is a narrative essay most like
    8·2 answers
  • What is the f(n) runtime of the following pseudocode: sum-0 for A = N/2 downto 1 for B-1 t increment sum by B Explain: exactly w
    13·1 answer
  • Identify the six components of an information system. Which are most directly affected by the study of computer security? Which
    8·1 answer
  • Write a program to calculate and return total surface area of a box using FUNCTION _END FUNCTION.​
    15·1 answer
  • Communications that take the form of electronic junk mail or unsolicited e-mail are referred to as
    13·2 answers
  • 6. What is the difference between portrait and landscape orientation? What are the advantages of
    9·1 answer
  • When working with arrays, most programming languages perform ________, which means they do not allow programs to use invalid sub
    5·1 answer
  • A browser is an example of a. :
    7·1 answer
  • What are three sections in a work sheet accounting
    12·1 answer
  • Drag each label to the correct location on the image. Match the movie qualities with the right period of movies.
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!