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????
Continuity vs Uniformity when designing Hash functions
ds.data structures;hash function
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.