skip to content

Identity vs Equality

8 roadmaps3 questions

Reference identity (the same object) versus value equality (equivalent content), and why it decides comparisons, caching and collection behavior. Interviewers use it as a fast depth probe.

on this pageshow

explore

questions

3

When is it safe to use identity comparison ("are these two references the same object?") as a stand-in for value equality? Name languages where this is a guarantee and languages where it only appears to work.

level: middleimportance: should knowfreq 45%

answer

  1. Canonical instance = identity is equality
  2. Erlang atom table: unbounded input is a DoS
  3. Scheme eq? guaranteed for symbols, unspecified for numbers
  4. Java Integer cache and CPython interning are optimizations, not contracts
  5. Interning demands immutability plus a construction chokepoint

basics

~20 s

Only when the type guarantees exactly one canonical instance per value. Erlang and Elixir atoms, Lisp and Scheme symbols, Ruby symbols and JavaScript's Symbol.for registry give that guarantee. Java's small-Integer cache and CPython's interned strings do not; they are optimizations.

solid answer

~50 s

Identity substitutes for equality only where canonicalization is a **language guarantee**, not an implementation detail. - **Erlang/Elixir atoms** live in one global table, so atom comparison is a word compare and identity *is* equality. The price is a table that is bounded and (for module-referenced atoms) never reclaimed, which is why `String.to_existing_atom/1` exists for untrusted input. - **Scheme** publishes the boundary instead of hiding it: `eq?` is guaranteed for symbols and the empty list, explicitly *unspecified* for numbers and characters, so `eqv?`/`equal?` are the correct rungs there. - **Java** caches boxed integers in -128..127 and interns compile-time string literals, so reference comparison succeeds for small values and literals and fails one value later. It is a trap, not a contract. - **CPython** interns identifier-like short strings; since 3.8 the compiler emits a SyntaxWarning for `is` against a literal because the optimization leaks into semantics. Canonicalization also demands immutability: everyone shares the one instance.

code

elixir · 5 lines
elixir
a = :active
b = String.to_existing_atom("active")
a === b        # true, always - one entry in the atom table

# String.to_atom(user_input) would grow that table without bound

go deeper

for a junior

Know that comparing references asks 'same object?' and that this is not the same question as 'same value?', and that a value type may or may not hand you the same object twice.

for a middle

Be able to name at least one language where canonical instances are guaranteed (atoms, symbols) and one where interning is only an optimization, and state that interning requires immutability.

for a senior

Discuss the cost side: table growth, untrusted input turning interning into a denial-of-service vector, and the construction chokepoint that makes the invariant hold.

for a principal

Frame it as a design lever: when to introduce canonicalization in your own system (compiler symbol tables, protocol tags, repeated JSON field names), what lifetime policy the table needs, and why publishing the guarantee explicitly, the way Scheme does, beats leaving callers to infer it.

## The three relations When two expressions are compared, a language can mean one of three things. **Reference identity**: the two expressions denote the same storage. **Value equality**: the two objects have equivalent content according to the type. **Canonical identity**: the type guarantees that equivalent content is *always represented by the same object*, which collapses the first two into one. Interning (also called canonicalization, or hash-consing when it is applied recursively to a whole tree) is the technique that produces the third. On construction, the runtime looks the value up in a table of already-created instances and hands back the existing one. Equality then costs a pointer compare, memory is shared, and the value can be used as a key in an identity-keyed map. ## Where it is a guarantee **Erlang and Elixir atoms.** Every atom is an entry in a global atom table; the term itself is an index. `:ok == :ok` is a machine-word comparison, which is why atoms are the idiomatic tag for messages and return tuples. The cost is a table with a hard limit (default around one million entries) that is not garbage-collected the way ordinary terms are. Converting attacker-controlled strings with `String.to_atom/1` is a documented denial-of-service vector; the safe form is `String.to_existing_atom/1`. **Lisp and Scheme symbols.** In Common Lisp, `intern` is literally the operation that reads a name into a package and returns the canonical symbol, and `eq` on symbols is reliable. Scheme is unusually honest: R7RS guarantees `eq?` for symbols and the empty list and leaves `eq?` on numbers and characters *unspecified*, offering `eqv?` and `equal?` as the next rungs. The language tells you exactly where the shortcut is legal instead of leaving you to infer it from observed behaviour. **Ruby symbols** are unique and frozen. Ruby 2.2 made dynamically created symbols garbage-collectable precisely because the old permanent table was a memory-exhaustion vector, the same lesson Erlang encodes in `to_existing_atom`. **JavaScript** ships both designs at once: `Symbol("x")` creates a fresh unique value every time, while `Symbol.for("x")` consults a cross-realm global registry and returns the canonical one. Two calls to `Symbol.for` are identical; two calls to `Symbol` never are. ## Where it only appears to work **Java** caches boxed `Integer` values in at least -128..127 and interns compile-time string constants into a pool, so reference comparison happens to succeed for `127` and for two occurrences of the same literal and fails for `128` or a runtime-built string. The cache range is mandated as a minimum, but the observable effect is a coincidence you must not build on. **CPython** interns short identifier-like strings and small integers. Because programs kept relying on it, CPython 3.8 added a SyntaxWarning when `is` is used against a literal. `"aa" is "aa"` may be true while `"a" * 2 is "aa"` is false, on the same interpreter, in the same file. **Objective-C** stores small `NSNumber` values inside the pointer itself (tagged pointers), so pointer comparison succeeds for some numbers and fails for larger ones on the same runtime. **.NET** interns literals per process and offers `string.Intern`, whose entries are never collected for the life of the AppDomain. ## What canonicalization requires in exchange Three things. First, **immutability**: a canonical instance is shared by every holder, so a mutation is a global mutation. Every language above interns only immutable values. Second, **a lifetime story**: the table is a leak by construction, which is why atom tables have limits, Ruby made symbols collectable, and `string.Intern` carries a warning in its own documentation. Third, **a construction chokepoint**: if a value can be built without going through the table, the invariant is void. ## Where you would use it deliberately Compilers intern identifiers so that name comparison during resolution is a pointer compare. Parsers such as Jackson intern field names because the same keys repeat across millions of documents. Erlang interns protocol tags. In all three cases the type is immutable and construction goes through one door. The rule to carry away: reach for identity-as-equality only when you can name the guarantee, and prefer a language that says the guarantee out loud (Scheme's `eq?` wording, Elixir's `to_existing_atom`) over one where you inferred it from a REPL session.

  • Why do languages that guarantee canonical values always make those values immutable?
    A canonical instance is shared by every holder of that value, so mutating it would change the value seen by unrelated code across the whole program. Atoms, symbols and interned strings are therefore immutable by construction. Interning a mutable type would turn a local write into a global one.
  • What is the memory cost of interning, and how have languages mitigated it?
    The table retains every distinct value ever created, so unbounded interning is a leak. Erlang caps the atom table and offers to_existing_atom; Ruby 2.2 made dynamically created symbols garbage-collectable; .NET's string.Intern entries live for the process. The mitigation is either a bounded, trusted input domain or collectable table entries.
  • Scheme exposes eq?, eqv? and equal?. Why three rather than one?
    They form a ladder of increasing cost and decreasing implementation freedom: eq? is a pointer-level test guaranteed only for symbols and the empty list, eqv? adds well-defined behaviour for numbers and characters, and equal? recurses structurally. Publishing all three lets the standard leave implementations free to intern or not, without programs depending on an accident.

An interning table is a coat check that hands the same ticket to identical coats: comparing tickets works only while the cloakroom is the sole way in, and nobody is allowed to alter a coat after checking it.

saying these in an interview costs you the question

  • Claiming reference comparison works for strings or small integers 'in general' because it worked in a REPL
  • Treating an interning cache as part of the language contract rather than an optimization
  • Interning values that are later mutated, so one holder's write is seen by every other holder
  • Assuming interning is free memory-wise, with no answer for how the table is bounded or reclaimed
  • Not knowing any language where identity comparison is actually guaranteed sound

context

resolving links…

open as a page

Some standard libraries let a hash container carry its own equality: C++'s std::unordered_map takes Hash and KeyEqual template arguments, and .NET's Dictionary<TKey,TValue> accepts an IEqualityComparer<T> at construction. Others fix the relation on the key type — java.util.HashMap has no such hook, and Go's map always uses the language's == operator. Suppose you need one case-insensitive, Unicode-normalised index over strings while ordinary string equality stays exact everywhere else in the program. How do you build that on each side of the divide, and what is the design argument for the keying relation belonging to the container rather than to the type?

level: seniorimportance: should knowfreq 38%

basics

~20 s

A lookup relation belongs to the index, not the type. C++ and .NET let a container carry its own hash-and-equality pair; Java's HashMap and Go's map cannot, so you canonicalise or wrap the key instead. Never loosen the type's own equality.

open as a page

Some languages give certain types no stable reference identity at all: structs are copied on assignment, or values are moved. How do you model an entity whose identity must persist in such a language, and what changes once the entity crosses a process or storage boundary?

level: principalimportance: should knowfreq 33%

basics

~20 s

Reify identity as a field. Go copies structs on assignment, Swift gives === only to classes, Rust moves values and offers Rc::ptr_eq only on request. No address survives serialization anywhere, so entities carry an explicit key and compare by it.

open as a page