6.10. 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.

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

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

    Q-1: 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 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.
You have attempted of activities on this page
Next Section - 7. Sorting