Bidirectional map

Definition A bidirectional map, often abbreviated as "BiMap" or "BidiMap," is a data structure that maintains a one-to-one correspondence between a set of keys and a set of values, allowing for efficient lookup of a value given its key, as well as efficient lookup of a key given its value.

Overview Unlike a standard map (or associative array, dictionary, hash map), which primarily provides a mapping from keys to values, a bidirectional map extends this functionality to allow efficient inverse lookups. This means that if K maps to V, a bidirectional map can quickly retrieve V from K and also K from V. A crucial characteristic of a bidirectional map is that it enforces a one-to-one mapping, meaning no two distinct keys can map to the same value, and no two distinct values can be mapped by the same key. This constraint ensures that the inverse mapping is always unambiguous.

Etymology/Origin The term "bidirectional map" is descriptive, combining "bidirectional" to denote the two-way mapping capability with "map," referring to the fundamental data structure that associates keys with values. While the concept of requiring efficient inverse lookups has likely existed as long as associative arrays, the formalization and widespread use of the "bidirectional map" as a distinct data structure or utility, often with dedicated library implementations, became more prevalent with the evolution of computer science and software development paradigms. Accurate information regarding a specific inventor or definitive origin point for the term is not confirmed, but its usage reflects a practical need in software engineering.

Characteristics

• One-to-One Mapping: This is the most defining characteristic. Each key maps to exactly one value, and each value maps to exactly one key. Attempting to add a key that already exists, or a value that is already mapped to another key, will typically result in an error or replacement of the existing mapping.
• Symmetric Operations: Operations such as put(), get(), and remove() often have symmetric counterparts or implicit inverse actions. For example, get(key) returns the value, and inverse().get(value) returns the key.
• Efficient Two-Way Lookup: The primary advantage is the ability to retrieve either the value from the key or the key from the value with similar efficiency, typically O(1) average time complexity for hash-based implementations.
• Implementation: Bidirectional maps are commonly implemented by internally maintaining two standard maps (e.g., Map<K, V> and Map<V, K>). Any modification (addition, removal, update) must be synchronized across both internal maps to maintain consistency.
• Memory Overhead: Due to storing mappings in both directions, a bidirectional map typically has a memory overhead roughly twice that of a single standard map storing the same number of key-value pairs.
• Key and Value Type Restrictions: Similar to standard maps, keys and values must generally be immutable or treated as such for hash-based implementations to ensure consistent hashing and retrieval.

Related Topics

• Map (Associative Array, Dictionary, Hash Map): The fundamental data structure from which a bidirectional map is derived, providing key-to-value mappings.
• Hash Table: A common underlying implementation for maps, offering efficient average-case time complexity for lookups, insertions, and deletions.
• Data Structure: The general classification for organized collections of data that allow efficient access and modification.
• Isomorphism: A mathematical concept describing a structure-preserving mapping between two structures, often used to describe one-to-one correspondences.
• Guava: A popular open-source Java library developed by Google, which provides a BiMap interface and concrete implementations, demonstrating the practical utility of this data structure in software development.