COMP 2402 Final: comp 2402 exam notes part 2
15 Apr 2016
School
Department
Course
Professor
Document Summary
Consists of two components: a table (bucket array) that stores the key value pairs, a hash function that maps keys to locations in the table (particular buckets) where that key value pair is or should be located. The function finds the right bucket for the key. A problem with this hash table is that each bucket holds all word-definitions pairs that start with a given letter and we expect lots of words will begin with the same letter. The hash function in this simple example is expected to have many collisions. A collision occurs when two keys have the same hash value. Two types of hashing to avoid collision: hashing with chaining, linear probing, cuckoo hashing. The degree of a vertex is the number of edges that are incident to it. There is a unique path between any two nodes in a binary tree. Length of a path is the number of edges on the path.
