Class Note for CS 357 at UA-Data Structures (11)
Class Note for CS 357 at UA-Data Structures (11)
Popular in Course
Popular in Department
This 5 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Alabama - Tuscaloosa taught by a professor in Fall. Since its upload, it has received 32 views.
Reviews for Class Note for CS 357 at UA-Data Structures (11)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CS 357 Data Structures Class 23 March 18 2001 Announcements Next time finish chapter 8 Project 3 is out and due this Saturday March 23 by 1159p Project 4 will be out on Friday mzmzc 357C135 mm p More Practice Generate a Polynomial Hash Code V 7 awn X L lrUHKW i For the elementkey use the last 4 digits of your social security number For a use 2 Use the simple compression map of hashCodek N where N31 to generate your hash key hk Example 123456789 HashCode 6 23 7quot2Z 8 21 9quot2El 101 hk HashCode N 101 31 8 mzmzc 357C135 mm p Collisions Ideally h is a 1to 1 map of the keys to the 0N1 range Realistically collisions occurwhich means k1 k2 but hk1hk2 Some means of handling collisions are Separate Chaining Open Addressing mzmzc 357C135 Ms p a Separate Chaining Any keyitem pair whose key maps to a bucket is stored in that bucket Each bucket may be a sequence list etc A good hash function should create buckets of size lnNl also referred to as the load factor mzmzc 357C135 Ms p s Quick Quiz What does separate chaining do to ndElement insertltem removeElement ndAllElements removeAllElements What order are the methods mzmzc 357C135 Ms p 5 Open Addressing Avoids use of auxiliary data structures thereby savmg space Requires that the load factor is S 1 n S N Stores all items in the bucket array one item per bucket Some means of doing this are Linear Probing Quadratic Probing Double Hashing mzmzc 357C135 Ms p 7 Open Addressing Linear Probing Check bucket hk If it already contains an item check the next bucket hk1 Continue checking consecutive buckets until an empty bucket is found wrapping back to the rst bucket if necessary Once an empty bucket is found place the item mzmzc 357C135 Ms p z Quick Quiz Given the hash furic ion h such that hkintlogzk 2 insert 8 14 and 16 into he given bucket array Use linear probing to resolve collisions What does separate chaining do to e findElement e insertitern e remuveElement e findAllElements e remuveAllElements mzmzc 357C135 Ms p 9 Quick Partial Answer Given the hash function h such that hkintlog2k 2 insert 8 14 and 16 into the given bucket array naa25 mma25 h16426 Check bucket 57 Full Check bucket 5 7 Full Check bucket e 7 Full Check bucket 67 Full Check bucket e 7 Full Check bucket 7 7 Full Check bucket 77 Empty Check bucket 7 7 Full Check bucket a 7 Full Place m bucket 7 Check bucket a 7 Empty Check bucket a 7 Empty Placembucka Placembuckaa mzmzc 357C135 mm p em Open Addressing Quadratic Probing To avoid the clustering patterns of linear probing searches for an empty bucket using hk fj mod N jo12 39 f0 17 Does create secondary clustering May not find an empty bucket even if one exists Not as likely if N is chosen to be prime mzmzc 357C135 mm p e Open Addressing Double Hashing Avoids the kind of clustering found with linear and quadratic probing Uses a secondary hash function h Iterativer checks buckets using hkfi mod N 7 u 7 2 f0 j h k Atypical h is qk mod q for some prime number q lt N N should also be prime Should attempt to nd a secondary hash function that causes the least amount of clustering mzmzc 357C135 mm p m Quick Quiz Given the hash function h such that hkintlog2k 2 insert 8 14 and 16 into the given bucket array Use double hashing to resolve collisions with h q k mod q given q7 mzmzc 357C135 mm p 13 Quick Partial Answer naa25 n14a25 nle42e Check bucket 57 Full Check bucket 5 7 Full Check bucket e 7 Full New bucket l5 mayam New bucket l5 57m New nucxeumsmm Check bucket l 7 Empty Check bucket 2 7 Full Check bucket l 7 Full Place lrl bucketl New nucxeuwamm New nucxeuenumm Check bucket a rEmpty Check bucket 6 7 Full Place in bucket a mzmzc 357C135 mm p m Load Factors amp Rehashing The load factor 9 is the ratio of buckets with items to total buckets For separate chaining should maintain M08 For open addressing should maintain M05 A means of maintaining is to rehash as 9 approaches the threshold A new table is created at least double the previous size and the elements are rehashed using a new hash function th What about the code fragment in 82 page 355 if K1 and insertltem is called mzmzc 357C135 mm p e15
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'