DOC PREVIEW
GSU CSC 2320 - CSCI2320 Chapter 20 Hash Table

This preview shows page 1-2-15-16-31-32 out of 32 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Hash tableA basic problemArray as tableUnsorted arraySorted arrayLinked listMore approachesSlide 8Slide 9Slide 10Slide 11Hash functionHash TableHash Table with Perfect HashSlide 15Division MethodCollisionSolutions to CollisionChained Hash TableSlide 20Chained Hash tableOpen AddressingHow to compute probe sequencesLinear Probing: h(k, i ) = (h(k) + i ) mod m.Linear Probing ExampleSlide 26Choosing a Hash FunctionClusteringQuadratic Probing: h(k, i ) = (h(k) + c1i + c2i 2) mod mQuadratic Probing ExampleDouble HashingDouble Hashing Example1Hash table2A basic problemWe have to store some records and perform the following:add new recorddelete recordsearch a record by keyFind a way to do these efficiently!3Array as table990303098020209801010005678900123450033333tommarypeterdavidandybetty731002056.881.590studid name score9908080 bill 49......Consider this problem. We want to store 1,000 student records and search them by student id.Consider this problem. We want to store 1,000 student records and search them by student id.4Unsorted arrayUse an array to store the records, in unsorted orderadd - add the records as the last entry fast O(1)delete a target - slow at finding the target O(n)search - sequential search slow O(n)5Sorted arrayUse an array to store the records, keeping them in sorted orderadd - insert the record in proper position. much record movement slow O(n)delete a target - how to handle the hole after deletion? Much record movement slow O(n)search - binary search fast O(log n)6Linked listStore the records in a linked list (unsorted) add - fast if one can insert node anywhere O(1)delete a target - fast at disposing the node, but slow at finding the target O(n)search - sequential search slow O(n) (if we only use linked list, we cannot use binary search even if the list is sorted.)7More approacheshave better performance but are more complexHash tableTree (BST, Heap, …)8Array as table990303098020209801010005678900123450033333tommarypeterdavidandybetty731002056.881.590studid name score9908080 bill 49......Consider this problem. We want to store 1,000 student records and search them by student id.Consider this problem. We want to store 1,000 student records and search them by student id.9Array as table:0033333:00123450000000::betty:andy::90:81.5:name score0056789david 56.8:9908080:::bill:::49::9999999One ‘stupid’ way is to store the records in a huge array (index 0..9999999). The index is used as the student id, i.e. the record of the student with studid 0012345 is stored at A[12345]One ‘stupid’ way is to store the records in a huge array (index 0..9999999). The index is used as the student id, i.e. the record of the student with studid 0012345 is stored at A[12345]10Array as tableIt is also called Direct-address Hash Table.• Each slot, or position, corresponds to a key in U.• If there’s an element x with key k, then T [k] contains a pointer to x.• Otherwise, T [k] is empty, represented by NIL.11Array as tableStore the records in a huge array where the index corresponds to the keyadd - very fast O(1)delete - very fast O(1)search - very fast O(1)But it wastes a lot of memory! Not feasible.12Hash functionfunction Hash(key: KeyType): integer;Imagine that we have such a magic function Hash. It maps the key (studID) of the 1000 records into the integers 0..999, one to one. No two different keys maps to the same number.Imagine that we have such a magic function Hash. It maps the key (studID) of the 1000 records into the integers 0..999, one to one. No two different keys maps to the same number.H(‘0012345’) = 134H(‘0033333’) = 67H(‘0056789’) = 764…H(‘9908080’) = 313Hash Table:betty:bill::90:49:name scoreandy 81.5::david:::56.8::0033333:9908080:0012345::0056789:3670764999134To store a record, we compute Hash(stud_id) for the record and store it at the location Hash(stud_id) of the array. To search for a student, we only need to peek at the location Hash(target stud_id).To store a record, we compute Hash(stud_id) for the record and store it at the location Hash(stud_id) of the array. To search for a student, we only need to peek at the location Hash(target stud_id).14Hash Table with Perfect HashSuch magic function is called perfect hashadd - very fast O(1)delete - very fast O(1)search - very fast O(1)But it is generally difficult to design perfect hash. (e.g. when the potential key space is large)15Hash functionA hash function maps a key to an index within in a rangeDesirable properties:simple and quick to calculateeven distribution, avoid collision as much as possiblefunction Hash(key: KeyType);16Division MethodCertain values of m may not be good:When m = 2p then h(k) is the p lower-order bits of the keyGood values for m are prime numbers which are not close to exact powers of 2. For example, if you want to store 2000 elements then m=701 (m = hash table length) yields a hash function: h(k) = k mod mh(key) = k mod 70117CollisionFor most cases, we cannot avoid collisionCollision resolution - how to handle when two different keys map to the same indexH(‘0012345’) = 134H(‘0033333’) = 67H(‘0056789’) = 764…H(‘9903030’) = 3H(‘9908080’) = 318The problem arises because we have two keys that hash in the same array entry, a collision. There are two ways to resolve collision:Hashing with Chaining: every hash table entry contains a pointer to a linked list of keys that hash in the same entryHashing with Open Addressing: every hash table entry contains only one key. If a new key hashes to a table entry which is filled, systematically examine other table entries until you find one empty entry to place the new keySolutions to Collision19Chained Hash Table24103nilnilnil5nil:HASHMAXKey: 9903030name: tomscore: 73 One way to handle collision is to store the collided records in a linked list. The array now stores pointers to such lists. If no key maps to a certain hash value, that array entry points to nil.One way to handle collision is to store the collided records in a linked list. The array now stores pointers to such lists. If no key maps to a certain hash value, that array entry points to nil.20Chained Hash TablePut all elements that hash to the same slot into a linked list. • Slot j contains a pointer to the head of the list of all stored elements that hash to j • If there are no such elements,


View Full Document

GSU CSC 2320 - CSCI2320 Chapter 20 Hash Table

Download CSCI2320 Chapter 20 Hash Table
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CSCI2320 Chapter 20 Hash Table and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CSCI2320 Chapter 20 Hash Table 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?