Checkpoint 6.11.1.
- binary search
- One repeatedly divides a sorted data structure in half and determines if the item is in one half of it until the item is found or deemed not in the data.
- load factor
- Its the number of items in a hash table divided by the size of the table.
- map
- Associate data type that stores key-data pairs
- mid-square method
- Method for constructing a hash function by squaring the item and then using some portion of the result.
- open addressing
- Collision resolution that tries to find the next open slot/address in the hash table.
- perfect hash function
- Hash function that maps each item to a unique hash slot.
- quadratic probing
- Variation of linear probing in which rehashing is done using successive squared values.
- rehashing
- Putting an item into a hash table after a collision.
- searching
- Algorithmic process of finding a particular item in a collection of items.
- sequential search
- Search method in which one follows the underlying ordering of items in a collection of data to find a specific item.
- slot
- Position in a hash table.
- chaining
- Collision resolution method, in which each slot in a hash table holds a reference to a collection of items.
- collision
- Having two or more items sharing the same slot in a hash table.
- collision resolution
- Systematic method for solving hash table collisions.
- clustering
- Items being mapped in a hash table near each other resulting in items with collisions being put together.
- folding method
- Constructing a hash function by dividing the item into equally sized pieces, adding the pieces together to get a hash value, dividing by the size of the hash table, and the remainder becomes the slot for that item.
- hashing
- Creating a value for an input that can be used to find the input by searching for the value.
- hash function
- Mapping between an item and its slot in a hash table
- linear probing
- Open addressing technique in which each slot is visited one at a time systematically.
Drag the word on the left to its corresponding definition
Review classes and their properties
