记忆化搜索时候为啥用数组，而不是用hashmap？

Question

在使用记忆化搜索时，为什么通常选择使用数组而不是哈希表呢？将大规模（约两千万）的数组元素初始化为 -1 本身就需要一定的成本。而且这样做之后，数组的利用率如何呢？是否会出现数组中大部分元素并未被实际使用的情况？

Answer 1

liuyubobobo 2024-12-21 00:49:54

1. 

所有使用数组的地方，都可以使用 hashmap 代替。数组可以作为不处理哈希冲突的 hashmap 用。

2.

在现代计算机上，将两千万数组初始化为 -1 的时间成本近乎可以忽略不计。如果论时间成本，大多数时候，hashmap 是远远慢于数组的。因为 hashmap 要计算哈希值，处理哈希冲突，再去寻找值，而数组是直接随机索引到值。对于大多数问题，如果可以使用数组的话，数组的时间性能将比 hashmap 快 4-5 倍，在极端情况下甚至会快 10-20 倍。你可以在算法网站中找一些记忆化搜索或者动态规划的问题来试验，问题越复杂，这个性能差异越明显。

3.

空间的角度，hashmap 也可能浪费空间。如果让 hashmap 不浪费空间，缩小空间，代价就是更多的处理哈希冲突，降低时间性能。hashmap 本来就是在空间不允许的情况下，在统计意义下牺牲常数时间（做哈希冲突处理，需要哈希冲突不要过于频繁），来使得有限空间可以做处理的数据结构。所以如果空间 ok，应该优先选用数组；如果空间确实是 concern，有严格的空间限制，当前内存无法承载所有的可能性，则应该转用 hashmap。

无论是算法比赛中，还是实际应用中，也都存在这类问题。可能是数组范围过大，也可能是处理的是复杂数据（比如结构，时间，字符串等），必须将这些数据映射为哈希值。

继续加油！：）