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

Explain arithmetic shift micro-operations, Q. Explain arithmetic shift Micr...

Q. Explain arithmetic shift Micro-operations? In arithmetic shift a signed binary number is shifted to right or to the left. So an arithmetic shift-left causes a number to be m

Decision trees, Decision Trees: Visualize you only ever do four things...

Decision Trees: Visualize you only ever do four things at the weekend such as go shopping or watch a movie or play tennis and just stay in. In such case what you do depends on

Explain about fundamental nature of a computer, Q. Explain about fundamenta...

Q. Explain about fundamental nature of a Computer? The fundamental nature of a Computer is as an information transformer. So a computer should be able to take input and process

Represent negative numbers in the computer system, Q. What are the values o...

Q. What are the values of x, y, and z. (1011.001101)2 = (x)10 = (y)8 = (z)16 Q. What are the various ways to represent Negative Numbers in the Computer system?

Electric typewriter in information distribution, Electric typewriter : Ele...

Electric typewriter : Electric typewriters are similar to standard typewriters but with an electronic motor taking the place of human energy. It is much faster than the standard m

Defining data definition, Defining Types of Data ? The subsequent forma...

Defining Types of Data ? The subsequent format is used for defining data definition:  Format for data definition:  {Name}  Name -   a program references the data

What are the event key words in interactive reporting, What are the event k...

What are the event key words in interactive reporting? Event Keyword                                                 Event AT LINE-SELECTION         Moment at which the u

Which technique is an encryption technique, Which technique is an encryptio...

Which technique is an encryption technique? Ans. Block cipher technique and also Steam cipher technique is an encryption technique.

Describe target processor arrangements, Q. Describe target processor arrang...

Q. Describe target processor arrangements? Having seen how to describe one or more target processor arrangements we need to initiate mechanisms for distributing data arrays ove

Give solution for readers-writers problem, Give a solution for readers-writ...

Give a solution for readers-writers problem using conditional critical regions. Solution for readers-writers problem using conditional critical regions: Conditional critical

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