We’re rewarding the question askers & reputations are being recalculated! Read more.
63

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,...\}$ ...


41

There are two settings under which you can get $O(1)$ worst-case times. If your setup is static, then FKS hashing will get you worst-case $O(1)$ guarantees. But as you indicated, your setting isn't static. If you use Cuckoo hashing, then queries and deletes are $O(1)$ worst-case, but insertion is only $O(1)$ expected. Cuckoo hashing works quite well if you ...


26

A whole treatise could be written on this topic; I'm just going to cover some salient points, and I'll keep the discussion of other data structures to a minimum (there are many variants indeed). Throughout this answer, $n$ is the number of keys in the dictionary. The short answer is that hash tables are faster in most cases, but can be very bad at their ...


24

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.


21

This answer summarises parts of TAoCP Vol 3, Ch 6.4. Assume we have a set of values $V$, $n$ of which we want to store in an array $A$ of size $m$. We employ a hash function $h : V \to [0..M)$; typically, $M \ll |V|$. We call $\alpha = \frac{n}{m}$ the load factor of $A$. Here, we will assume the natural $m=M$; in practical scenarios, we have $m \ll M$, ...


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 ...


14

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 ...


11

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

A perfect hash function can be defined as an injective function from a set $S$ to a subset of the integers $\{0, 1, 2, ..., n\}$. If a perfect hash function exists for your data and storage needs, you can easily get $O(1)$ behavior. For instance, you can get $O(1)$ performance from a hash table for the following task: given an array $l$ of integers and a set ...


9

A perfect hash function will result in $\cal{O}(1)$ worst case lookup. Moreover, if the maximum number of collisions possible is $\cal{O}(1)$, then hash table lookup can be said to be $\cal{O}(1)$ in the worst case. If the expected number of collisions is $\cal{O}(1)$, then the hash table lookup can be said to be $\cal{O}(1)$ in the average case.


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! ...


9

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 ...


8

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^...


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

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 ...


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

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


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

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

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 ...


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