Implementing Maps and Sets in PHP

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

Php provides a native mapping capability with its associative arrays. However, associative arrays do not allow objects to be used as keys. This is different than most Map or HashMap implementations in most languages, which do allow objects to be used as keys. Here, we're going to implement a Map, and a Set, in Php which does allow objects to be used as keys. The map we will be implementing should be able to:

1. Set a key value pair in the map. If the key already exists, it should overwrite the previous value.
2. Accept keys which are strings, numbers, or objects.
3. Check if keys exist in the map.
4. Remove keys, and their values, from the map.
5. Keep track of how many key value pairs are in the map.
6. Be iterable with Php's foreach loop.

Implementing a Map

One way we can implement our map is by implementing a hash table from scratch. However, in this article, we will instead take an approach which re-uses associative arrays so we don't have to do this work from scratch. If you would like to read about creating hash tables from scrach, please visit our introduction to hash tables. There are a few concerns we will need to consider and address in order to implement this Map:

• Mapping objects to keys.
• Storing keys and values for retrieval.
• Iterating through the map.

We'll cover each concern in more detail in the sections below.

Creating the Keys

We will be implementing our map with a class which uses associative arrays internally. In order to do so, we will need to find some way of mapping an object to a string so that we can store that string as the key instead of the object itself. We can use Php's spl_object_hash function to do this. That function will take an object as a parameter and return a hash string corresponding to that object. However, that function does not accept primitive types, so we must implement some additional logic if the key provided to a map is actually a string or object:

• If key is a string: use the key directly for the internal assoc array.
• If key is numeric: cast it to a string and use that for the internal assoc array.
• If key is an object: use spl_object_hash and use the returned string for the internal assoc array.

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.