Stable sort - Retains ordering of equivalent keys. e.g. A sort of athis course's classlist, first by section, then by name, would be sorted first by name and then by section. This depends on the sort being stable, meaning when we sort by section, al the names in each section are already ordered and that order must be maintained. =============================================================================== Hashing - Goal: O(1) access. - Values are best evenly distributed throughout the table. - A hash table should (must?) contain a number of slots that is prime. * This way elements will always be found for storing, accessing, removing - Size of a hash table should greatly (vastly?) exceed the max size of data. * Sparse - Operations: * Insert * Access * Remove - Hash table has three possible states 1. Never used 2. In use 3. Was used - Collision Resolution * Separate chaining is used when the has table is an array of pointer + Each 'bucket' holds all values that hashed to that index * Other resolutions require applying functions to the hash result to find an open space. * Prime size hash table critical to be sure collision resolution is dependable. * When does probing stop? + For access or removal, a never used space indicates item not found + For insertion, a new datum can be placed in any space not currently in use. A cluster is a series of in-use or previously used elements in consecutive slots