Ada:整数溢出

Question

因此，我正在散列并定义了这些类型/函数：

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

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

Answer 1

类型Long_Integer是一个带符号整数类型，并保证覆盖范围–2**31+1 .. +2**31–1 (如果存在的话)：

LRM 3.5.4(22)：

如果为实现预先定义了Long_Integer，则其范围应包括范围–2**31+1 .. +2**31–1。

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

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

Answer 2

您可以使用所示的Hash方法比较各种这里函数的质量，这种方法在字典单词的哈希表中记录冲突。生成的Counts存储在Ada.Containers.Ordered_Maps的一个实例中。

作为一个具体例子，库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;

在最坏的情况下，产生一个结果，只有不到一半的单词具有唯一的散列，而在最坏的情况下，两个不同的哈希值分别产生二十次碰撞：

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%)