CPSC 319 Lecture Notes - Lecture 10: Linked List, Binary Search Algorithm, Quadratic Probing

• School: University of Calgary
• Department: Computer Science
• Course: CPSC 319
• Professor: Leonard Manzara

Document Summary

Hash tables are classified as set structures: nodes have no predecessors or successors. Are good for implementing dictionaries, where we only need the operations: Are not suitable when we need to find an item"s predecessor or successor i. e. are not good for ordered lists. With arrays, we directly access an array element using an index. Hash tables are a generalization of ordinary arrays: given a key k, we address the array to access element array[k] If the key corresponds directly to the array index, then we have an ordinary array. With hash tables, we compute the array index from the key using a hash function i. e. access an element using array[h(k)], where h is the hash function: accessing an element does not depend on n. The search operation takes constant time, i. e. is