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
Cerinţa
Firdavs [7]
Uummmm English please
4 0
3 years ago
Write a Python program that takes a file name as input and generates the following output: File size in bytes and KBs Time the f
Airida [17]

Answer:

See explaination

Explanation:

import os

import time

from stat import *

file = input("Enter file name: ")

details = os.stat(file)#stores statistics about a file in a directory

print("File size: ", details[ST_SIZE])#retreiving size

print("File last accessed time: ", time.asctime(time.localtime(details[ST_ATIME])))#access time

print("File last modified time: ", time.asctime(time.localtime(details[ST_MTIME])))#modified time

print("File creation time: ", time.asctime(time.localtime(details[ST_CTIME])))#creation time

print("First character: ", file[0])

print("Middle character: ", file[len(file) // 2])

print("Last character: ", file[len(file) - 1])

num_words = 0

num_lines = 0

f=open(file, "r")

lines = f.readlines()

for line in lines:

num_lines = num_lines + 1

num_words = num_words + len(line.split())#add no. of words in that line

print("Number of lines: ", num_lines)

print("Number of words: ", num_words)

8 0
3 years ago
Your worksheet contains confidential information in column C; to prevent others who use your worksheet from seeing the data, you
emmainna [20.7K]
To prevent others who use your worksheet from seeing the data you can hide column C
5 0
2 years ago
What should be done on a tablet in order for that tablet to cease all network connections?
ankoles [38]

Answer:

Turn On Airplane Mode

Explanation:

Turning off cellular does not turn off wifi.

Turning off wifi does not turn off cellular.

Turning off location services does not affect your network connections.

Airplane mode is what turns off all network connections.

3 0
3 years ago
Rob calls the help desk to report that he cannot access any websites on the Internet. While he is still on the phone, you have h
kotykmax [81]
In order for Rob to connect to the network,be must check all the connections he has in order to verify if it is physical problem or not. Let Rob check the wires and all the necessary devices like the routers and switches. If its not physical problem then check if the packets have gone out to the different layers of the network.
8 0
3 years ago
Other questions:
  • Which of the following is the correct order for arranging these titles in a subject filing system? A. Applications, Banking Serv
    5·1 answer
  • What are language standards? At this point in your study of programming, what do they mean to
    5·1 answer
  • #Write a function called string_finder. string_finder should #take two parameters: a target string and a search string. #The fun
    14·1 answer
  • Page UND
    8·1 answer
  • Write a procedural programming loop.. Your loop should start variable n with a value of 10 and count down to zero. The loop shou
    10·1 answer
  • Two technicians are discussing a parasitic load test. Technician A says that the parasitic load is measured with an ammeter Tech
    13·1 answer
  • Credible sites contain __________ information,
    7·2 answers
  • Click to review the online content. Then answer the question(s) below, using complete sentences. Scroll down to view additional
    6·2 answers
  • Please help
    5·1 answer
  • Can anyone figure this out???? I need help ASAP!
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!