Phabstractic: Map Data Type

asherwunk/phabstractic now supports the map abstract data type, also known as an associative array or ‘object store’.

Map

To quote Wikipedia:

In computer science, an associative arraymapsymbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

I have implemented what I call a map, or an associative array, in pure PHP.  Truly, it is more than just a map or dictionary, it’s an “object store.”  This is because keys can be any data type, including objects, and values can be any data type, including objects.  This is similar to SplObjectStorage in the PHP standard library.  However, where SplObjectStorage implements Iterator, ArrayAccess, Countable and Serializable, my pure PHP construction only supports Iterator, and ArrayAccess.

The nice thing about having a pure PHP solution is that you have fine grained access to exactly how the data structure works, plus, you can see how the basic mechanics are implemented.

Implementation

The Map data type is composed of two arrays, a keys array, and a values array.  In PHP the traditional ‘built-in’ array can only have scalars (integers or strings and such) as keys, though any data can be a value.  In the Map data type you are able to use objects as keys as well.  This requires the objects as keys to be stored in their own array.

The idea is that there is an array of keys paired with indices.  Each array element is a two element array containing the key, and to what index in the value array that key corresponds to.  This separation of keys and values make it easy to separate out the keys and the values of the Map for further computation.  It’s possible that the Map could also be built by simply associating the key element with the second element in the two element array.

Every time we add an element to the Map we increment an internal counter ( $this->index ) by one and then reference that index in our two element key array.  So, for example, let’s say we execute the following on our Map:

We would end up with the following internal representation:

Construction

There are many options to constructing a Map.  You can pass data in an array as either purely array elements, or as packaged units associating one piece of data with another.  This includes a string representation, a StdClass, or a two element array.  See the comments of the constructor:

As you can see, you can mix multiple data types in an array that you pass to the constructor.

SplObjectStorage Comparison

A Map and a SplObjectStorage object are very similar.  Both associate data with another given piece of data.  The SplObjectStorage definition is provided in the PHP manual as:

The Map data type defines the following manipulation methods as outlined in the corresponding Wikipedia article:

Operations associated with this data type allow:

  • the addition of a pair to the collection
  • the removal of a pair from the collection
  • the modification of an existing pair
  • the lookup of a value associated with a particular key

As you can see, a Map defines all the pertinent functionality that SplObjectStorage also defines.  However, it would be awkward to use SplObjectStorage and Map this way, so it’s been made easier by implementing ArrayAccess.  This means that you can access a Map data type like you would a normal array.  This allows you to use objects as keys ‘in the language’ itself.  An example might be:

This is made possible by our implementation of the ArrayAccess interface:

Iteration

Another handy thing that SplObjectStorage also offers is the ability to be used in a foreach loop.  This is because it implements the Iterator interface.  Well, fortunately, so does our Map data type as well.  This allows you to use a foreach loop with the Map just like you’d use a normal array.  If you specify $key => $value, then $key will actually be the object you specified at definition.  The interface mostly works by simply iterating over the keys of the Map structure, accessing the indices as necessary.  The Iterator interface is implemented as such:

Other Interfaces

SplObjectStorage implements Countable and Serializable.  The Map data structure here does not implement those interfaces.  If you need something that can be serialized, I still recommend using the SplObjectStorage implementation.

Operations

The Map data type actually offers some functionality that the SplObjectStorage class does not.  These include difference, intersection, and frequency counting.

When you want to find out how many times a particular value occurs in a Map without regards to keys you can use the countValues static method.  The idea can be outlined as follows:

countValues is implemented as follows:

The Map data structure can also be combined in various ways with other Maps, including difference, and intersection.  To find out the difference between Maps, or their intersection, you can use the following static methods:

Conclusion

Object stores, associative arrays, and Maps are important data structures.  They are useful in statistical analysis, as well as for in memory database storage, such as a Redis implementation.  The advantage of a map is that you don’t have to remember cryptic index values, as well it allows you to establish an abstract association between two data objects.

(View on Github)

This is part of the Phabstractic Library.

If you appreciate my programming please help support me through my Patreon.

photo credit: Park Avenue between Sunol and Race, San Jose CA via photopin (license)

kadar

I'm just a wunk, trying to enjoy life. I am a cofounder of http//originalpursuitssoc.com/ and I like computers, code, creativity, and friends.

You may also like...

Leave a Reply

%d bloggers like this: