Searching and Hashing
It is important to understand what search is and when it is appropriate. This page explains sequential and binary search, and their implementation. There is also the matter of hashing as a storage and search technique. In so doing, we introduce the unordered map and how to implement a map abstract data type using hashing. Read Sections 6.1-6.5. You may also find Sections 6.6-6.11 useful for practice.
9. 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 key-data pairs
- mid-square 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