×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

32

0

5

# Class Note for CS 357 at UA-Data Structures (11)

Marketplace > University of Alabama - Tuscaloosa > Class Note for CS 357 at UA Data Structures 11

No professor available

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
No professor available
TYPE
Class Notes
PAGES
5
WORDS
KARMA
25 ?

## 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)

×

×

### What is Karma?

#### 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

×

×

### BOOM! Enjoy Your Free Notes!

×

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'

## Why people love StudySoup

Steve Martinelli UC Los Angeles

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Janice Dongeun University of Washington

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Bentley McCaw University of Florida

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com