In this article, we'll be implementing a Map and a Set in Php which both allow for objects to be used as their keys and values. We'll introduce the core concepts, then show the full code implementation.
Maps and Associative Arrays
- Set a key value pair in the map. If the key already exists, it should overwrite the previous value.
- Accept keys which are strings, numbers, or objects.
- Check if keys exist in the map.
- Remove keys, and their values, from the map.
- Keep track of how many key value pairs are in the map.
- Be iterable with Php's foreach loop.
Implementing a Map
We'll cover each concern in more detail in the sections below.
Creating the Keys
We can implement this logic in its own private function so that other methods in the class can re-use it:
Note that with this strategy, there is a small possibility that there will be a key collision between a key provided as a string and a string generatd by spl_object_hash, but the chances of this so small that we will ignore this possibility in our implementation. If, however, you wanted to remove this possibility entirely, you can use multiple assoc arrays, one for key strings and one for object hash strings, to ensure that such a collision does not cause values to be overwritten. Also note that spl_object_hash values are re-used internally by Php: when an object is destroyed, its spl_object_hash string might be re-used for some other object. However, this will not pose a problem for our implementation, as we will be storing the object references for our keys, thus the object will not be destroyed by garbage collection.
Storing the Keys and Values
Since our map needs to be able to return the keys and values upon request, we will need to maintain a mapping between the actual keys provided by the user and the keys we generate with our getAssocKey method. If we do not store the keys seperately, we will not be able to return a list of keys and it will be possible that any keys which are objects will be collected by garbage collection if they have no other references. To solve these issues, our map will contain two associative arrays, one to map hashed-keys to values, and one to map hashed-keys to original keys. When we make insertions, we will need to insert to both assoc arrays, and when we make deletions, we will need to delete from both assoc arrays. When we make retrievals or check for key existance, we will need to be careful when dealing with keys that don't exist. If you try to access a key from an assoc array, and that key does not exist in that array, Php will most likely log a warning, or even an error. To prevent this, we can use array_key_exists to check without causing any warnings or errors.
Size and Iteration
To keep track of the number of elements, we will use a $count variable. When we call set, we will increment it only if the key was not already present in the map. When we call delete, we will decrement it only if the key was present. We can expose the property with a class method to fall inline with most map implementations. This will also facilitate iteration. In our class, we will implement the Iterator interface so that consumers can iterate over the map with a foreach loop. Our implementation is almost exactly the same as the implementation shown on Php's Iterator documentation, so we will not describe it in detail here.
Full Map Implementation
The implementation below brings everything we've discussed into one place. We've also added a few bells and whistles, such as addMany to add more than one thing at once and the ability to initialize the Map via constructor parameter.
Implementing a Set
We can implement a set using a similar strategy to what we've just used for the Map. We will carry over our getAssocKey method and keyMap object, but we will not carry over the valueMap object. When we make insertions and deletions, we will only update the keyMap object, and when we retrieve values in the set, we will return the values in the keyMap. We will be treating values in our Set in the same manner we treated keys in our Map. Other than this difference, the implementation is almost exactly the same as that of the Map.
Full Set Implementation
Similar to our Map implementation, we've added some bells and whistles here as well.