4

目前我有一个名为Collection. 它使用一个数组来保存一组独特的对象。它们是唯一的，不是因为它们具有不同的内存地址（尽管显然它们确实如此），而是因为集合中没有等效的对象。

我一直在阅读关于SplObjectStorage哪个比数组具有显着的速度优势并且可能比我的Collection班级更容易维护的信息。我的问题是它SplObjectStorage不关心等同性，只关心身份。例如：

class Foo {
  public $id;

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

  function equals(self $obj){
    return $this->id==$obj->id;
  }
}

$f1a = new Foo(1);
$f1b = new Foo(1);//equivalent to $f1a
$f2a = new Foo(2);
$f2b = $f2a; //identical to $f2a

$s=new SplObjectStorage;
$s->attach($f1a);
$s->attach($f1b);//attaches (I don't want this)
$s->attach($f2a);
$s->attach($f2b);//does not attach (I want this)

foreach($s as $o) echo $o->id; //1 1 2, but I wish it would be 1 2

所以我一直在考虑如何子类化SplObjectStorage，这样它attach()就会受到对象等效性的限制，但到目前为止，它涉及将$data对象设置为“等效签名”，这似乎需要遍历数据结构，直到我找到（或没有）一个匹配的值。

例如：

class MyFooStorage extends SplObjectStorage {

  function attach(Foo $obj){
    $es=$obj->id;
    foreach($this as $o=>$data) {//this is the inefficient bit
      if($es==$data) return;
    }
    parent::attach($obj);
    $this[$obj]=$es;
  }
}

有没有更好的办法？

4

1 回答 1

3

如果唯一定义相等的东西是相对于另一个对象，那么恐怕你想要的就是不可能的。想想看，除非我检查每个对象，否则无法确定一个对象是否已经包含在数组中，所以无论如何我都会有 O(n) 的复杂度。

但是，如果您使相等是绝对的，那么这是可能的。为此，您必须为每个对象生成一个哈希值。当且仅当它们的哈希值相等时，两个对象才会相等。一旦你有了它，你就可以用 HashMap 实现 O(1)。

在幕后，这正是 SplObjectStorage 所做的，将对象的地址作为其哈希值。

于 2011-03-04T21:26:12.830 回答