エイダ：整数オーバーフロー

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 

（関数は、目的に悪いですが、私それを実装する必要があります）問題は、オーバーフローのために、2つのlong整数の合計で256を加算したり、または乗算しようとするときに発生します。私は何とかPOSITIVE整数値として文字列を扱う必要がありますまた、私の関数のオーバーフローがありません。感謝!!!

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属性とAda.Unchecked_Conversion属性をお読みください。

Answer 2

さまざまなHash関数の品質を、hereという方法を使用して比較することができます。これは、辞書単語のハッシュテーブルの衝突を示します。結果としてCountsはAda.Containers.Ordered_Mapsのインスタンスに格納されます。これとは対照的に

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 is new Ada.Strings.Bounded.Hash(ASB); 

がユニークワードの半分以上のためのハッシュと最悪の場合にはわずか7衝突を持つ結果を生成

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