0
$\begingroup$

Two questions about the construction of a hash function:
Let $U = \{u_1,...,u_n\}$ be a set of size $n$, and suppose that one is interested in a function $h\colon U \rightarrow [0,1]$ such that $h$ "looks like" it maps each of the $u_i$s to a random number, chosen from the uniform distribution on $[0,1]$. One simple way to construct such $h$ is to store in the memory a table of size $n$, and saving, for each element $ u_i$, the corresponding random sample. This is obviously very inefficient, and impossible to do if $U$ is infinite (or even continuous). Are there known approaches (or lower bounds) for the discrete, finite case? Are there approaches for the continuous case (i.e. $U$ is a continuous set)?
Clarification for the continues domain case:
Suppose that $U = \mathbb{R}$. What I am after is a function $h : U \rightarrow [0,1]$ such that $h(u)$ has the property of "being random" i.e. if you sample many points from $\mathbb{R}$, and look at $h(x_1),...,h(x_m)$ they would look like numbers which were sampled from uniform distribution

$\endgroup$
  • $\begingroup$ Use a hash function. Interpret the result as the binary expansion of a number in $[0,1)$. $\endgroup$ – Yuval Filmus May 27 at 11:21
  • $\begingroup$ Are there hash functions for continuous domains? $\endgroup$ – SomeoneHAHA May 27 at 13:03
  • $\begingroup$ In your case it’s the range which is continuous. $\endgroup$ – Yuval Filmus May 27 at 13:09
  • $\begingroup$ I am also interested in a continuous domain: $h : U \rightarrow [0,1]$ where $U$ is a continuous set $\endgroup$ – SomeoneHAHA May 27 at 13:16
  • $\begingroup$ This sounds like a different question... the model isn’t completely clear, anyhow. How is the input accessed? What are the required properties? $\endgroup$ – Yuval Filmus May 27 at 13:17

Your Answer

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

Browse other questions tagged or ask your own question.