0
$\begingroup$

What would be a good hash function that will return a positive integer value, even if the key is an negative integer value? How do I pick a hash function? So what I would want is to associate negative numbers with some positive value so I can use them later.

UPDATE: (summary) I need to find a bijection $f: \mathbb{Z}\to\mathbb{N}$ which also has the property that: $$ f(x) + f(y) = f(x + y) $$

Improve this question
$\endgroup$
  • $\begingroup$ What is the purpose of your hash function? $\endgroup$ – reinierpost Nov 12 '19 at 9:43
  • $\begingroup$ @reinierpost the purpose is to map negative numbers to some positive value and also not collide with other positive numbers from an array. so basically, I have an array with some integer values, and i want to map every integer value from that array to some other positive value so then i could use an algorithm that only works for positive values. $\endgroup$ – C. Cristi Nov 12 '19 at 9:45
  • $\begingroup$ In that case, any simple bijection from $\mathbb{Z}$ to $\mathbb{N}$ will do, right? It doesn't need to "hash" (mix up the ordering). $\endgroup$ – reinierpost Nov 12 '19 at 9:49
  • $\begingroup$ @reinierpost sure, but i cant think of any bijection like that $\endgroup$ – C. Cristi Nov 12 '19 at 9:51
  • $\begingroup$ @reinerpost nevermind, i think i found one! thanks! $\endgroup$ – C. Cristi Nov 12 '19 at 9:53
2
$\begingroup$

From your comments, it appears all you need a bijection from $\mathbb{Z}$ to $\mathbb{N}$ that is easy to compute.

The simplest one I can think of: $x \mapsto 1/2 + 2 \mid\!(x - 1/4)\mid$.

This isn't really a hash function: it doesn't "hash" (scatter its consecutive function values across their range).

Improve this answer
$\endgroup$
  • $\begingroup$ Hello, I also need that the function to be like f(x) + f(y) = f(x + y) $\endgroup$ – C. Cristi Nov 12 '19 at 11:08
  • $\begingroup$ Can you see the edit? $\endgroup$ – C. Cristi Nov 12 '19 at 12:16
  • 2
    $\begingroup$ Yes. With that additional requirement, no such function exists: for infinitely many different $x$, you now require that $f(x)$ is positive, $f(-x)$ is positive, and $f(x) + f(-x) = f(0)$; no value for $f(0)$ can meet that requirement.. Are you sure you really need it? Or perhaps your function doesn't need to be injective? $\endgroup$ – reinierpost Nov 12 '19 at 12:27
  • $\begingroup$ @reinerpost The problem goes like this: given an array with N integer elements find the longest subsequence which sum gives K. and i thought of a linear time solution but only works for positive elements, so that's why i'm searching for something like this $\endgroup$ – C. Cristi Nov 12 '19 at 12:29
  • 1
    $\begingroup$ That's a different question ... $\endgroup$ – reinierpost Nov 12 '19 at 12:38
1
$\begingroup$

Hint: map the positive numbers to the odd numbers and the negative numbers to the even numbers.

Improve this answer
$\endgroup$

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.