2024年PHP日本大会

    Set 类

    (PECL ds >= 1.0.0)

    介绍

    Set 是一个唯一值的序列。此实现使用与Ds\Map相同的哈希表，其中值用作键，映射值被忽略。

    优势

    • 值可以是任何类型，包括对象。
    • 支持数组语法（方括号）。
    • 保留插入顺序。
    • 当大小下降到足够低时，会自动释放分配的内存。
    • add()、remove()和contains()都是O(1)。

    劣势

    • 不支持push()、pop()、insert()、shift()或unshift()。
    • 如果在访问索引之前的缓冲区中存在已删除的值，则get()为O(n)，否则为O(1)。

    类概要

    class Ds\Set implements Ds\Collection, ArrayAccess {
    /* 常量 */
    const int MIN_CAPACITY = 16;
    /* 方法 */
    public add(mixed ...$values): void
    public allocate(int $capacity): void
    public capacity(): int
    public clear(): void
    public contains(mixed ...$values): bool
    public copy(): Ds\Set
    public diff(Ds\Set $set): Ds\Set
    public filter(callable $callback = ?): Ds\Set
    public first(): mixed
    public get(int $index): mixed
    public intersect(Ds\Set $set): Ds\Set
    public isEmpty(): bool
    public join(string $glue = ?): string
    public last(): mixed
    public map(callable $callback): Ds\Set
    public merge(mixed $values): Ds\Set
    public reduce(callable $callback, mixed $initial = ?): mixed
    public remove(mixed ...$values): void
    public reverse(): void
    public reversed(): Ds\Set
    public slice(int $index, int $length = ?): Ds\Set
    public sort(callable $comparator = ?): void
    public sorted(callable $comparator = ?): Ds\Set
    public sum(): int|float
    public toArray(): array
    public union(Ds\Set $set): Ds\Set
    public xor(Ds\Set $set): Ds\Set
    }

    预定义常量

    Ds\Set::MIN_CAPACITY

    变更日志

    版本 描述
    PECL ds 1.3.0 该类现在实现了ArrayAccess。
    PECL ds 1.2.7 添加了Ds\Set::map()方法。

    目录

    发现问题？

    了解如何改进此页面 • 提交拉取请求 • 报告错误
    ＋添加注释

    用户贡献注释 2 条注释

    19
    匿名
    6 年前
    集合的查找操作应该为 O(1)。这对于任何语言中的集合和哈希表（例如映射）都是正确的。

    实现这一点的方法是集合存储值的方式与数组不同。

    在数组中，值是根据它们在数组中的位置以及该数组在内存中的位置顺序存储的，因此要查找项目，需要顺序扫描数组以查找项目（除非它是一个排序数组，然后可以使用 O(logn) 的二分查找）。

    集合声明一块内存，就像数组一样，但是它们不是像数组一样顺序地将项目放入内存中，而是通过将项目通过哈希函数（本质上是一个接收对象并返回均匀分布的、非常大的随机数的函数）来确定要添加项目的索引，然后将哈希函数的结果对它们拥有的内存块的大小取模。

    因此，当调用 contains($needle, $mySetHaystack) 时，php 将获取 $needle，并将其输入哈希函数，该函数将返回一个很大的数字，例如 9283472378，然后它获取 $mySetHaystack 的长度（假设为 31），并执行 9283472378 % 31 = 28，因此它检查 $mySetHaystack 的第 28 个索引以查看 $needle 是否在那里。此操作列表中的所有内容都独立于 $mySetHaystack 的大小，因此性能为 O(1)。

    如果哈希函数对两个不同的项目返回相同的值（哈希冲突，这完全会发生），或者如果该值的模相同，则在该索引处的集合中存储一个值数组。由于集合不允许重复值，因此这种情况很少发生，从性能角度来看可以忽略不计。

    您应该查看维基百科关于哈希表的页面（类似于集合），因为有很多图片可以使这个概念更容易理解。
    7
    Sebastien
    2 年前
    一个好处是类型感知。array_unique() 会丢失值（无论使用什么标志），而 Ds\Set 会保留它们。

    <?php

    $array     = [true, false, null, '', 0, '0', 123, '123'];
    var_dump(array_unique($array));
    var_dump(new \Ds\Set($array));

    /*

    结果：

    array(4) {
    [0]=> bool(true)
    [1]=> bool(false)
    [4]=> int(0)
    [6]=> int(123)
    }
    object(Ds\Set)#1 (8) {
    [0]=> bool(true)
    [1]=> bool(false)
    [2]=> NULL
    [3]=> string(0) ""
    [4]=> int(0)
    [5]=> string(1) "0"
    [6]=> int(123)
    [7]=> string(3) "123"
    }

    */
    ＋添加注释
    To Top