SFWRENG 2C03 Study Guide - Midterm Guide: Directed Graph, Topological Order, Giveh
2 Aug 2018
School
Department
Course
Professor
Document Summary
Open addressing: an attempt to eliminate collisions altogether by implementing a hash table with an array; no chaining; no pointers. No 2 values can be at the location. However, multiple values can share the same hash function value. Before i explain what that means, note that there are 2 values that go into the hash function: the key and a number called trial count: go to step 2, insert the key in the slot. Probing: trying to find an empty slot for a key using the hash function. Multiple values can share the same slot in these hash tables. Trial count: a number that identifies how many failed probe attempts were required to find a slot where the key fits. Think of it like different versions of the computed key. The trial count ranges from 0 to m 1, where m is the size of the table. Linear: where h"(k) is given, h k i h k i mod m.
