6
$\begingroup$

Reading available literature (yep, including wikipedia), I see that hash functions should have (continuity) and map values that differ very little to similar/same hash codes, in particular for (hash tables that use linear search) ... if that makes any sense. Supposedly, this would help linear search benefits from locality of reference.

OTH, a hash function should be uniform, in the sense that hash values are uniformly distributed. Unless I'm misunderstanding something, it looks to me as if these two properties are in conflict.

Let's say we have a sequence $S$ of input values $(s_1, ..., s_n)$ such that the delta between any two value pairs is small and similar across the set.

That is

$$\forall s_i, s_j \in S\,\,|\,\varepsilon_{min} < \delta(s_i, s_j) < \varepsilon_{max}$$

and with the differences between any two values ($\delta(s_i,s_j)$) being uniformly distributed. In such a case the values in the sequence have a uniform distribution.

Let's suppose we aim to store these values in a hash table with open addressing (linear probing) and a hash function $h$. Obviously, we assume that the hash table is large enough to accommodate all input values (and to be below an initial load factor.)

If the hash function $h$ exhibits continuity, then it will map all the values in $S$ very close to one another (if not, to the same hash code) ergo increasing collisions. That is, it would exhibit clustering.

Wouldn't that then, deteriorate the search performance (via liner probing) as a result of the resulting collisions. If continuity is desirable when using linear probing, then how does one cope with the collisions when a large part of the values are close to one another?

--- EDIT ---

Sorry, I left some things out. $\delta(s_i,s_j)$ represents the number of symbols by which the strings $s_i$ and $s_j$ differ (or the number of changes that need to occur to convert $s_i$ into $s_j$.)

For a better example, let $\Sigma = {\sigma_1, \sigma_2, ... , \sigma_n}$ be an alphabet, and $L(i, n)$ be a language over $\Sigma$ such that

$$ L(i,n)\,\triangleq \{s| (s=\sigma_i^*\sigma_k\sigma_i)\wedge (|s| = n) \wedge (\{\sigma_i,\sigma_k\} \subset \Sigma)\} $$

So, if we were to consider input strings, all of length $n$ such as $$aaa..., baaa..., abaa..., ....aaab, caaa..., acaa$$

that only differ on one character, the value and position of which is uniformly distributed among the input strings, then a hash function $h$ that possess continuity will cluster them all on top or near the same hash value.

-- ADDITIONAL EDIT --

The only place I've read so far that mentions continuity as a desirable property has been in the Wikipedia article for hash functions. I've consulted all the other books I have on Algorithms (CLRS, Sedgewick's, Berman and Paul's and others), and I've not found any such assertion on hash functions.

So it seems to me that continuity is not a desirable trait despite what the Wiki entry says. Or am I missing something????

$\endgroup$
  • 2
    $\begingroup$ what is $\delta$? $\endgroup$ – Sasho Nikolov Aug 4 '12 at 5:59
  • 2
    $\begingroup$ I fail to see why the hash function used in hash tables with linear probing should exhibit continuity at all. Continuity is required if you want to find a value in a hash table that is similar to a given value efficiently, but this is unrelated to linear probing. $\endgroup$ – Tsuyoshi Ito Aug 4 '12 at 12:42
  • $\begingroup$ @SashoNikolov - thanks for asking that. I forgot to mention what $\delta$ was for (in this context, it's the number of characters by which the two strings differ.) I've updated my question to reflect that. $\endgroup$ – luis.espinal Aug 4 '12 at 17:54
  • 1
    $\begingroup$ (1) Hmm, I agree that that sentence in the Wikipedia article still does not make sense. (2) The choice of hash function depends on the application, and in your application, you want to balance between uniformity and continuity. I do not know a good hash function on strings in that sense, but maybe someone who has experiences in this field knows much better. $\endgroup$ – Tsuyoshi Ito Aug 4 '12 at 21:20
  • 4
    $\begingroup$ @luis.espinal: Continuity is something hash functions strive AGAINST in the general case and instead try to separate similar data (to prevent consecutive ids to be hashed in a clump, for instance). Only some very specific applications (which most people have never heard of) instead find use in having hash functions which map similar data to similar hash values. $\endgroup$ – Jérémie Aug 4 '12 at 21:24
2
$\begingroup$

While continuity in a strong sense is probably too much to ask for, locality sensitive hashing (LSH) achieves a very similar goal: given a set of items $x_1, \ldots, x_n$ which belong to some metric space with metric $d$, an LSH family of hash functions (parametrized by $D, c, p, q$) maps $x_i$ and $x_j$ into the same bucket with probability $\geq p$ if $d(x_i, x_j) \leq D$ and maps $x_i$ and $x_j$ into different buckets with probablity $\geq q$ if $d(x_i, x_j) > cD$. Of course there is tension in the requirements, so one looks for tradeoffs. Look at the wiki page and Alex Andoni's webpage, especially the CACM survey.

For context, LSH is a tool to solve the approximate nearest neighbor problem in high dimensional metric spaces. There exist solutions for various metrics, like hamming distance and $\ell_p$ norms, see the CACM survey. The approximate nearest neighbor problem is an important problem in computational geometry, and the high-dimensional version comes up in a variety of applications, for example in computer vision and information retrieval.

The way LSH is used to solve approximate near neighbor search is a fairly natural two-level hashing scheme. As you note, there is tension between the "continuity" property and bounding the number of collisions. For that reason, usually the gap between $p$ and $q$ (as I defined them above) is pretty small. To overcome this we construct a new hash function by choosing several functions from an LSH family and taking their concatenation. The resulting universe is too big, so it is reduced using traditional hashing. Then we build several hash tables using these hash functions. A query is answered by hashing the query point and inspecting the other points in the same bucket(s) to determine if they are close enough (this is the linear search part). Parameters can be chosen so that a query is answered in sublinear time.

$\endgroup$
  • $\begingroup$ As far as I know, LSH is a recent application most people have never heard of. Furthermore, LSH is not a type of hashing function, but rather an algorithm that computes indices using standard uniform hash functions. It is an outgrowth of Broder's original MinHash, itself the spiritual successor of Flajolet and Martin's observation that cardinality estimation schemes based on projection are very good at estimating unions of stream (see "Applications to Distributed Computing" p.204). $\endgroup$ – Jérémie Aug 5 '12 at 17:27
  • $\begingroup$ @Jérémie Of course LSH is a type of hash function. By definition a family of hash functions is locality sensitive if collision probability is bounded from above and below as described in my answer (see CACM survey section 2.3). If this is not a type of hash function, then pairwise independence isn't either! You are talking about a particular construction of an LSH family, and not all constructions fit your description, for example the constructions based on $p$-stable distributions from Datar et al., SCG 2004 $\endgroup$ – Sasho Nikolov Aug 5 '12 at 18:39
  • $\begingroup$ I find your claims that LSH is obscure puzzling too, but that's not a constructive discussion. In any case, notice that the application is near-neighbor search in high dimension, and that's what I am saying is far from unheard of (it's one of the most prominent problems in computational geometry). But, since this comment upsets you, and I admit I was too curt, I will edit that part of my answer. I'd appreciate it if you explain the downvote, or at least what you understand by type of hashing function. $\endgroup$ – Sasho Nikolov Aug 5 '12 at 18:46
  • $\begingroup$ I think that in the vast context of hash functions and their applications, LSH is a fascinating but relatively minor topic. For the main part of their history, and for the bulk of the problems that they solve, we ask that hash function separate data -- in other words I believe that "continuity" is by far the exception not the rule. In particular, luis.espinal seems to be focused on the application of hash functions to hash tables, and I feel like this is not something you have factored in when responding (although everything you say is perfectly true). $\endgroup$ – Jérémie Aug 5 '12 at 19:56
  • $\begingroup$ Another way of seeing it is: you are answering "Is continuity possible?" when the question was "Why the heck would we want continuity in hash functions for hash tables?" But perhaps I am wrong? :-/ $\endgroup$ – Jérémie Aug 5 '12 at 19:59

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.