elixir - Elixir O(1)中的 map 查找吗？

Question

基于哈希表的 dict/map 结构提供 O(1)查找时间。然而，我不断看到在 Elixir 中找到匹配的函数头比在 map 中查找内容更快的含义。

例如，Elixir 的 String.Unicode compiles a list of unicode characters into many function heads ，因此通过查找 upcase 的函数头来回答“é 的大写版本是什么”。期望“é”。

我不知道为什么这会比使用单个 upcase 更快或更节省内存。在 map 中查找“é”的函数头。

同样，在“Metaprogramming Elixir”中展示如何构建 I18n 库时，Chris McCord 为每个翻译键指定了自己的函数头，并说:

“By generating function heads for each translation mapping, we again let the Virtual Machine take over for fast lookup.”

Elixir 中的 map 不提供 O(1) 查找吗？ 是否正在寻找匹配的函数头 O(1)？为什么选择为许多函数头编译一个静态列表而不是仅仅将它存储在一个映射中？

Answer 1

Elixir 映射不是基于平面散列表的数据结构。小 map 是 map 有 <= 31 个条目的有序列表。当一个映射获得 32 个条目时，它会更改为具有查找 O(log n) 的哈希树。 .毕竟，基于不可变哈希表的数据结构的更新成本非常高，这是“构建”这些数据结构之一的主要方法。更改一个值将需要您更新仅包含 1 个项目的新 map 。它们基于 Rich Hickey 的持久哈希图，这是一种哈希数组映射树。

函数头匹配复杂度为 O(n)最坏的情况，但可以由编译器以我不完全理解的方式进行优化。在某些情况下，它可以将一些功能头模式变成一棵树。但是因为函数头匹配没有总顺序，并且必须按照定义的顺序匹配，所以优化的数量非常有限。您可能只是幸运地使用了非常低的函数头匹配部分以及函数头匹配顺序的树。

头部匹配的每一步也非常轻量级和高度优化，其中 map 仍然很新，并且需要进行一些性能优化。例如，如果键是复杂/嵌套的，则哈希函数的复杂性并不简单(但是，简单的整数具有非常快的哈希函数)。但是在您的 unicode 示例中，我敢打赌，根据其对 id 的排序方式，unicode 标准将尽可能多的常用字符放在前面。这可能使 VM 很容易优化并获得非常好的查找​​时间。我敢肯定，如果您查找晦涩的字母表，您的复杂性会改变。

但是，不只是动态地生成具有函数匹配的模块作为查找数据的方式的原因是您会破坏全局状态，特别是 code_server 模块。一些查找可能会更快，但随着数据结构变大，加速可能会减慢。