array 优于 set 还是 map？
Is array preferred over set or map?
我最近面试了湾区（美国加利福尼亚州）的一家公司。其中一个问题是简单地查找字符串是否有重复字符（我已经简化了一个冗长的问题）。
eg:
input : "qwerrty"
output : True
我用 python 编写了这个代码。
我给出了一个解决方案，使用集合来跟踪迭代过程中遇到的元素。
但是面试官希望我使用一个数组[255]来跟踪遇到的字符。
虽然我对使用它们中的任何一个都感到很自在，但我的意见是使用集合只是因为我们在使用数组时浪费了 255 个字符 space。这是因为（众所周知）最初我们创建了一个 arr[255] = 0 所有元素都为零然后将 ASCII 等效索引值递增 1.
另一方面，集合只会在访问的元素上占用内存。
因为他（有点）争论在集合上使用数组，所以我很想知道他在技术上是否正确。在这种情况下，数组优于 set/map 吗？如果是，为什么？
关于这个问题需要注意的一件事是，如果字符串中可能只有 C 个不同的字符，那么对于任何长度为 C+1 或更长的字符串，您可以自动 return甚至没有查看字符串就存在重复项，因为字符太多以至于它们都不是唯一的（这是工作中的鸽巢原则）。这对于思考这个特定问题的结构很重要。
接下来，请注意您甚至不需要一堆计数器。您可以只为每个字符一位，因为您只需要知道在遍历数组时您是从未见过一个字符 (0) 还是在 (1) 之前见过它。这意味着每个字符需要一位。如果您的字大小是 W，这意味着您需要大约 C / W 存储的总机器字数 space 用于基于数组的解决方案。
假设您在一台字长为 32 位 (W = 32) 的机器上使用 C = 256（例如，每个字符都是一个字节值）。这意味着您需要八个机器字来存储位数组，这是一个可以忽略不计的存储量 space 并且可以很容易地初始化为 0。现在，考虑一下您的集合实现。如果你使用散列 table，就会有某种内部数组用于存储所有内容。您还需要 space 来存储有关哈希函数的信息，通常您会在某处缓存集合的大小。仅仅为了大小和哈希函数信息，这将吃掉三个机器字，剩下 space 五个字。如果散列 table 是通用实现的，并且每个条目使用一个机器字，那么如果您的散列 table 包含四个或更少的条目，那么您的方法只会节省 space，这不太可能发生。如果您的散列 table 被优化并直接存储 char 值，那么您最多可以存储五个字的字符（20 个字符）而不会发生任何冲突，但是如果您试图保持较低的负载因子，您可能会在看到 10 个左右的字符后调整 table 的大小。所以简而言之，除非你有一个非常的短字符串，散列table方法可能会使用更多内存，并且开销散列会很高。数组方法可能更快。
另一方面，假设您在字符串中存储任意 Unicode 字符。现在，C = 1,114,112（感谢维基百科），即使使用 64 位字长，您也需要一个包含 17,408 个机器字的数组来为每个可能的字符存储一位。那是 lot 的存储 space 并且需要一段时间来初始化它。现在，如果您作为输入获得的字符串是 "reasonable" 而不是病理构造的，那么您很可能会在字符串中很早就找到重复的元素（如果字符串是完全随机的，那么通过生日悖论平均只需要 √(2C) 个字符就可以得到一个重复项），因此构建哈希 [=49=] 可能需要更少 space。如果字符串是病态构造的，因此每个字符都是唯一的，但是，正在计算的散列函数的常数因子开销、散列 table 调整大小等可能意味着您的方法将比数组慢-基于一个，但这是一个不寻常的用例。
总结一下：
如果可能的字符数很少（想想 ASCII），基于数组的方法可能会更快并且更节省内存。
如果可能的字符数很大（想想 Unicode），基于数组的方法在合理的输入上可能会变慢并且内存效率较低，但对于病态选择的输入可能可能比基于散列的方法更快。
也就是说，您可能会争辩说，除非代码 运行 处于紧密循环中，否则 "just use a set" 以外的任何内容都会使代码难以阅读，对整个程序的好处微乎其微效率。出于这个原因，一个合理的答案是 "use the set unless there's a reason not to, and then switch to the array-based one only if the data supports it."
我相信时间复杂度与 space 复杂度分析是您的面试官正在寻找的实际答案。
Space 明智的，这两种情况都是 O(N)。
在时间上，将字符添加到集合中不是 O(1)，但将 1 添加到数组中的值是 O(1)。
所以一般来说，使用数组会消耗相同数量的内存，但时间要少得多。
我最近面试了湾区（美国加利福尼亚州）的一家公司。其中一个问题是简单地查找字符串是否有重复字符（我已经简化了一个冗长的问题）。
eg: input : "qwerrty" output : True
我用 python 编写了这个代码。
我给出了一个解决方案，使用集合来跟踪迭代过程中遇到的元素。
但是面试官希望我使用一个数组[255]来跟踪遇到的字符。
虽然我对使用它们中的任何一个都感到很自在，但我的意见是使用集合只是因为我们在使用数组时浪费了 255 个字符 space。这是因为（众所周知）最初我们创建了一个 arr[255] = 0 所有元素都为零然后将 ASCII 等效索引值递增 1.
另一方面，集合只会在访问的元素上占用内存。
因为他（有点）争论在集合上使用数组，所以我很想知道他在技术上是否正确。在这种情况下，数组优于 set/map 吗？如果是，为什么？
关于这个问题需要注意的一件事是，如果字符串中可能只有 C 个不同的字符，那么对于任何长度为 C+1 或更长的字符串，您可以自动 return甚至没有查看字符串就存在重复项，因为字符太多以至于它们都不是唯一的（这是工作中的鸽巢原则）。这对于思考这个特定问题的结构很重要。
接下来，请注意您甚至不需要一堆计数器。您可以只为每个字符一位，因为您只需要知道在遍历数组时您是从未见过一个字符 (0) 还是在 (1) 之前见过它。这意味着每个字符需要一位。如果您的字大小是 W，这意味着您需要大约 C / W 存储的总机器字数 space 用于基于数组的解决方案。
假设您在一台字长为 32 位 (W = 32) 的机器上使用 C = 256（例如，每个字符都是一个字节值）。这意味着您需要八个机器字来存储位数组，这是一个可以忽略不计的存储量 space 并且可以很容易地初始化为 0。现在，考虑一下您的集合实现。如果你使用散列 table，就会有某种内部数组用于存储所有内容。您还需要 space 来存储有关哈希函数的信息，通常您会在某处缓存集合的大小。仅仅为了大小和哈希函数信息，这将吃掉三个机器字，剩下 space 五个字。如果散列 table 是通用实现的，并且每个条目使用一个机器字，那么如果您的散列 table 包含四个或更少的条目，那么您的方法只会节省 space，这不太可能发生。如果您的散列 table 被优化并直接存储 char 值，那么您最多可以存储五个字的字符（20 个字符）而不会发生任何冲突，但是如果您试图保持较低的负载因子，您可能会在看到 10 个左右的字符后调整 table 的大小。所以简而言之，除非你有一个非常的短字符串，散列table方法可能会使用更多内存，并且开销散列会很高。数组方法可能更快。
另一方面，假设您在字符串中存储任意 Unicode 字符。现在，C = 1,114,112（感谢维基百科），即使使用 64 位字长，您也需要一个包含 17,408 个机器字的数组来为每个可能的字符存储一位。那是 lot 的存储 space 并且需要一段时间来初始化它。现在，如果您作为输入获得的字符串是 "reasonable" 而不是病理构造的，那么您很可能会在字符串中很早就找到重复的元素（如果字符串是完全随机的，那么通过生日悖论平均只需要 √(2C) 个字符就可以得到一个重复项），因此构建哈希 [=49=] 可能需要更少 space。如果字符串是病态构造的，因此每个字符都是唯一的，但是，正在计算的散列函数的常数因子开销、散列 table 调整大小等可能意味着您的方法将比数组慢-基于一个，但这是一个不寻常的用例。
总结一下：
如果可能的字符数很少（想想 ASCII），基于数组的方法可能会更快并且更节省内存。
如果可能的字符数很大（想想 Unicode），基于数组的方法在合理的输入上可能会变慢并且内存效率较低，但对于病态选择的输入可能可能比基于散列的方法更快。
也就是说，您可能会争辩说，除非代码 运行 处于紧密循环中，否则 "just use a set" 以外的任何内容都会使代码难以阅读，对整个程序的好处微乎其微效率。出于这个原因，一个合理的答案是 "use the set unless there's a reason not to, and then switch to the array-based one only if the data supports it."
我相信时间复杂度与 space 复杂度分析是您的面试官正在寻找的实际答案。 Space 明智的，这两种情况都是 O(N)。 在时间上，将字符添加到集合中不是 O(1)，但将 1 添加到数组中的值是 O(1)。 所以一般来说，使用数组会消耗相同数量的内存，但时间要少得多。