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;
(* .. *)

backtrace指向hashtbl.ml:

致命错误:异常Stack_overflow在文件"hashtbl.ml"处引发,第54行,字符16-40从文件"img/write_bmp.ml",第150行,字符52-108调用...

任何提示？

Answer 1

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

通常,最长链的长度为2或3,因此不会经常出现此错误也就不足为奇了.

看看我的hashtbl.ml(OCaml 3.12.1)的副本,我在第54行看不到任何非尾递归的东西.所以我的猜测可能是错的.在第54行,为哈希表分配新的内部数组.所以另一个想法就是你的哈希表太大了(可能是由于不必要的重复).

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