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 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.

    目录

    改进此页面

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

    用户贡献笔记 4 notes

    上
    下
    18
    匿名
    6 年前
    集合的查找应该为 O(1)。 这是任何语言中集合和哈希表（例如映射）的真实情况。

    这是可能的，因为集合以与数组不同的方式存储值。

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

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

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

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

    你应该查看维基百科关于哈希表的页面（类似于集合），因为有很多图片可以使这个概念更容易理解。
    上
    下
    6
    Sbastien
    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));

    /*

    Gives :

    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"
    }

    */
    上
    下
    -19
    rtheunissen at php dot net
    6 年前
    按值查找为 O(1)，按索引查找为 O(n)（如果索引之前有删除的值），否则为 O(1)。
    上
    下
    -37
    vdavila dot sm at gmail dot com
    6 年前
    我有一个问题是 contains() 为 O(1) 吗？ 为什么？
    ＋添加笔记
    To Top