liveBook · Manning

Linear search

As explained in High Performance Unity Game Development

A search technique that examines elements sequentially until it finds a match or reaches the end.

In one dictionary collision strategy, a linear search finds the next free slot when storing a colliding key. Lookup scans from the key’s hashed location until it finds a match. section 10.1

This approach uses linear search in two ways:

  • On insertion, scan for an empty slot after a hash collision. section 10.1
  • On lookup, scan from the hashed location to find the key; repeated collisions can leave data misplaced and force repeated scans. section 10.1
Figure 10.3 To find the value for a specific key, we need to linearly search the dictionary starting at the hashed location.

Shows lookup scanning from a key’s hashed location. section 10.1

How High Performance Unity Game Development covers it

How deep it goes
Explains insertion and lookup scans and their repeated cost, without detailing implementation code.
Examples
Uses dictionary insertion and lookup after hash collisions to illustrate sequential scans.
What it assumes
Assumes familiarity with dictionary keys and hash locations while describing collision handling.
What you can do after
Understand how collisions can trigger sequential scans during dictionary insertion and lookup.
How it connects
Connects linear search to dictionaries, hash functions, and hash collisions.

Also explained in

Compare how 7 books explain linear search →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of High Performance Unity Game Development. The section links point to the parts of the book it draws on.