hashtable - Stackoverflow 与专门的 Hashtbl(通过 Hashtbl.make)

Question

我正在使用这段代码，并且会触发stackoverflow，如果我使用Extlib的Hashtbl则不会发生错误。有没有关于在没有 stackoverflow 的情况下使用专门的 Hashtbl 的提示？

module ColorIdxHash = Hashtbl.Make(
  struct
    type t = Img_types.rgb_t
    let equal = (==)
    let hash = Hashtbl.hash
  end
)
(* .. *)
let (ctable: int ColorIdxHash.t) = ColorIdxHash.create 256 in
    for x = 0 to width -1 do
      for y = 0 to height -1 do
        let c = Img.get img x y in
        let rgb = Color.rgb_of_color c in
          if not (ColorIdxHash.mem ctable rgb) then ColorIdxHash.add ctable rgb (ColorIdxHash.length ctable)
      done
    done;
(* .. *)

回溯指向 hashtbl.ml:

Fatal error: exception Stack_overflow Raised at file "hashtbl.ml", line 54, characters 16-40 Called from file "img/write_bmp.ml", line 150, characters 52-108 ...

有什么提示吗？

Answer 1

嗯，您正在使用物理相等 (==) 来比较哈希表中的颜色。如果颜色是结构化值(我无法从这段代码中看出)，那么它们在物理上不会彼此相等。如果所有颜色都是不同的对象，它们都会进入表中，这实际上可能是相当大量的对象。另一方面，哈希函数将基于实际的颜色 R、G、B 值，因此很可能存在大量重复项。这意味着您的哈希桶将具有很长的链。也许某些内部函数不是尾递归的，因此会溢出堆栈。

通常最长链的长度为 2 或 3，因此这个错误不经常出现也就不足为奇了。

查看我的 hashtbl.ml (OCaml 3.12.1) 副本，我在第 54 行没有看到任何非尾递归的内容。所以我的猜测可能是错误的。第 54 行为哈希表分配了一个新的内部数组。因此，另一个想法是您的哈希表变得太大(可能是由于不需要的重复项)。

可以尝试的一件事是使用结构相等 (=) 并查看问题是否消失。