UCF COT 4810 - Storage by Hashing - D251085

Home> Schools> University of Central Florida> Computer Theory (COT) > COT 4810> Storage by Hashing

UCF COT 4810 - Storage by Hashing

School name University of Central Florida

Course Cot 4810- Topics in Computer Science

Pages 15

Download Save

Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Storage by HashingTravis RoeTopics of Computer ScienceChapter 432-5-2006OutlineA ProblemA Solution: HashingQuestionsQ & AA ProblemCompany organizing data using social security numbers, or similar.Need to add and search through collections of identifiers to find objects.Potential Solution: 1-1One index per potential locationAdding: O(1)Searching: O(1)Pros: Very fast, very easy to implementCons: Far too much memory, much of it unusedPotential Solution: Unsorted ArrayAdding. O(1)Searching. O(n)Pros: Easy to implement, fast adding.Cons: Everything else. O(n) ridiculously slow.Potential Solution: Sorted ArrayAdding. O(n)Searching. O(lg n)Pros: Fast searching.Cons: Slow adding.Potential Solution: Balanced BSTAdding. O(lg n)Searching. O(lg n)Pros: Fast speed for adding, searching.Cons: Hard to program. Not O(1).A New Solution: HashingAdding.Use the keys to choose an index.Place the object at the index.O(1)Searching.Use the keys to find the index.Get the object from that index.O(1)Hashing: An Example154-38-1287987-65-4321123-45-6789192-83-7465Social Security Numbers are the keyThe hash-key is based off the last 4 digits of the number.........1287432167897465CollisionsExpected problems:Two objects with the same keyTwo keys, after hashing, with same value.Ways to solve the problems:ChainingProbingCollision Handling: ChainingEvery node is a list of some sort.Whenever there is a collision, put the new item into the list.Collision Handling: ProbingWhenever there is a collision, go to another location some distance away and attempt to fill that location.Can cause grouping.h(k) + a * x; a = 2123-45-6789543-21-6789Reducing CollisionsUse prime numbers for array sizesTake more space than you'll needChoose a better hash functionReferencesDewdney, A.K. “Storage By Hashing”. The New Turing Omnibus. 1993. Computer Science Press.“Hash Tables”. Recording My Programming Path. http://qiang-ma.blogspot.com/2007/10/hash-tables.html <Accessed last 2-5-2008>Standish, Thomas. Data Structures, Algorithms & Software Principles in C. 1995. Addison-Wesley Publishing Company, Inc. pp450-475(ish)Questions1.What are the two methods for handling collisions that were discussed in this lecture?2.What is one situation where hash-tables are not useful

View Full Document

UCF COT 4810 - Storage by Hashing

Sign up for free to view:

This document and 3 million+ documents and flashcards
High quality study guides, lecture notes, practice exams
Course Packets handpicked by editors offering a comprehensive review of your courses
Better Grades Guaranteed


School:
Email:
New Password:
Confirm Password:

UCF COT 4810 - Storage by Hashing

Sign up for free to view:

Please select your school