java - 散列一个长字符串进行比较或比较两个字符串是否更快？

Question

假设我有一个非常长的字符串列表(40-1000 个字符)。用户需要能够在列表中输入一个术语，列表将报告该术语是否存在。

除了存储，将散列与长字符串一起存储是否更有效，然后当用户尝试查找时，它对输入进行散列并将其与散列列表进行比较？

There are similar answers here, but they aren't quite generalized enough.

Answer 1

假设数据适合堆(即内存)，最好的办法是使用 Set(如果每个字符串都有关联的数据，则使用 Map)。将您的存储从列表更改为集合(使用 HashSet)，或者如果您确实还需要列表，则维护一个单独的集合。

计算字符串的hashcode() 的时间与字符串的长度成正比。假设一个正确实现的 hashcode() 和适当大小的 Set，查找字符串的时间相对于集合中的字符串数量是恒定的(一旦计算出哈希码)。

如果您在未排序的列表上使用 equals()，您的查找时间可能与列表中的项目数成正比。如果您保持列表排序，您可以使用比较次数进行二进制搜索，以查找与列表中项目数的日志成比例的字符串(并且每次比较都必须比较字符，直到找到差异)。

从本质上讲，Set 有点像将字符串的哈希码放在手边，但它更进一步，以一种可以非常快速地直接跳转到集合中具有的元素的方式存储数据该哈希码值。

请注意，一旦发现差异，两个字符串的相等比较就可以退出，但可能必须比较两个字符串中的每个字符(当它们相等时)。如果您的字符串具有相似的长前缀，则可能会影响性能。有时，您可以(在性能方面)受益于对数据类型内容的了解。例如，如果您的所有字符串都以相同的 1K 前缀开头并且仅在末尾不同，您可以受益于覆盖 equals() 实现以从末尾到开头进行比较，这样您就可以找到差异早些。