編譯字符類型的時間一致性散列

我想以類似於Symbol的方式實現ruby。編譯字符類型的時間一致性散列

爲此，我創建了一個用戶定義的文字，返回std::basic_string<T>對應的std::hash。

代碼非常好，但是當我讀somewhere時，哈希函數在同一程序的多次執行中可能不一致。此外，我想在編譯時進行這種計算，這是1）std::hash不支持，2）如果std::hash返回值發生更改，將會破壞代碼。

所以我寫下了基於java.lang.String.hashCode實現的以下實現。

typedef size_t symbol; 

template<typename CharT> 
constexpr size_t constant_hash(const CharT* p, size_t h = 0) noexcept 
{ 
    return (*p == 0) ? h : constant_hash(p + 1, h * 31 + static_cast<size_t>(*p)); 
} 

constexpr symbol operator "" _sym (const char* p, size_t n) noexcept 
{ 
    return constant_hash(p); 
}

我的問題是：是否有任何問題與此實現？

我只能在GCC 4.7.1上測試它，並且我想知道它是否符合標準，並且也應該在其他編譯器上工作。

我在問這是因爲以前的實現在GCC上工作，但如果二進制編譯爲clang ++（我認爲增量運算符的未定義行爲的問題），導致段錯誤。

在此先感謝

編輯

鏗鏘工作++（感謝KennyTM）

來源

2012-06-22 Geoffroy

我試過clang ++，但它不會崩潰。 – kennytm

謝謝:)我編輯帖子 – Geoffroy

有沒有UB，它工作正常，只要字符串有'\0'終止。請注意，constexpr評估無法調用UB;在運行時導致UB的算術或指針操作需要在常量表達式的上下文中產生編譯錯誤。

請注意，static_cast是不必要的; char操作數將被提升爲size_t。

此外，乍一看散列函數看起來不太好，因爲h * 31只是(h << 5) - h。你可以在整個二進制值中隨機選擇一個更大的數字。但另一方面，由於ASCII的低5位具有最大的熵，所以它們可能試圖變得聰明，這消除了不同長度的短串之間發生碰撞的可能性。

來源

2012-06-22 08:53:00 Potatoswatter

感謝有關UB的精度。如果將constant_hash函數與另一個類型（如wchar_t）一起使用，或者甚至可以將其轉換爲size_t的任何其他類型，並且只要該數組以零終止，那麼static_cast可能仍然有用。關於哈希函數，你認爲我應該用（h << 5） - 1代替h * 31？ – Geoffroy

@Geoffroy：Potatoswatter意味着你可以選擇一個更好的散列函數，而不是用'（h << 5）-h'來代替'h * 31'。由於向後兼容，Java需要使用'h * 31'，所以不需要。 – kennytm

好的，謝謝你的精確度，我不明白他的意思。你知道任何滿足相同條件的散列實現嗎？ – Geoffroy

注意：n3333是C++ 17的建議。儘管我不相信C++ 11需要在多次運行時產生相同的結果，但實際上我相信所有當前的實現都是如此。

來源

2012-06-22 14:27:33 Nevin

所有的實現可能暫時做它，但C++ 1y可能會指定散列函數從一個執行到另一個執行，只是爲了防止危險的習慣。或者只是指定它不能改變。我們會看到:) – Geoffroy

在當前活躍的C++標準中，散列函數的定義通常是以這種方式編寫的，以便爲特定於域的實現提供更多可能性，而不是要求以特定方式執行散列。例如，它允許執行池化字符串並將池實例的內存位置用作散列值的可能性（順便說一句，這是ruby如何進行其字符串和哈希運算，這導致了一些interesting issues）。如果你正在計算你的哈希值而不是參考值，那麼這個值就會保持穩定 - 除非你發現了常量表達式不存在的某種數學形式。

基本上，在這種情況下，「可能不」是授予許可讓事情以特定方式行事，而不是說明可能發生的事情。

這就是說，如果你正在使用std::hash，你不能保證該值將永遠是執行之間相同的（並且在未來，如果n3333被採納，這依賴於任何代碼將打破），所以如果需要穩定散列，最好定義自己的穩定散列函數。

來源

2012-06-22 16:13:43 fluffy

感謝您的精確:) – Geoffroy

編譯字符類型的時間一致性散列

回答

相關問題