Lecture 28 - December 5, 2007 - last lecture

Returned quizzes

Handed out depth first search and breadth first search and went over them.

Terminology:

• Hash function: a function used to manipulate the key of an element to identify its location in the list
• Hashing: the technique used for ordering and accessing elements in a list in a relatively constant amount of time by manipulating the key to identify its location in the list.
• Hash table: the data structure used to store and retrieve elements using hashing.
• Collision: the condition resulting when two or more keys produce the same hash location.
• Linear probing: resolving a hash collision by sequential searching a hash table beginning at the location returned by the hash function.
• Open addressing : group of techniques used to resolve collisions directly within the hash table.
• Clustering: the tendency of elements to become unevenly distributed in the hash table with many elements clustering around a single hash location.
• Quadratic probing: resolving a hash collision by using the square of the number of times we have probed the table to determine the next location.
• Double hashing: resolving a collision through a second hash function. The first function computes a hash address from the key. The second hash function computes the increment for use in the general linear probing formula.
• Bucket: a collection of elements associated with a particular hash location.
• Direct Chaining: a hash collision resolution method based on storing elements in linked lists (chains) external to the hash table. Each hash table entry is an external pointer to the linked list. (see page 829).
• Coalesced chaining: a variation of chaining that stores the linked lists for each hash index within the table itself.
• Load factor: the fraction of slots in a hash table that are used. ranges from 0.0 to 1.0
• Methods of hashing numeric keys
• division methods using / and rem
• multiplication methods
• folding methods
• methods of hashing string keys
• folding example (p. 838
• Perfect hash function: a hash function that produces no collisions for a defined set of keys
• Minimal perfect hash function: a perfect hash function that maps the defined set of keys to a hash table with a load factor of 1.0