是否存在雜湊等於自身的字元串？
我想知道是否有任何字元串的雜湊值等於它自己，所以——當使用任何（非特定）雜湊函式時——雜湊值等於那個字元串？
以便：
hash(x) = x請注意，這不是任務或任何東西。我只是好奇，找不到任何具體的答案或參考。而且我不確定如何去向自己證明/反駁這一點！
我僅限於雜湊函式 $ H $ 具有一些固定大小的輸出 $ n\ge1 $ 位，接受一些字元串作為輸入，包括所有 $ n $ -位字元串；MD5 (resp. SHA-1, SHA-256) 是這種函式的一個例子 $ n=128 $ （分別。 $ n=160 $ , $ n=256 $ ).
是否存在解決方案 $ H(x)=x $ 取決於特定的雜湊函式。如果 $ H $ 是一個隨機函式（如 MD5、SHA-1 和 SHA-256 的目標），答案是肯定的，賠率旁邊 $ 63.2% $ 對於實際值 $ n $ .
更確切地說： $ H(x)=x $ 只有當 $ x $ 正好有 $ n $ 位。有 $ 2^n $ 的值 $ x $ 滿足後一個條件，並限制 $ H $ 對這樣的 $ x $ 有 $ (2^n)^{(2^n)} $ 不同的 $ H $ 函式，其中 $ (2^n-1)^{(2^n)} $ 這樣 $ H(x)=x $ 沒有解決辦法。因此，如果我們選擇一個 $ H $ 均勻隨機，機率正好 $ 1-{(2^n-1)^{(2^n)}\over(2^n)^{(2^n)}}=1-(1-2^{-n})^{(2^n)} $ 我們挑選的 $ H $ 這樣 $ H(x)=x $ 有解決辦法。作為 $ n $ 增加，這會很快收斂到 $ 1-1/e\approx0.632 $ （在哪裡 $ e\approx2.718 $ 是自然對數的底）。
這並不能說明 MD5 是否具有存在解決方案的屬性 $ \operatorname{MD5}(x)=x $ （這將是一個 128 位的位串 $ x $ ）。我們能說的最好的就是它可能成立，機率約為 63%，但確定斷言是真還是假超出了我們目前的計算能力（我們擁有的最好方法是窮舉搜尋，如果答案是否定的需要 $ 2^{128} $ 雜湊；否則它仍然可能需要超過 $ 2^{126} $ 雜湊，這是遙不可及的）。
PHP 特定：如果
md5($string) === $string有一些解決方案，那將是 32 個十六進制小寫字元的字元串；我們的雜湊值不一樣 $ 2^{128} $ 候選人如上所述，所以問題不等價，但可以調整推理，我們可以說的最好的情況是，很可能有一個解決方案，機率約為 63%。此外，原始問題詢問是否存在這樣的字元串
md5($string) == $string。要回答這個問題，我們必須考慮運算符在 PHP 中是如何==工作的，因為類型雜耍（它持有"0042" == "42", 和"20e2" == " +002000"）。極有可能有一個解決方案（只要考慮一下 $ 2^{200} $ 由 200 個空格或製表符和一個額外的 final組成的字元串0，我們預計大約 $ 31\cdot2^{72} $ 散列到"00000000000000000000000000000000","000000000000000000000000000000e0".."0e000000000000000000000000000000") 之一；但是我們不能展示一個。定義散列函式很容易 $ H $ 這樣 $ H(x)=x $ 沒有解決方案：例如，定義 $$ H(x)=\begin{cases}x\oplus1&\text{if }\operatorname{MD5}(x)=x\\operatorname{MD5}(x)&\text{otherwise}\end{cases} $$
定義散列函式也很容易 $ H $ 這樣 $ H(x)=x $ 至少有一個解決方案：例如，選擇一些任意的 128 位常量，例如 $ k=\text{af5d2bc6c9181f76f3161f43f41f6aeb} $ , 並定義 $$ H(x)=\begin{cases}k&\text{if }x=k\\operatorname{MD5}(x)&\text{otherwise}\end{cases} $$
不可能有 $ x $ 這樣對於所有可能的雜湊函式 $ H $ , $ H(x)=x $ .
對立證明：假設存在這樣的 $ x $ , 一個函式 $ H $ 和 $ x $ 具有該屬性，並考慮功能 $ \tilde H $ 被定義為 $ \tilde H(x)=H(x)\oplus1 $ .