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

Differentiate aggregation and containment, Aggregation is the relationship ...

Aggregation is the relationship among the whole and a part. We can add/subtract some properties in the part (slave) side. It won't affect the entire part. Best example is Car,

What is a rendezvous point?, You insert rendezvous points into Vuser script...

You insert rendezvous points into Vuser scripts to imitate heavy user load on the server. Rendezvous points instruct Vusers to wait during test implementation for multiple Vusers t

Displays a format of floating-point number, Q. Displays a format of floatin...

Q. Displays a format of floating-point number? A floating binary number +1010.001 in a 16-bit register is able to be represented in normalised form (presuming 6 bits for expone

Explain height of a tree, Height of a tree The length of the longest pa...

Height of a tree The length of the longest path from root to any node is called as the height of the tree.

Differentiate the latch and flip-flop, Differentiate the latch and flip-flo...

Differentiate the latch and flip-flop? The major difference between latch and FF is which latches is level sensitive whereas FF is edge sensitive. They both need the use of clo

Customer service and support in post purchase interaction, Describe the cus...

Describe the customer service and support in post purchase Interaction. Post purchase Interaction: The considerations at this step can be explained by the given example:

Illustrate high performance fortran, In 1993 High Performance FORTRAN Forum...

In 1993 High Performance FORTRAN Forum which is a group of academicians and many leading software and hardware vendors in field of parallel processing established an informal langu

Where particular header ends & next item begins of ipv6, As IPV6 contain mu...

As IPV6 contain multiple headers, how does it know where particular header ends and next item begins? Several headers types contain fixed size. For illustration a base header h

How semaphores implement mutual exclusion, How semaphores implement mutual ...

How semaphores implement mutual exclusion? Mutual-exclusion implementation along with semaphores: Assume that there are n-processes and they share a semaphore, mutex (stan

What is asp.net authentication providers and iis security, What is ASP.NET ...

What is ASP.NET Authentication Providers and IIS Security? ASP.NET implements authentication using authentication providers, which are code modules that verify credentials and

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