阿達：整數溢出

，所以我散列和定義這些類型/功能：阿達：整數溢出

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這兩個長整數的總和時會出現問題，因爲它溢出。我需要以某種方式將字符串視爲POSITIVE整數值，並且沒有我的函數溢出。謝謝！！！

來源

2017-04-16 Numnumberry

一般一個使得散列表的大小的質數，以確保更均勻的分佈。 – user3344003

我假設的作業，因爲你被困在次優散列函數。 –

類型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中的LRM。

來源

2017-04-16 07:03:34

我解決了我的問題，我創建了一個模塊化的類型，允許我保存更大的數字 – Numnumberry

但是，是否給你正確的答案？ –

它是，即時獲得我所需的哈希值，我的模塊化類型允許我有2^64正整數，所以不會更多溢出 – Numnumberry

您可以使用顯示here的方法比較各種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;

產生具有獨特的散列爲不到一半的話，並且每個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%)

來源

2017-04-20 10:42:26 trashgod

阿達：整數溢出

回答

相關問題