TAILIEUCHUNG - Lecture Data Structures: Lesson 42

Lecture Data Structures: Lesson 42 provide students with knowledge about example hash functions; collision; find something to do with the second and subsequent values that hash to this same location; solution for handling collisions; open addressing and closed hashing; . | Lecture Data Structures Dr. Sohail Aslam Example Hash Functions If the keys are integers then key T is generally a good hash function unless the data has some undesirable features. For example if T 10 and all keys end in zeros then key T 0 for all keys. In general to avoid situations like this T should be a prime number. Collision Suppose our hash function gave us 0 kiwi the following values 1 hash quot apple quot 5 hash quot watermelon quot 3 2 banana hash quot grapes quot 8 3 watermelon hash quot cantaloupe quot 7 4 hash quot kiwi quot 0 hash quot strawberry quot 9 5 apple hash quot mango quot 6 hash quot banana quot 2 6 mango 7 cantaloupe hash quot honeydew quot 6 8 grapes 9 strawberry Now what Collision When two values hash to the same array location this is called a collision Collisions are normally treated as first come first served the first value that hashes to the location gets it We have to find something to do with the second and subsequent values that hash to this same location. Solution for Handling collisions Solution 1 Search from there for an empty location Can stop searching when we find the value or an empty location. Search must be wrap-around at the end. Solution for Handling collisions Solution 2 Use a second hash function .and a third and a fourth and a fifth . Solution for Handling collisions Solution 3 Use the array location as the header of a linked list of values that hash to this location Solution 1 Open Addressing This approach of handling collisions is called open addressing it is also known as closed hashing. More formally cells at h0 x h1 x h2 x are tried in succession where hi x hash x f i mod TableSize with f 0 0. The function f is the collision resolution strategy. Linear Probing We use f i i . f is a linear function of i. Thus location x hash x i mod TableSize The collision resolution strategy is called linear probing because it scans the array sequentially with wrap around in search of an empty cell. Linear Probing .

• Cơ sở dữ liệu
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Data structures
• Hash functions
• Handling collisions
• Open addressing
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• Programming assignments
• Data structures organize data
• Resource constraints
• Abstract data types
• Tree data structure
• Lecture Data structures and algorithms
• Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Bài giảng Cấu trúc dữ liệu và thuật toán
• Fundamental data structures
• Computational complexity
• Complexity of algorithms
• Data structure
• Pointers to structures
• Pointers to classes
• Josephus problem
• List data structures
• Doubly linked list
• Circularly linked list
• Code for simulation
• Priority queue
• Tree data structures
• Computer science
• Design of data structures
• Algorithms in Java
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming