2
\$\begingroup\$

I started creating a Dictionary class that accepts objects as there keys:

class Dictionary
    implements ArrayAccess
{    
    private $_keys = array();

    private $_values = array();

    public function offsetExists( $key )
    {
        return false !== array_search( $key, $this->_keys, true );
    }

    public function offsetGet( $key )
    {
        if( false === ( $index = array_search( $key, $this->_keys, true ) ) )
        {
            throw new OutOfBoundsException( 'Invalid dictionary key' );
        }

        if( !isset( $this->_values[ $index ] ) )
        {
            throw new LogicException( 'No matching value found for dictionary key' );
        }

        return $this->_values[ $index ];
    }

    public function offsetSet( $key, $value )
    {
        if( false !== ( $index = array_search( $key, $this->_keys, true ) ) )
        {
            $this->_values[ $index ] = $value;
        }
        else
        {
            $this->_keys[] = $key;
            $this->_values[] = $value;
        }
    }

    public function offsetUnset( $key )
    {
        if( false === ( $index = array_search( $key, $this->_keys, true ) ) )
        {
            throw new OutOfBoundsException( 'Invalid dictionary key' );
        }

        if( !isset( $this->_values[ $index ] ) )
        {
            throw new LogicException( 'No matching value found for dictionary key' );
        }

        array_splice( $this->_keys, $index, 1 );
        array_splice( $this->_values, $index, 1 );
    }
}

It works pretty well for the very elementary test cases I've done so far. However, I'm worried about three things:

  1. Can you think of a situation where $this->_keys and $this->_values will not be synchronized with each other anymore, thus leading to data corruption? I thought maybe there could occur a situation where something might happen between the two array_splices, for instance, in:

    public function offsetUnset( $key )
    {
        ...
    
        array_splice( $this->_keys, $index, 1 );
        array_splice( $this->_values, $index, 1 );
    

    ... leading to data corruption.

  2. I feel array_search() might be inefficient, but I specifically don't want to resort to using spl_object_hash() as keys (and thereby circumventing the need for an internal keys and values array) as I belief this is not bulletproof, as it doesn't guarantee hash uniqueness for objects at all.

  3. I feel array_splice() might be inefficient, but I don't want to resort to unset() as I feel this could lead to unwieldy internal arrays keys eventually. I'd like to keep the internal arrays keys as tightly packed as possible.

Looking forward to your feedback.

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

First, I do have to say that you look like you are re-inventing the wheel. You can get all of that with SplObjectStorage. Since you're using OutOfBoundsException, you're already using the Spl types.


To your specific questions:

  1. It is hard to think of such a situation, but that doesn't mean that it is inconceivable.
  2. While spl_object_hash is not guaranteed unique, it is highly likely that you will run out of memory far before encountering a hash collision. As the documents state: A string that is unique for each currently existing object and is always the same for each object. It is both faster and cheaper than keeping/maintaining your own internal state.
  3. Yes, the internal keys will not be quite as ordered in the internal arrays, but it will only make a substantial difference if you actually have a problem keeping the two arrays synced — basically, if you can get #1 to work consistently and without fail, then unset will not matter here.
\$\endgroup\$
0
0
\$\begingroup\$

I stumbled upon your implementation and I can really appreciate it - I think this will work well for most people without extreme engineering.

Unfortunately, spl_object_hash is just a string representation of the object reference in memory. For example, if you create two copies of the same array: array( 'a' => 1, 'b' => 2 ), each object will return a different spl_object_hash.

Other languages (such as Java and C#) have a concept of Equatable objects. Equatable objects do 2 things:

  1. GetHashCode()
  2. IsEqual( $other ) - this seems to be what your array_search() is doing.

BUT (pay careful attention here) GetHashCode() IS NOT COMPLETELY UNIQUE. GetHashCode() is 2 different things:

  • Consistent!
  • FAST!

The idea here is that you can reduce the array passed to array_search VERY QUICKLY using GetHashCode(), THEN you find the actual match using array_search()/IsEqual().

The code might look something like this:

$objectiveLookup = new ObjectiveLookup();

//create an association between $obj1 and $val1
$objectiveLookup[ $obj1 ] = $val1;

//Here's what actually happens:
 {
    $hash_code = $obj1->GetHashCode();
    if( !isset( $objectiveLookup->_similarValues[ $hash_code ] ) )
        $objectiveLookup->_similarValues[ $hash_code ] = array();

    //regular array
    $objectiveLookup->_similarValues[ $hash_code ][] = $obj1;

    //this is an SplObjectStorage
    $objectiveLookup->_actualValues[ $obj1 ] = $val1;
 }

Then, after thousands, or even millions of objects are in memory, only a fraction of this should be _similarValues.

Because of this, finding values should be MUCH faster:

//this NEW object should be "IsEqual()" to $obj1
$obj1075383 = new CoolObject();

//get a value
$val1 = $objectiveLookup[ $obj1075383 ];

//Here's what actually happens:
 $hash_code = $obj1075383->GetHashCode();
 if( isset( $objectiveLookup->_similarValues[ $hash_code ] ) )
 {
    $similar_values = $objectiveLookup->_similarValues[ $hash_code ];

    //find the one that IsEqual()
    $matching_index = array_search( $similar_values, $obj1075383 );
    $actual_object_key = $similar_values[ $matching_index ];

    $actual_value = $objectiveLookup->_actualValues[ $actual_object_key ];
    return $actual_value;
 }

Overall, nice work fireeyedboy!!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.