List the properties which a hashing function should possess, Computer Engineering

Assignment Help:

List the properties which a hashing function should possess to ensure a good search performance. What approaches are adopted to handle collision?

A hashing function h must possess the subsequent properties to make sure good search performance:

1. The hashing function must not be sensitive to the symbols utilized in some source program. That is it must perform uniformly well for various source programs.

2. The hashing function h must execute reasonably fast.

The subsequent approaches are adopted to handle collision are: 

Chaining: One easy scheme is to chain all collisions in lists attached to the suitable slot. This allows an unlimited no. of collisions to be handled and doesn't need a priori knowledge of how many components are contained in the collection. The tradeoff is similar as with linked lists versus array implementations of collections: linked list overhead into space and to a lesser extent, in instance.

Rehashing: It schemes utilizes a second hashing operation while there is a collision. If there is a further collision, we re-hash till an empty "slot" in the table is determined. The re-hashing function may either be an original function or a re-application of the new one. As long as the functions are applied to a key in similar order, then a sought key can all the time be located.

1661_hashing function.png

h(j) = h(k), so the subsequent hash function, h1 is used, a second collision is arise, so h2 is used

Overflow chaining: The other scheme will divide the pre-allocated table in two sections: the primary area  to that keys  are mapped  and  an  area  for  collisions, usually termed the overflow area. While a collision happens, a slot in the overflow area is utilized for the new component and a link from the primary slot established as into a chained system. It is essentially similar as chaining, except the overflow area that is pre-allocated and therefore possibly faster to access. Along with re-hashing, the maximum number of components must be identified in advance, but in this case, two parameters should be estimated: the optimum size of overflow and the primary areas.

899_Rehashing.png


Related Discussions:- List the properties which a hashing function should possess

What is matrix addressing mode, What is Matrix Addressing Mode. Ans. M...

What is Matrix Addressing Mode. Ans. Matrix Addressing Mode: The arrangement which needs the fewest address lines is a square array of n rows and n columns for a whole memory

.image forgery detection, what is the code to detect image forgery using Ma...

what is the code to detect image forgery using Matlab..??

What do you mean by memory mapped i/o, What do you mean by memory mapped I/...

What do you mean by memory mapped I/O? In Memory mapped I/O, there is no particular input or output instructions. The CPU can manipulate I/O data residing in interface register

Explain the configuration of a step-by-step switching system, With neat dia...

With neat diagrams explains the configuration of a step-by-step switching system. The schematic diagram for an exchange is specified in figure. Each subscriber is associated to

Era of first generation computers, Q. Era of first generation computers? ...

Q. Era of first generation computers? The trends that were encountered at the time of the era of first generation computers were: Centralized control in a single CPU (al

How can arithmetic processor be associated to the CPU, Q. How can this arit...

Q. How can this arithmetic processor be associated to the CPU?  Two mechanisms are used for connecting arithmetic processor to CPU.   If an arithmetic processor is treated a

Properties for of static ram, a) Give eight properties for each of static R...

a) Give eight properties for each of static RAM (SRAM) and DRAM (dynamic RAM) and provide the low-level structure of each type of memory. b) Assume a system with 16 Megabytes o

What is preemptive and nonpreemptive scheduling, What is preemptive and non...

What is preemptive and nonpreemptive scheduling? Under nonpreemptive scheduling once the CPU has been allocated to a process, the process keeps the CPU unless it releases the C

Does gimp have scanner support, Yes. It's available on Windows and uses TWA...

Yes. It's available on Windows and uses TWAIN, and on GNU/Linux you constant have a choice among XSane and gnome-scan - both can be used as GIMP plug-ins.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd