Implementing a Simple Map Data Structure in Go

This challenge asks you to implement a basic map data structure in Go, focusing on core operations like insertion, retrieval, and deletion. Understanding how maps work internally is crucial for efficient data storage and manipulation, and this exercise will solidify your grasp of Go's map functionality while also providing a deeper understanding of data structures.

Problem Description

You are tasked with creating a simplified map implementation in Go. This map will store key-value pairs where both keys and values are integers. Your implementation should include the following operations:

• Insert(key, value int): Adds a new key-value pair to the map. If the key already exists, update the existing value with the new value.
• Get(key int) (int, bool): Retrieves the value associated with the given key. Returns the value and a boolean indicating whether the key exists in the map. If the key doesn't exist, return 0 and false.
• Delete(key int): Removes the key-value pair associated with the given key from the map. No return value is needed.
• Size() int: Returns the number of key-value pairs currently stored in the map.

Your map should handle collisions gracefully. For simplicity, you can use a linear probing strategy for collision resolution. The map should be implemented as a struct with a fixed-size underlying array.

Examples

Example 1:

Input:
Insert(1, 10)
Insert(2, 20)
Get(1)
Get(2)
Get(3)
Delete(1)
Get(1)
Size()

Output:

(10, true)
(20, true)
(0, false)
(0, false)
2

Explanation: The map starts empty. We insert (1, 10) and (2, 20). Get(1) returns (10, true), Get(2) returns (20, true), and Get(3) returns (0, false). Deleting key 1 removes the (1, 10) pair. Get(1) now returns (0, false). Finally, Size() returns 2 (representing the remaining (2, 20) pair).

Example 2:

Input:
Insert(1, 10)
Insert(1, 15)
Get(1)
Size()

Output:

(15, true)
1

Explanation: The map starts empty. We insert (1, 10). Then, we insert (1, 15), which updates the value associated with key 1 to 15. Get(1) returns (15, true). Size() returns 1.

Example 3: (Edge Case - Full Map)

Input:
Assume map size is 3.
Insert(1, 10)
Insert(2, 20)
Insert(3, 30)
Insert(4, 40) // Attempt to insert when full
Get(1)
Size()

Output:

(10, true)
3

Explanation: The map has a fixed size of 3. The first three insertions succeed. The fourth insertion (4, 40) will fail silently (no error is returned, the map remains full). Get(1) returns (10, true), and Size() returns 3.

Constraints

• The underlying array size for the map will be 10.
• Keys and values are integers.
• The Insert operation should handle key collisions using linear probing. If a collision occurs, probe the next available slot in the array.
• The Get operation should also use linear probing to find the key if it's not in the initial slot.
• The Delete operation should mark the slot as available for future insertions (e.g., by setting the key and value to a default value like 0). It does not need to rehash the map.
• Performance: The average time complexity for Insert, Get, and Delete should be close to O(1). Worst-case (all keys collide) should be O(n) where n is the map size.

Notes

• Consider using a sentinel value (e.g., -1) for keys to indicate that a slot is empty or has been deleted. This helps distinguish between an empty slot and a slot containing a valid key.
• Linear probing can lead to clustering, which can degrade performance. For this simplified implementation, focus on correctness rather than optimizing for clustering.
• You are not required to implement resizing or rehashing. The map size is fixed at 10.
• Focus on the core map operations and collision handling. Error handling beyond the "key not found" scenario is not required.
• The goal is to demonstrate understanding of map concepts and collision resolution, not to create a production-ready map implementation.