Sep 10, 2011

What is Hashing , HashTable, Hash Function and its collision resolution strategies

Hashing is the technique used for performing almost constant time search in case of insertion, deletion and find operation. Taking a very simple example of it, an array with its index as key is the example of hash table.
So each index (key) can be used for accessing the value in a constant search time. This mapping key must be simple to compute and must helping in identifying the associated value. Function which helps us in generating such kind of key-value mapping is known as Hash Function.

Hash Table a.k.a Hash Map is a data structure which uses hash function to generate key corresponding to the associated value.

lets look at some sample hash function for strings

Folding Method:-
int h(String x, int D)
{
     int i, sum;
     for (sum=0, i=0; i<x.length(); i++)
         sum+= (int)x.charAt(i);
     return (sum%D);
}

Cyclic Shift :-
static long hashCode(String key, int D)
{
  int h=0;
  for (int i=0, i<key.length(); i++)
  {
        h = (h << 4) | ( h >> 27);
        h += (int) key.charAt(i);
  }
  return h%D;
}



good link for hash function on string : click here

Coming to very important part of hashing , which is collision resolution. Since its always not possible to design perfect hash function with minimal overhead which would generate unique key. To address this problem following are the two main collision resolving techniques :-
1) Open Hashing also known as separate chaining 
2) Closed Hashing also known as open addressing

Lets understand the difference between them
1) Open Hashing :- In this strategy collision is resolved by keeping the conflicting element in a list. That is to keep all element in a list which generate same hash.
Open Hashing

From above figure its clear that how collision get resolved by keeping a linked list.

2) Closed Hashing :- In this strategy collision is resolved by placing the conflicting element near to the slot generated by the hash function. Associated with closed hashing is a rehash strategy:
     “If we try to place x in bucket h(x) and find it occupied, find alternative location h1(x), h2(x), etc. Try each in order, if none empty table is full,”
Lets take an example to understand it

HASH_TABLE_SIZE = 8
Input data :- a,b,c,d   Hash for them H(a) = 0, H(b) = 3, H(c) = 7 and  H(d) = 3

Now as 'c' and 'd' has same hash, where to insert 'd' then ?
Finding position using linear hashing :
h1(d) = (h(d)+1)%8 = 4%8 = 4

Adding 1 to hash function of h(d) we get new position 4, and slot 4 is currently non occupied. So entering d at position 4. In this way Closed hashing works.

Disadvantage of closed hashing is that it consumes more space as compared to open hashing 
also it has less flexibility in accommodating for duplicate hash element.
Major advantage of closed hashing is that it reduces the overhead of introducing new data structure and reduces cost of new memory allocation per new element insertion.



103 comments:

its good with precise informtion

thanks dear
you give very simple language to understand
once again thnx.......

This is the most difficult and confusing portion which I am trying from several days to learn. A big thanks to you for simplifying all the things in such a simple and easy way.
e signatures

Good
in example for closed hashing above 'c' is taken instead of 'd'.

Good eexplanatin....bt can u give more explanation on other methods of hashing such as mid-square, multiplication and division....

very helpful information thanks

Very useful information but it will be even better if you provide questions to workout like Geeks for geeks.Try to update..

What you describe is important. Such details in the articles are very much needed.

Repairing of Lenovo laptop are very well done by us as we have experts that are well versed with the technology used in Lenovo laptop to build them. Get in touch with us for swift & skilled help in repairing your Lenovo laptop system. Lenovo service center in Gurgaon. Call us: 7217871051
Lenovo Service Center in Gurgaon

Lenovo Laptop Service Center offer repairing for your laptop needs, we are experts in laptop chip level repair, call us: 7217871051
Lenovo Service Center in Ghaziabad

Lenovo Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 7217871051
Lenovo Service Center in Uttam Nagar

Hp Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 7217871051
HP Service Center in Uttam Nagar

Lenovo Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Lenovo Service Center in DLF Cyber City
Lenovo Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Lenovo Service Center in DLF Cyber City

Hp Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Hp Service Center in Sec-14 Gurgaon

Lenovo Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Lenovo Service Center in Sec-14 Gurgaon

Hp Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Hp Service Center in Palam Vihar

Lenovo Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Lenovo Service Center in Palam Vihar

Hp Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Hp Service Center in Ghaziabad

Lenovo Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Lenovo Service Center in DLF Garden City

Hp Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Hp Service Center in DLF Garden City

Lenovo Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Lenovo Service Center in Kanpur

Hp Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 9891868324
Hp Service Center in Mangolpuri

Hp Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 9891868324
Hp Service Center in Sohna-Road

Hp Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 9891868324
Hp service center in Goregaon

Hp Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 9891868324
Hp service center in Bandra

Hp Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 9891868324
Hp Service in Center in Malad

Lenovo Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 9891868324.
Lenovo service center in Borivali

Lenovo Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Lenovo Service Center in Hero Honda Chowk

Hp Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 9891868324
Hp Service Center in South-City-1

Hp Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 9891868324
Hp Service Center in Malad

Hp Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Hp Service in Center in Santacruz

Hp Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 7217871051
Hp Service Center in Lajpat-Nagar

Lenovo Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Lenovo Service in Center in Janakpuri

Hp Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Hp Service Center in Rohini

Hp Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 9891868324
Hp Service Center in Chattarpur

Dell Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 9891868324
Dell Service Center in Rajouri Garden

Hp Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 9891868324
Hp Service Center in Rajouri Garden

Lenovo Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324
Lenovo Service Center in Rajouri Garden

Dell Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 9891868324
Dell Service Center in Dwarka

Lenovo Laptop Service Center offer repairing for your laptop needs, we are experts in laptop chip level repair, call us: 9891868324
Lenovo Service Center in Pitampura

Hp Laptop Service Center offer repairing for your laptop needs, we are experts in laptop chip level repair, call us: 9891868324
Hp Service Center in Pitampura

Hp Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324.
HP Service Center in Uttam Nagar

Hp Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324.
Hp Service in Center in Okhla

Lenovo Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324.
Lenovo Service in Center in Okhla

Lenovo Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324.
Lenovo Service Center in Greater Noida

Hp Laptop Service Center offer fixing for your PC needs, we are experts in PC chip level fix, call us: 9891868324.
Hp Service in Center in Greater Noida



Hp Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 7042640351.
Hp Service Center in Chattarpur



Lenovo Laptop Service Center offer fixing for your PC needs, we are specialists in PC chip level fix, call us: 7042640351.
Lenovo Service Center in Chattarpur


The school maintains the authors' obligation to greatness in all fields, with accentuation on its maxim Higher Stronger Brighter. High ethics are an essential of a decent individual. Contact on us: 8130269997.
top 10 schools in rohini

The school keeps up the creators' commitment to significance in all fields, with complement on its saying Higher Stronger Brighter. High morals are a fundamental of a nice person. Contact on us: 8130269997.
cbse school in Rohini

The school keeps up the creators' commitment to significance in all fields, with complement on its saying Higher Stronger Brighter. High morals are a fundamental of a nice person. Contact on us: 8130269997.
Top Schools in Rohini

Arising as a broadly perceived promoting organization in all features of publicizing and marking arrangements centering in outside, on the web and electronic media spaces. Contact on us: 9868946230.
Outdoor advertising

Arising as a broadly perceived promoting organization in all features of publicizing and marking arrangements centering in outside, on the web and electronic media spaces. Contact on us: 9868946230.
Hoarding advertising

Arising as a broadly perceived promoting organization in all features of publicizing and marking arrangements centering in outside, on the web and electronic media spaces. Contact on us: 9868946230.
Digital wall painting

It is attempt of Mast Banarasi Paan Company to construct a chain of establishment outlets in a large portion of the urban areas of India to guarantee that heavenly Banarasi Paan is made accessible to each client with a similar flavor, taste, quality and cleanliness and we are the best paan supplier in INDIA
Paan Café

It is attempt of Mast Banarasi Paan Company to construct a chain of establishment outlets in a large portion of the urban areas of India to guarantee that heavenly Banarasi Paan is made accessible to each client with a similar flavor, taste, quality and cleanliness and we are the best paan supplier in INDIA
Flavour Paan

Hp Laptop Service Center offer repairing for your laptop needs, we are experts in laptop chip level repair, call us: 7838122281.
Hp Service Center in BKC-Mumbai

Lenovo Laptop Service Center offer repairing for your laptop needs, we are experts in laptop chip level repair, call us: 7838122281.
Dell Service Center in Mumbai

The school maintains the authors' obligation to greatness in all fields, with accentuation on its maxim Higher Stronger Brighter. High ethics are an essential of a decent individual. Contact on us: 8130269997.
GD GOENKA
Top Schools in Rohini
cbse school in Rohini

Hp Laptop Service Center offer repairing for your laptop needs, we are experts in laptop chip level repair, call us: 7838446546.
Hp Service Center in Mumbai

Lenovo Laptop Service Center offer repairing for your laptop needs, we are experts in laptop chip level repair, call us: 7838446546.
Lenovo Service Center in Mumbai

Dell Laptop Service Center offer repairing for your laptop needs, we are experts in laptop chip level repair, call us: 7838446546.
Dell Service Center in Mumbai

The school maintains the authors' obligation to greatness in all fields, with accentuation on its maxim Higher Stronger Brighter. High ethics are an essential of a decent individual. Contact on us: 8130269997.
Nursery Admissions 2021-2022
Best Schools in Delhi
GD GOENKA Rohini

Arising as a broadly perceived promoting organization in all features of publicizing and marking arrangements centering in outside, on the web and electronic media spaces. Contact on us: 9868946230.
Outdoor Advertising Companies in Delhi

Arising as a broadly perceived promoting organization in all features of publicizing and marking arrangements centering in outside, on the web and electronic media spaces. Contact on us: 9868946230.
Outdoor advertising

Arising as a broadly perceived promoting organization in all features of publicizing and marking arrangements centering in outside, on the web and electronic media spaces. Contact on us: 9868946230.
Hoardings in Delhi

The Company eyes the vision of getting one of the India's notable and rumored Ad Agency by satisfying our customer's requirements and giving our significant customers the best quality outcomes utilizing our ability and rich encounters of publicizing area. We have practical experience in vital and inventive Brand Promotion arrangements in OOH.
Hoardings in Delhi
Rural wall painting advertising
Digital wall painting
Transit Media Service

G.D. Goenka Public School Rohini Sector- 9 is a Co-educational Senior Secondary School, recognized and affiliated to the Central Board of Secondary Education (CBSE). It has classes from Preschool till Class 12th. The school upholds the founders' commitment to excellence in all fields, with emphasis on its motto Higher Stronger Brighter. High morals are a prerequisite of a good human being.
top 10 schools in rohini
cbse school in Delhi
Nursery Admissions 2021-2022

Arising as a broadly perceived promoting organization in all features of publicizing and marking arrangements centering in outside, on the web and electronic media spaces. Contact on us: 9868946230.
Hoardings in Delhi
Digital wall painting
Auto Rickshaw advertising

Four Square Media Services is engineered in Delhi NCR. The Company eyes the vision of getting one of the India's striking and assumed Outdoor Advertising Companies in Delhi by fulfilling our client's basics and giving our colossal clients the best quality results using our ability and rich experiences of advancing. Contact on us: 9868946230.
Hoardings in Delhi
Digital wall painting
Wall painting advertising
Outdoor advertising

Four Square Media Services is engineered in Delhi NCR. The Company eyes the vision of getting one of the India's striking and assumed Outdoor Advertising Companies in Delhi by fulfilling our client's basics and giving our colossal clients the best quality results using our ability and rich experiences of advancing. Contact on us: 9868946230.
Digital wall painting
Auto Rickshaw advertising
Advertising wall painting
Auto rickshaw ad in delhi
Rural wall painting advertising

Bs system solution in Delhi provides the best solution for laptop repair. Our experienced engineers take complete care and responsibility for your device and provide you a high-quality solution. The Lenovo Laptop Technical support is available for all range of customers. IF YOU ARE INTERESTED YOU MAY CALL -9891868324, 9643406897, and 9643409808
laptop repairing center in Delhi
best laptop service center in Delhi

Bs system solution in Delhi provides the best solution for laptop repair. Our experienced engineers take complete care and responsibility for your device and provide you a high-quality solution. The Lenovo Laptop Technical support is available for all range of customers. IF YOU ARE INTERESTED YOU MAY CALL -9891868324, 9643406897, and 9643409808
laptop service in Delhi
laptop reparing center in Mumbai

The ventilated external shell protects against electrical hazards, molten substance splash and squeezes. With its eventuality for integration of a Petzl headlamp, hearing protection, and multiple accessories, it's an entirely modular helmet, therefore meeting the specific fresh conditions of professionals.
petzl HELMETS Vertex price in Mumbai
Petzl HARNESS Avao Bod price in Mumbai

Klever Trade is a new-generation online stock trading platform which will change the way you trade forever. Klever Trade is a new-generation online stock trading platform which will change the way you trade forever. 02614245940
How to trade in algo
Best api for algo trading

Denex International - India's largest manufacturer and exporter of surgical disposables has a wide product base and are regularly adding new medical disposables to the list. The products include I.V. Cannula with PTFE Catheter of different gauges/ sizes, non-woven fabric products such as SURGEON'S GOWNS & APRONS, O.T. SHEETS and are manufactured under the brand name Amie IV Cannula (All Gauges). 9310148912
IV Cannula Manufacturer
IV Catheter Manufacturer

We always attempt to keep international standards in our vending machines to give the superior quality and taste of natural tea and coffee to our customers and users. We are one of the well-known providers of Coffee Machine in Gurgaon. 09873633436
Coffee Vending Machine in gurgaon
Vending Machine in Gurgaon

If you are planning to take the CELPIP test and looking forward to achieve your highest score, then there is great chances our course can really help you achieve your desired score in all four modules. In fact more than 85% of our students have achieved their dream score through our live online sessions.
celpip training near me
celpip training center near me

T-shaped front points are designed for excellent penetration of hard ice and comfort on mixed terrain, while providing solid purchase in snow
Petzl ICE AXES Quark price in Mumbai
Petzl CRAMPONS Sarken price in Mumbai

The ventilated external shell protects against electrical hazards, molten substance splash and squeezes. With its eventuality for integration of a Petzl headlamp, hearing protection, and multiple accessories, it's an entirely modular helmet, therefore meeting the specific fresh conditions of professionals.
Petzl ICE AXES Quark price in Mumbai
Petzl CRAMPONS Sarken price in Mumbai
Petzl ROPES AXIS price in Mumbai
Petzl HEADLAMPS Tikina price in Mumbai

Post a Comment