# Symmetric hash function

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),
sym_hashfunc(flipkey));

// 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)
else
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.