Hashing & Its Application
#1

Presented By…
Surya Mukherjee

[attachment=12166]
History
• In January 1953, H. P. Luhn wrote an internal IBM memorandum that used hashing with chaining.
• G. N. Amdahl, E. M. Boehme, N. Rochester, and A. L. Samuel implemented a program using hashing at about the same time.
• Open addressing with linear probing (relatively prime stepping) is credited to Amdahl, but Ershov (in Russia) had the same idea
What is hashing?
The process of building or finding information in the hash table.
Hashing is the antithesis of sorting.
The process of chopping up the key and mixing it up in various ways in order to obtain an index which will be uniformly distributed over the range of indices.
Implementation
 Use hash function to map keys into positions in a hash table.
 If element “e” has key “k” and “h” is hash function, then “e” is stored in position “h(k)” of table.
To search for “e”, compute “h(k)” to locate position. If no element, dictionary does not contain “e”.
Analysis ( Ideal Case )
 O(b) time to initialize hash table (b number of positions or buckets in hash table)
 O(1) time to perform insert, remove, search.
Collision
 If key range too large, use hash table with fewer buckets and a hash function which maps multiple keys to same bucket:
h(k1) = b = h(k2): k1 and k2 have collision at slot b
 Example: hash table with 11 buckets
h(k) = k%11
80 ® 3 (80%11= 3), 40 ® 7, 65 ® 10
58 ® 3 collision
Collision Resolution Policies
Two classes:

 Open hashing
 Closed hashing
 Difference has to do with whether collisions are stored outside the table (open hashing) or whether collisions result in storing one of the records at another slot in the table (closed hashing)
Open Hashing
Open 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,”
 h(x) is called home bucket
 Simplest rehash strategy is called linear hashing
 hi(x) = (h(x) + i) % D
 In general, our collision resolution strategy is to generate a sequence of hash table slots (probe sequence) that can hold the record; test each slot until find empty one (probing)
 Example : Linear (OpeN) Hashing
 D=8, keys a, b, c, d have hash values h(a)=3, h(b)=0, h©=4, h(d)=3.
Closed Hashing
 Each bucket in the hash table is the head of a linked list
 All elements that hash to a particular bucket are placed on that bucket’s linked list
 Records within a bucket can be ordered in several ways
 by order of insertion, by key value order, or by frequency of access order
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page
Popular Searches: seminar on hashing and hash tables, open hashing ppt, types of image hashing ppt, seminar topics related to operating system hashing, http seminarprojects net t hashing its application, ppts on image hashing, hashing ppt,

[-]
Quick Reply
Message
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  Application of Software Testing in E-Learning full report project topics 3 6,509 27-06-2013, 07:52 PM
Last Post: Ashley Brownile
  Hand And Finger Gesture Recognition System for Robotic Application seminar class 1 4,034 22-11-2012, 12:00 PM
Last Post: seminar details
  Application System Modeling Data Modeling through ER Model seminar class 0 1,970 31-03-2011, 12:12 PM
Last Post: seminar class
  Rapid Application Development Model project report helper 0 1,639 05-10-2010, 01:00 PM
Last Post: project report helper
  Composition of Java-based Router Elements and its Application to Generalized Video computer science topics 0 1,462 17-06-2010, 01:18 PM
Last Post: computer science topics
  Time SeriesSimilarity Search and its Applications computer science technology 0 993 23-01-2010, 08:15 PM
Last Post: computer science technology
  Application of AI in Education Electrical Fan 0 1,215 03-09-2009, 01:54 AM
Last Post: Electrical Fan

Forum Jump: