Mappings in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Mappings

O(1)

Understanding Time Complexity

When working with mappings in blockchain, it's important to know how fast we can find or store data.

We want to understand how the time to access or update a mapping changes as it grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

mapping(address => uint) public balances;

function updateBalance(address user, uint amount) public {
    balances[user] = amount;
}

function getBalance(address user) public view returns (uint) {
    return balances[user];
}
    

This code stores and retrieves a user's balance using a mapping from addresses to numbers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Direct access to mapping entries by key (address).
• How many times: Each access or update happens once per call, no loops involved.

How Execution Grows With Input

Accessing or updating a mapping entry takes about the same time no matter how many entries exist.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The time stays constant even as the mapping grows larger.

Final Time Complexity

Time Complexity: O(1)

This means accessing or updating a mapping entry takes the same short time no matter how many items are stored.

Common Mistake

[X] Wrong: "Accessing a mapping gets slower as it stores more data."

[OK] Correct: Mappings use a hash-like structure that lets the program jump directly to the data, so size does not slow access.

Interview Connect

Understanding that mappings provide quick access helps you explain efficient data handling in blockchain smart contracts.

Self-Check

"What if we replaced the mapping with an array and searched for the user each time? How would the time complexity change?"

Practice

1. What is the primary purpose of mapping in blockchain smart contracts?

easy

A. To create user interfaces

B. To store a list of all keys used

C. To perform complex mathematical calculations

D. To connect keys to values for fast data lookup

Solution

1. Step 1: Understand the role of mapping

   Mappings are used to link a key to a value, allowing quick access to data based on the key.

2. Step 2: Compare options

   Only To connect keys to values for fast data lookup correctly describes this purpose; others describe unrelated functions.

3. Final Answer:

   To connect keys to values for fast data lookup -> Option D

4. Quick Check:

   Mapping = key-value fast lookup [OK]

Hint: Mappings link keys to values quickly [OK]

Common Mistakes:

• Thinking mappings store all keys explicitly
• Confusing mappings with arrays or lists
• Assuming mappings perform calculations

2. Which of the following is the correct syntax to declare a mapping from address to uint in Solidity?

easy

A. mapping(address, uint) balances;

B. mapping(address => uint) public balances;

C. mapping[address => uint] balances;

D. mapping(address => uint) balances()

Solution

1. Step 1: Recall Solidity mapping syntax

   The correct syntax uses parentheses with key type, arrow, and value type: mapping(keyType => valueType) visibility name;

2. Step 2: Check each option

   mapping(address => uint) public balances; matches the correct syntax. Options A, C, and D have syntax errors like using commas instead of =>, wrong brackets, or function-like declaration.

3. Final Answer:

   mapping(address => uint) public balances; -> Option B

4. Quick Check:

   Correct mapping syntax uses (key => value) [OK]

Hint: Use parentheses and arrow for mapping syntax [OK]

Common Mistakes:

• Using square brackets instead of parentheses
• Missing visibility keyword like public
• Using commas instead of =>

3. Consider the Solidity code:

mapping(address => uint) public balances;

function setBalance(address user, uint amount) public {
  balances[user] = amount;
}

function getBalance(address user) public view returns (uint) {
  return balances[user];
}

// After calling setBalance(0x1234..., 50), what does getBalance(0x1234...) return?

medium

A. 50

B. Error

C. Undefined

D. 0

Solution

1. Step 1: Understand setBalance effect

   The function sets the balance of the given address to the specified amount, here 50.

2. Step 2: Understand getBalance output

   Calling getBalance with the same address returns the stored value, which is 50.

3. Final Answer:

   50 -> Option A

4. Quick Check:

   Set then get returns stored value [OK]

Hint: Set value then get returns that value [OK]

Common Mistakes:

• Assuming default zero is returned after setting
• Thinking mapping keys are enumerable
• Expecting an error for unset keys

4. What is wrong with this Solidity code snippet?

mapping(address => uint) balances;

function addBalance(address user, uint amount) public {
  balances[user] += amount;
}

function getBalance(address user) public view returns (uint) {
  return balances[user];
}

medium

A. The mapping is missing initialization before use

B. The mapping keys are not stored, so balances[user] always returns zero

C. There is no error; the code works as expected

D. The mapping is not declared public, so balances cannot be read

Solution

1. Step 1: Check mapping declaration

   Mapping does not need explicit initialization; default values are zero.

2. Step 2: Check function logic

   addBalance adds amount to the current balance; getBalance returns it. Not declaring public means no automatic getter, but manual getter exists.

3. Final Answer:

   There is no error; the code works as expected -> Option C

4. Quick Check:

   Mapping defaults and manual getter work fine [OK]

Hint: Manual getter works even if mapping not public [OK]

Common Mistakes:

• Assuming mapping must be public to read values
• Thinking mappings need explicit initialization
• Confusing mapping keys storage with values

5. You want to track ownership of unique items by users using mappings in Solidity. Which approach correctly allows you to check if a user owns a specific item ID with a direct lookup starting from the user address?

hard

A. mapping(address => mapping(uint => bool)) ownsItem; // nested mapping user to item ID to ownership

B. mapping(uint => address) itemToOwner; // maps item ID to owner address

C. mapping(address => uint) ownerToItem; // stores one item per user

D. mapping(address => uint[]) userItems; // mapping to array of item IDs

Solution

1. Step 1: Understand ownership tracking needs

   We need to check if a user owns a specific item ID, so a direct boolean check is best.

2. Step 2: Analyze options

   Only mapping(address => mapping(uint => bool)) ownsItem; // nested mapping user to item ID to ownership provides a nested mapping(address => mapping(uint => bool)) ownsItem, allowing direct ownsItem[user][itemID] lookup from the user address. A limits to one item per user; B requires starting from item ID; D requires searching an array.

3. Final Answer:

   mapping(address => mapping(uint => bool)) ownsItem; // nested mapping user to item ID to ownership -> Option A

4. Quick Check:

   Nested mapping allows direct ownership check [OK]

Hint: Use nested mapping for user-item ownership check [OK]

Common Mistakes:

• Using single mapping limiting one item per user
• Using arrays which are not mappings
• Confusing item-to-owner with user-to-item ownership check