0、..、nは一様に画像

Question

Iが32または64ビットのいずれかで符号なし整数を取り、上にマッピングする（ハッシュ）関数を検索しようとしている上に、符号なし整数、マッピング配列について全単射関数を探しもう一度同じタイプ。

それは全単射と高速である必要があります。

追加プロパティ：任意について

N Nにint値0のシーケンスが画像上に「均一に」マッピングされるべきです。私はKに等しく大きなサブセットに画像を分割する場合 意味は、それらがK < < nに対して、ほぼ等しくなければなりません。

Answer 1

これはあなたの要件をすべて満たしている：

unsigned int identity(unsigned int x) { 
    return x; 
} 

Answer 2

私は32または64ビットの符号なし整数を取り、同じ型にそれをマップする（ハッシュ）関数を見つけようとしています再び。

それは全単射と高速である必要があります。

私は0の衝突を満たす関数は、恒等関数です。

uint64_t hash(uint64_t inp) { 
    return inp; 
} 

あなたの追加の特性：任意について

N Nにint値0のシーケンスが画像上に "均一に" マッピングされるべきです。

hmです。したがって、最初のn個の数値は当然コンパクトであるため、同一性はそれを行いません。しかし：

ビット反転は、トリックを行います！

代わりに同じ番号を返すので、ちょうどそれらのビット反転バージョンを返します。

ビット反転はです。通常、は、高速操作ではありません。ただし、その手伝いに役立つトリックやCPU命令がある場合を除きます。

編集：ああ、私はKnuthがあなたの平均的なハッシュimplよりもはるかに速くすべき機能を提案したことを覚えています。 multを仮定

Answer 3

は奇数である（それは、任意の現代のプロセッサであろうようにTの範囲は、2の累乗である）、

template <T> 
auto linear_congruential_hash(T mult, T incr) { 
    static_assert(std::is_integral<T>::value, 
        "template argument must be an integral type"); 
    return [mult, incr](T n) -> T { 
     return mult * n + incr; 
    } 
} 

によって返される任意の関数は全単射です。 multが上限のTに近い場合、機能は均一性の要件を満たすことにも近くなります（multの一部の小さな倍数が0に近すぎないようにしてください。たとえば0x7fffffffUが悪いです）。ですから、具体的な例を挙げると、linear_congruential_hash<uint32_t>(0x68832099U, 0x30571005U)のようなものがうまくいけばうまくいくはずです。