membership test
Asking whether a collection contains a given item, written `x in collection` in Python.
In more detail
The cost depends entirely on the structure: O(n) for a list, O(log n) for a sorted list with bisect, and O(1) on average for a set or dict. A Bloom filter answers membership approximately in very little memory. For workloads dominated by membership tests, a set is almost always the right choice.
Related terms
- set — Python's built-in unordered collection of unique items, implemented as a hash table that stores keys without values.
- linear search — Finding an item by checking each element in turn from the start until it matches or the list ends.
- Bloom filter — A compact, probabilistic set that can say "definitely not present" or "probably present", using a bit array and several hash functions.
- bisect module — Python's standard-library module of correct binary-search functions for sorted lists.
Taught in
- Why Complexity Matters In Production — Algorithms & Data Structures for Working Engineers
- Python Dicts And Sets Under The Hood — Algorithms & Data Structures for Working Engineers
- Bloom Filters: Membership Without The Data — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers