Jac*_*ack 6 language-agnostic floating-point hashtable
我需要存储一对,float,int其中int值存储float我正在开发的工具中使用的模型中出现的值的数量,我想知道这样做是否安全.
在谈论用于直接比较的浮点数(或作为要散列的内容)时,有限精度应该是一个问题所以我认为不鼓励使用类似的方法,我是对的吗？
实际上问题是我没有任何其他信息与这些浮点数相结合所以我根本不能使用其他任何东西作为哈希表的关键,但同时,因为键将很多,具有良好的性能将是不错.
也许最好的解决方案是使用二叉搜索树(或更高级的数据结构)来获得至少O(logn)的平均情况,如果常数因子更好的话.
你有什么建议吗？只是为了让你知道我正在开发OCaml,但我认为这些考虑可以被认为是语言无关的
浮点数的常见问题是计算是近似的.如果您以两种不同的方式计算相同的值,结果可能会略有不同.(在某些情况下,通过以相同的方式计算相同的值,您可以获得轻微的差异.)
因此,如果您正在对浮点数进行任何计算,您将得到近似值,而不应该依赖于相等性.如果您的来源以各种方式计算浮点数,则传递给您的数据将是近似值.如果您获得精确的浮点值,并且可以指望任何应该相同的数字是完全相同的位表示,那么相等性正常工作,您可以使用哈希表.
我想这里有几个问题
是.我现在想不到一种语言,floats它不符合哈希表中密钥所需的要求(通常是稳定的哈希代码和相等的语义)
取决于多少.如果键的数量如此之大,则会导致表超出允许的内存大小,然后肯定没有,因为它会导致内存不足的情况.没有更多的背景,回答这部分问题真的是不可能的.可能你是唯一一个能够回答它的人.
float比其他类型更差int？这是特定于实现的,但我相信OCaml a float具有双精度(8字节).因此,询问精度是否使其无效作为键是等同于询问C#long类型不适合作为哈希表键.它们都具有相同数量的可能值(它们都是8个字节).我当然会说long是一种有效的密钥类型(经常使用它并且没有任何问题).
我认为真正的问题是你是否不负责任地创建了float用作密钥的实例.
可能但不是很多.二叉树和哈希表都涉及开销.对于哈希表,它通常是未使用的桶和桶内列表中的下一个指针.对于二叉树,树中的每个元素都有2个额外的开销(左右指针).如果你的内存不足,我不确定是否会更好地转向二叉树.