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

Advantages and disadvantages of e-commerce, E-commerce is one of the most s...

E-commerce is one of the most significant aspects of the internet. Having emerged recently and growing at a steady state, it becomes essential to look at the advantages and disadva

How does the dialog handle user requests, How does the Dialog handle user r...

How does the Dialog handle user requests? when an action is performed ,the system triggers the PROCESS AFTER INPUT event. The data passed contains field screen data data enter

Explain the major consideration of laptop computers, Explain the major cons...

Explain the major consideration of laptop One of the major considerations when buying a laptop is battery life. This can rely on a number of things though one major factor is p

What is throughput of a system, Throughput of a system is? Ans. "Throug...

Throughput of a system is? Ans. "Throughput" of a system is no. of programs processed by this per unit time.

Explain what is internal modems, Q. Explain what is Internal Modems ? I...

Q. Explain what is Internal Modems ? Internal Modems: Internal Modems plug in expansion slots in your PC. Internal Modems are efficient andcheap. Internal Modems are bus-specif

Arbitrary categorisation - learning decision trees, Arbitrary categorisatio...

Arbitrary categorisation - learning decision trees: Through visualising  a set of boxes with some balls in. There if all the balls were in a single box so this would be nicely

Design and development of an information system, This assignment consists o...

This assignment consists of design and development of an information system. The first part of the assignment consists of the design, which includes construction of ER and DFD diag

Translating from english to first-order logic, Translating from English to ...

Translating from English to First-Order Logic: Still we have now seen some of examples of first order sentences, than you should practice writing down English sentences in fir

Handling interrupts - computer architecture, Handling Interrupts: Pre...

Handling Interrupts: Precise interrupts (sequential semantics) Complete instructions before the offending instructions o   Force trap instruction into IF o

Optimum solution based on constraint problems, Optimum solution based on co...

Optimum solution based on constraint problems: Whether depending on what solver you are using so there constraints are often expressed as relationships between variables as e.

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