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
$\begingroup$
$\endgroup$
9
-
$\begingroup$ Use a hash function. Interpret the result as the binary expansion of a number in $[0,1)$. $\endgroup$– Yuval FilmusMay 27 '19 at 11:21
-
$\begingroup$ Are there hash functions for continuous domains? $\endgroup$– SomeoneHAHAMay 27 '19 at 13:03
-
$\begingroup$ In your case it’s the range which is continuous. $\endgroup$– Yuval FilmusMay 27 '19 at 13:09
-
$\begingroup$ I am also interested in a continuous domain: $h : U \rightarrow [0,1]$ where $U$ is a continuous set $\endgroup$– SomeoneHAHAMay 27 '19 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 FilmusMay 27 '19 at 13:17
|
Show 4 more comments