反向字符串比较

Reverse string comparison

本文关键字：比较 字符串      更新时间：2023-09-26

我使用的是Dictionary（关联数组、哈希表、这些同义词中的任何一个）。

用于唯一标识值的键是相当长的字符串。然而，我知道这些弦往往在尾部而不是头部有所不同。

在JS对象中查找值的最快方法是测试object[key]，但在一个相当大的字典（+1000个条目）中，超长、基本相似的键（+100个字符？

对于这种情况，是否有其他选择，或者这是一个完全没有意义的问题，因为通过键访问值已经快得离谱了？

长话短说；这并不重要。JS将在内部使用一个哈希表（正如您自己所说的），因此它需要计算密钥的哈希，以便插入和（在某些情况下）访问元素。

计算哈希（对于大多数合理的哈希函数）对于长键来说比短键需要稍长的时间（我猜大约线性更长），但变化是在尾部还是在头部并不重要。

您可以决定滚动自己的哈希，以某种方式缓存这些哈希，并将其用作密钥，但这将由您来处理哈希冲突。很难比默认实现做得更好，而且几乎可以肯定不值得麻烦。

此外，对于只有1000个元素的关联数组，这些可能都无关紧要。现代CPU每秒可以处理接近/大约数十亿条指令。即使只是在整个阵列中进行线性搜索，也可能表现得很好，除非你必须经常这样做。

Hash表（字典、映射等）首先检查哈希代码，然后，如果有必要（在冲突的情况下-至少两个键具有相同的哈希代码），则执行equals。如果您遇到性能问题，您必须检查的第一件事IMHO是哈希代码冲突。可能会出现（糟糕的实现或奇怪的密钥），比如说，哈希代码是根据3个第一个字符计算的（当然，这是一种夸张的说法）：

  "abc123".hashCode() ==  
  "abc456".hashCode() ==
  ...
  "abc789".hashCode()

所以你有很多碰撞，必须执行等于，最后减慢O（N）复杂性例程。在这种情况下，你必须考虑一个更好的散列。

相关文章：