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

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.


a method of collision resolution in which each slot in a hash table holds a reference to a collection of items


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


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.


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.


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


putting an item into a hash table after a collision


the algorithmic process of finding a particular item in a collection of items

search method in which one follows the underlying ordering of items in a collection of data to find a specific item


a position in a hash table