80

Consider the set of keys $K=\{0,1,...,100\}$ and a hash table where the number of buckets is $m=12$. Since $3$ is a factor of $12$, the keys that are multiples of $3$ will be hashed to buckets that are multiples of $3$: Keys $\{0,12,24,36,...\}$ will be hashed to bucket $0$. Keys $\{3,15,27,39,...\}$ will be hashed to bucket $3$. Keys $\{6,18,30,42,...\}$ ...


25

The hash function doesn't return some string such as mkwer. It directly returns the position of the item in the array. If, for example, your hash table has ten entries, the hash function will return an integer in the range 0–9.


16

Whether a collision is less likely using primes depends on the distribution of your keys. If many of your keys have the form $a+k\cdot b$ and your hash function is $H(n)=n \bmod m$, then these keys go to a small subset of the buckets iff $b$ divides $n$. So you should minimize the number of such $b$, which can be achieved by choosing a prime. If on the ...


15

Pathological data is supposed to be data that makes things go wrong in some way for your intended computation. It can be called pathological when it is rare enough in actual uses, so that things work OK most of the time. This can sometimes be made mathematically more precise (for example with probabilities), but the use of the word pathological in often ...


15

The entries of a hash table are stored in an array. However, you have misunderstood the application of the modulo operator to the hash values. If the hash table is stored in an array of size $n$, then the hash function is computed modulo $n$, regardless of how many items are currently stored in the table. So, in your example, if you were storing ...


13

The most obvious answer is that trees can be traversed in their natural order very efficiently. If you need to visit every element of a dictionary in alphabetical order, a tree can support this directly, where a hash table cannot. Another answer is that trees can be made immutable - where insertion and deletion only involve recreating a small number of ...


12

Refresh your knowledge of binary! The $p$ lowest-order bits of $k$ are the last $p$ bits when $k$ is written out in binary (i.e., the $p$ rightmost bits). For example, if $p=3$ and $k=17$ then $k$ is $10001$ in binary and the three lowest-order bits are $001$. The point is that, in general, computing $k \bmod m$ is a relatively ...


11

Pathological data is data that will make the algorithm perform bad. For hash tables, pathological data is data that causes collisions. That of course depends on the hash function being used. For example, if your hash function adds the characters together: hash("abcd") = 'a' + 'b' + 'c' + 'd'. Then pathological data looks like: {"abcd", "dcba", "cbda", ...}....


10

Binary search trees (BSTs) of various sorts and their variations are widely used data structures today, so they are hardly a "historical note". For example, both the .NET Framework and the Java Standard Library provide a tree-based implementation of a dictionary. A red-black tree no less in the latter case. One of the reasons for this is that tree-based ...


9

Whether this has an impact (also) depends on how you treat collisions. When using some variants of open hashing, using primes guarantees empty slots are found as long as the table is sufficiently empty. Try to show the following, for instance: Assume we want to insert an element that hashes to address $a$ and resolve collisions by trying positions $a + i^2$ ...


9

Simply compute the index of the permutation into the sorted list of all permutations and use that as your hash key. This can be achieved with a relatively simple algorithm: https://stackoverflow.com/questions/5131497/find-the-index-of-a-given-permutation-in-the-sorted-list-of-the-permutations-of Once you have that index, you can make a table with exactly 9! ...


8

The method you propose is, as far as I know, the historically first one for "perfect" hashing in linear space. In perfect hashing, lookup takes $O(1)$ time in the worst-case. (Recall that in most simple hash tables, lookup takes $O(1)$ time only in expectation.) The idea is to use chaining (rather than open addressing), but make each chain a hash table of ...


8

When you're asking about "exact" memory usage, do consider that all of those pointers may not be necessary. To see why, consider that the number of binary trees with $n$ nodes is $C_{2n}$, where: $$C_i = \frac{1}{i+1} { 2i \choose i }$$ are the Catalan numbers. Using Stirling's approximation, we find: $$\log C_{2n} = 2n - O(\log n)$$ So to represent a ...


8

An hash set is an hash table. Using an hash set to handle collisions in an hash table is equivalent to using a bigger hash table, with an hashing function which is a combination of the hashing functions of both level. In other words, you'd probably be better with a bigger initial table (for instance there is no risk of resonance between the two hash ...


8

Because we generally use the RAM model of computation with uniform cost model when computing the running time of operations on a hash table, and the RAM model with uniform cost states that the time to do a single operation on an entire machine word is $O(1)$. Also, we generally assume that the hash value fits within a single machine word. Thus, the running ...


7

Hash-table usually do waste space. Many algorithms do, since time-space trade-offs are common, but they usually hide it better :). Like other algorithms, hash-tables do it to get better time performance. The first point is that you try to avoid collisions in your hash-table, because that keeps the access time cost constant (but collisions are usually ...


7

SHA1 or SHA256, whichever you use, is for any practical purpose a random function. What you are observing is that random allocation is not as good as deterministic allocation. If you knew all the values in advance then you could indeed arrange that each cell would get exactly the same number of hits. Unfortunately, when you throw $n$ balls into $k$ bins, the ...


7

But then the lookup time is no longer constant Not worst-case constant -- which it never is for (basic) hashtables -- but it is still average-case constant, provided the usual assumptions on input distribution and hashing function. Why not use a hash set instead of a linked list? And how do you implement that one? You have created a circular definition. ...


7

The easiest way is to construct a static hash table $T$ containing all the collisions, in the following form: for each set of keys $S$ which are supposed to map to the same value, single out some $x \in S$, and put all other $y \in S$ in the table with an entry stating "$x$". Now take a good hash function $h$, and construct a new one as follows: On input $...


6

If you really just want to count the number of distinct words in the document, you don't need to save each instance of the word to the hash table. So, if you find a words that's already in the table, just don't add it there. This means you don't have to deal with chaining as often, which will speed things up. But you still have to deal with collisions, ...


6

Using a hash table with $n$ buckets and a hash function $h_n : S \rightarrow \{0, 1, ..., n - 1\}$ , where each bucket is a hash table with $m$ buckets and a hash function $h_m : S \rightarrow \{0, 1, ..., m - 1\}$, is equivalent to a hash table wit $nm$ buckets and a hash function $h_{nm} : S \rightarrow \{0, 1, 2, ..., nm - 1\}$ where $h_{nm}(x) = mh_n(x) +...


6

Yes, but in complexity theory, $≤O(1)$ only means $O(1)$ i.e. constant time.


6

Hash function calculates array position from given string. If this is perfect hash it means that there are for sure no collisions, the most probably array is at least twice bigger than number of elements. For example I will give very poor hash for letters, just to ilustrate mechanism: 0) $x = 0;$ 1) for each character in string take ascii value, subtract 'a'...


6

The load factor denotes the average expected length of a chain, therefore it is interesting for an average case analysis, not the worst case analysis. That's why on average you expect needing constant time for search operations. In the worst case however, all your elements hash to the same location and are part of one long chain of size n. Then, it depends ...


6

You are right now thinking of a data structure from which just three operations are expected, Insertion Lookup Deletion But if you extend these range of operations, to let's say finding number of elements greater than a certain value, one can see how BST's can be useful. A BST can still manage this operation in $\log n$ time but a hash table can't. ...


6

This is a nice question. In the comparison model or, what is more general, the algebraic decision-tree model, the problem of element distinctness has a lower bound of $\Theta(n\log n)$ time-complexity in the worst case as said in this Wikipedia article. So there is no algorithm to count distinct elements in linear time in the worst case, even without ...


5

The idea of a routing table in Pastry (and all structured P2P networks) is to minimize its size, while guaranteeing a quicker routing. The routing algorithm of Pastry goes as follows: Step A. A node u searches for an object A by firstly looking it up in its leaf set. Step B. If it was not available, then the query is forwarded to a known node that ...


5

The term can at least be traced back to a publication by Carriero, Gelernter and Leichter from 1986: Distributed Datastructures in Linda[Lin86]. The paper attributes the term to Rob Bjornson (which I believe to be this guy), but only cites personal communication as their mean of learning the term. [Lin86] also refers D. Gelernter: Dynamic global name spaces ...


5

Adding permutations isn't about preventing slow servers from becoming bottlenecks, rather it's about dispersing a convoy once one forms behind a slow server. Because of the way tract locations are hashed, sequential reads of any blob always walk the tract locator table in the same order. Suppose you have six tract servers and your tract locator table looks ...


5

I assume under "size of slot" you mean length of chain in hash table with separate chaining collision resolution. From Knuth, TAoCP, Vol. 3, 6.4, ex. 34 probability of k-length chain in hash table with $M$ slots and $N$ entries is $\binom{N}{k} \left ( M-1 \right )^{N-k} / M^N$ Assuming "ideal" hash function, however practical real-world hash functions ...


Only top voted, non community-wiki answers of a minimum length are eligible