Just listen to Alex

July 21, 2011

PHP: Using objects as keys for a hash

Filed under: Uncategorized — bosmeeuw @ 1:58 pm

Hashes, or “associative arrays” are the bread and butter of PHP. Pretty much every PHP project will contain arrays this:

$peopleById = array(1234 => 'Alex', 1235 => 'Jimmy');

If you’re using PHP in an object oriented way, you might want to use hashmaps of objects, and you might want to use your objects as keys. So you try something like this:

class Author {
    public $name;

    function __construct($name) {
        $this->name = $name;
    }
}

class Book {
    public $name;

    function __construct($name) {
        $this->name = $name;
    }
}

$booksByAuthor = array();

$author = new Author("Ian McEwan");

$booksByAuthor[$author] = array(new Book("Atonement"), new Book("Solar"));

However, PHP will throw a “Warning: Illegal offset type” when trying to use the Author object as a key, and your array will be empty.

Fear not, we can fix this, with our very own hashmap class! Only one change to the code is needed:

$booksByAuthor = new HashMap();

$author = new Author("Ian McEwan");

$booksByAuthor[$author] = array(new Book("Atonement"), new Book("Solar"));

Unfortunately, it probably isn’t possible (or I haven’t found out how) to use a standard foreach($hash as $key => $value) to loop over this HashMap, but we can use this form:

foreach($booksByAuthor->keys() as $author) {
    foreach($booksByAuthor[$author] as $book) {
        echo $author->name . " wrote " . $book->name . "<br />";
    }
}

You can use $booksByAuthor->values() to loop over the values.

By default, this hashmap uses object identity to keep the keys apart. This means that if you create two objects, they will represent a different key, even if their values are exactly the same. For example, the assertion below will fail:

class Customer {
    public $id;

    function __construct($id) {
        $this->id = $id;
    }
}

$customer = new Customer(123);
$sameCustomer = new Customer(123);

$creditPerCustomer = new HashMap();

$creditPerCustomer[$customer] = 1000;
$creditPerCustomer[$sameCustomer] = 1500;

assert($creditPerCustomer[$customer] == 1500);

Because “sameCustomer” is a different object, the value will remain at 1000 and the assertion will fail, even though we might want to treat it as an equivalent key. We can fix this by having Customer implement interface HashCodeProvider, like this:

class Customer implements HashCodeProvider {
    public $id;

    function __construct($id) {
        $this->id = $id;
    }

    public function getHashCode() {
        return $this->id;
    }
}

$customer = new Customer(123);
$sameCustomer = new Customer(123);

$creditPerCustomer = new HashMap();

$creditPerCustomer[$customer] = 1000;
$creditPerCustomer[$sameCustomer] = 1500;

assert($creditPerCustomer[$customer] == 1500);

Your getHashCode() method can return any scalar value (int, string, etc), as long as it really represents the identity of the object.

You can grab the simple code for the HashMap class below. Happy hashing!

interface HashCodeProvider {
    public function getHashCode();
}

class HashMap implements ArrayAccess {

    private $keys = array();

    private $values = array();

    public function __construct($values = array()) {
        foreach($values as $key => $value) {
            $this[$key] = $value;
        }
    }

    public function offsetExists($offset) {
        $hash = $this->getHashCode($offset);

        return isset($this->values[$hash]);
    }

    public function offsetGet($offset) {
        $hash = $this->getHashCode($offset);

        return $this->values[$hash];
    }

    public function offsetSet($offset, $value) {
        $hash = $this->getHashCode($offset);

        $this->keys[$hash] = $offset;
        $this->values[$hash] = $value;
    }

    public function offsetUnset($offset) {
        $hash = $this->getHashCode($offset);

        unset($this->keys[$hash]);
        unset($this->values[$hash]);
    }

    public function keys() {
        return array_values($this->keys);
    }

    public function values() {
        return array_values($this->values);
    }

    private function getHashCode($object) {
        if(is_object($object)) {
            if($object instanceof HashCodeProvider) {
                return $object->getHashCode();
            }
            else {
                return spl_object_hash($object);
            }
        }
        else {
            return $object;
        }
    }

}
Advertisements

4 Comments »

  1. Hi Alex,

    nice write-up. Regarding the standard foreach issue for your custom hashmap object, have you tried to implement the Iterator or ArrayIterator classes, since ArrayAccess is no Iterator.

    Comment by Michaël — July 21, 2011 @ 2:17 pm

  2. Hiya Mikkel, long time no hear :)

    I tried implementing Iterator, but the key() method is documented as follows:

    /**
    * (PHP 5 > 5.1.0)
    * Return the key of the current element
    * @link http://php.net/manual/en/iterator.key.php
    * @return scalar scalar on success, integer
    * 0 on failure.
    */
    public function key();

    So PHP expects key() to return a scalar, and true enough, if I return an object, I get a warning and the foreach loop doens’t work properly. So I think the standard foreach loop just doesn’t support objects for the key variable, only scalars :\

    Comment by bosmeeuw — July 21, 2011 @ 2:40 pm

  3. Indeed, hadn’t looked it up. Seems like the only way around this is probably creating a custom Iterator. When I look at some PHP 5.3 Iterators in the SPL docs, I see that there are iterators where the key function gets overwritten to handle strings or mixed values.

    http://www.php.net/manual/en/book.spl.php

    Comment by Michaël — July 21, 2011 @ 3:00 pm

  4. Use `spl_object_hash()`.

    > Description
    >
    > string spl_object_hash ( object $obj )
    > This function returns a unique identifier for the object. This id can be used as a hash key for storing objects or for identifying an object.

    Comment by moteutsch — May 4, 2013 @ 7:13 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: