Can you provide a hash functions $F(x) | F(x) = F(\overline{x}), x \in {\{0;1\}}^n$

$\overline{x} $ is $x$ where all bits are swapped: $0 \rightarrow 1, 1 \rightarrow 0$

Basically it will help me improve my MAX-CUT algorithm


If $F(x)$ is a non-symmetric hash, you can always make it symmetric by defining $F'(x) = F(x) + F(\tilde x)$ where $+$ can be any symmetric operation (bitwise xor, for example).


The following hash function is symmetric. Note that the bit shifting is arbitrary and really you don't have to do it. The point is that you make sure the terms you use to create the hash are symmetric (in this case addition and multiplication) and that you use the key and its bit-flipped version to compute the hash index.

In C/C++:

// symmetric hash function
unsigned char sym_hashfunc( unsigned char key ){
    unsigned int flip = ~key;
    unsigned int left = (key + flip);
    unsigned int right = (key * flip);
    return (left>>3) ^ (right>>1);

int main(int argc, const char * argv[]) {

    // some random input key
    unsigned int key = 12;
    unsigned int flipkey = ~key; // find bit flipped version

    // print results. Should show same hash value
    printf("Hash1 = %u, Hash2 = %u\n",sym_hashfunc(key),

    // exit
    return 0;

I am not aware of an established symmetric hash function but it is easy to add this property to an existing function hash.

Our my_hash arbitrarily decides that all data with a positive first bit is $x$ and with a negative first bit is $\overline{x}$. If the input data is $x$ we return hash(i) otherwise bit_inverse(hash(i)). See pseudo code below.

def my_hash(data)
    # arbitrary way to identify if data is already inverted
    if first bit of data is set
        return hash(data)
        return bit_inverse(hash(data))

Before using this, make sure the negative effect on collisions and hash value distribution is not relevant to your problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.