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
A computer's hard disk drive holds 8 x 10^10 bytes of information. If Jill buys an extra memory stick that holds 5.1 X 10^8 byte
denis-greek [22]

Answer:

The computer will store 8.05 *10^10 bytes of information.

Explanation:

This is the same as saying that the computer will now have 80.51 Gigabytes ( 1gb = 1.000.000.000 bytes) of storage. In this case, the number is represented in its decimal form, and the previous one is displayed in Scientific Notation.

8 0
3 years ago
season is when the weather is not optimal and few tourists of vacation time a shoulder b high c average d low​
cricket20 [7]
Winter is such a season. Travel is lower to colder climate areas such as Canada, but higher to warmer climate areas like Columbia.
7 0
3 years ago
Read 2 more answers
WHAT DOES THE SCRATCH CODE BELOW DO?
Natasha_Volkova [10]

Answer:

the first one

Explanation:

3 0
2 years ago
Can someone answer me
Alexxandr [17]

Answer:

D. 5,184,000

Explanation:

3000*1728= 5184000

8 0
3 years ago
The physical components of a computer, such as a keyboard or hard drive, is called?
faust18 [17]

I'm assuming hardware.


Remember, Hard = Physical.


If that's not it, try peripherals.

4 0
3 years ago
Other questions:
  • A measure of the twisting or rotational force that an engine can produce is called
    12·1 answer
  • Create a funtion makeStudent(studentlist) where studentlist is your list of Student namedtuples The function should do the follo
    13·1 answer
  • What is the purpose of inserting SmartArt in a Microsoft Office program? (1 point)
    11·2 answers
  • Computer maker Dell realized the problems with keeping large inventories, especially because of the fast rate of obsolescence of
    7·1 answer
  • You use different office apps to accomplish specific tasks, such a creating a newsletter or producing a sales presentation, yet
    8·1 answer
  • What is a mortgage?
    8·2 answers
  • One form of e-mail attack that is also a DoS attack is called a mail spoof, in which an attacker overwhelms the receiver with ex
    14·1 answer
  • This code --> plt.plot(x,y) is used to draw :
    8·1 answer
  • Identify and explain 4 traditional (old ways) marketing approaches used by University uses in reaching
    7·1 answer
  • Which item is developed last in the cyclical process?
    5·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!