6.10. Glossary¶
 binary search
search method in which 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.
 chaining
a method of collision resolution in which each slot in a hash table holds a reference to a collection of items
 collision
a conflict of having two or more items sharing the same slot in a hash table
 collision resolution
a systematic method for resolving hash table collisions
 clustering
items being mapped in a hash table near each other because of collisions and linear probing resulting in items with collisions being put together
 folding method
a method for constructing a hash function by dividing the item into equally sized pieces and then adding the pieces together to get a hash value. The value is then divided by the size of the hash table and the remainder becomes the slot for that item.
 hashing
generating a value given an input that can be used to find the input by searching for the value.
 hash function
the mapping between an item and its slot in a hash table
 hash table
a collection of items which are stored in such a away as to make it easy to find them
 linear probing
an open addressing technique in which each slot is visited one at a time systematically
 load factor
Represents how full a hash table is. Its the number of items in a hash table divided by the size of the table.
 map
an associate data type that stores keydata pairs
 midsquare method
a method for constructing a hash function by squaring the item and then using some portion of the result.
 open addressing
a collision resolution that tries to find the next open slot/address in the hash table
 perfect hash function
a hash function that maps each item to a unique hash slot
 quadratic probing
a 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
the 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
a position in a hash table
6.11. Matching¶

Q1: Drag the word on the left to its corresponding definition
Review classes and their properties
 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 keydata pairs
 midsquare 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.