Ada：整数溢出

Question

所以我正在散列并定义了这些 types/functions:

subtype string2 is String(1..2);  
function cString2 is new Ada.Unchecked_Conversion(string2, long_integer);
function cChar is new Ada.Unchecked_Conversion(character, long_integer);

并且必须使用这个散列函数：

HA = (((cString2(s1) + cString2(s2)) * 256) + cChar(char)) mod 128

（该函数是故意的，但我必须实现它）问题出现在添加 and/or 试图将 256 乘以两个长整数之和时，因为它溢出了。我需要以某种方式将字符串视为正整数值，并且我的函数也不会溢出。谢谢！！！

Answer 1

类型Long_Integer是有符号整数类型，保证覆盖范围–2**31+1 .. +2**31–1（如果存在）：

LRM 3.5.4(22):

If Long_Integer is predefined for an implementation, then its range shall include the range –2**31+1 .. +2**31–1.

对于您的声明，您可能在转换后的值中包含至少 2 个字节的随机垃圾，但由于大小不匹配，结果是实现定义的，可能无效或异常。

我建议您阅读 'Pos 属性和 LRM 中的 Ada.Unchecked_Conversion。

Answer 2

您可以使用显示的方法 here, which tallies collisions in a hash table of dictionary words. The resulting Counts are stored in an instance of Ada.Containers.Ordered_Maps.

比较各种 Hash 函数的质量

作为具体示例，库 Hash 函数

function Hash is new Ada.Strings.Bounded.Hash(ASB);

产生的结果具有超过一半的单词的唯一哈希值，在最坏的情况下只有七次冲突：

Word count: 235886
Table size: 393241
Load factor: 59.99%
 0: 215725 (0.00%)
 1: 129710 (54.99%)
 2: 38727 (32.84%)
 3: 7768 (9.88%)
 4: 1153 (1.96%)
 5: 143 (0.30%)
 6: 14 (0.04%)
 7: 1 (0.00%)

相比之下，这个Hash函数

function Hash(Key : ASB.Bounded_String) return Ada.Containers.Hash_Type is
  S : String := ASB.To_String(Key);
  H : Ada.Containers.Hash_Type := 0;
begin
  for C of S loop
     H := H * 3 + Character'Pos(C);
  end loop;
  return H;
end;

在最坏的情况下，对于少于一半的单词产生具有唯一哈希的结果，并且对于两个不同的哈希值每个都有 20 次冲突：

Word count: 235886
Table size: 393241
Load factor: 59.99%
 0: 236804 (0.00%)
 1: 107721 (45.67%)
 2: 32247 (27.34%)
 3: 9763 (12.42%)
 4: 3427 (5.81%)
 5: 1431 (3.03%)
 6: 813 (2.07%)
 7: 441 (1.31%)
 8: 250 (0.85%)
 9: 150 (0.57%)
 10: 88 (0.37%)
 11: 41 (0.19%)
 12: 27 (0.14%)
 13: 14 (0.08%)
 14: 11 (0.07%)
 15: 7 (0.04%)
 16: 2 (0.01%)
 17: 1 (0.01%)
 19: 1 (0.01%)
 20: 2 (0.02%)

Ada：整数溢出

Ada: Integer Overflow

ada

overflow

long-integer