126
votes
Accepted
Why is it best to use a prime number as a mod in a hashing function?
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 ...
- 3,674
27
votes
Accepted
Why are graphs represented as adjacency lists instead of adjacency sets?
In many algorithms we don't need to check whether two vertices are adjacent, like in search algorithms, DFS, BFS, Dijkstra's, and many other algorithms.
In the cases where we only need to enumerate ...
- 15.5k
24
votes
Accepted
Why is a (collision-less) hashtable lookup really O(1)?
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 ...
- 81.4k
18
votes
Accepted
Why is the Java HashMap load factor 0.75?
I don't know the answer, but I can walk you through what might be going through the mind of someone designing such a data structure.
Assuming a "good" hash function, and that $n$ is large ...
- 21.7k
16
votes
Why use binary search trees when hash tables exist?
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 ...
- 379
10
votes
Why use binary search trees when hash tables exist?
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 ...
8
votes
Hash table collisions: why use a linked list if we can use a hash set?
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 ...
- 3,024
8
votes
Accepted
Why are hash map look-ups assumed to be $O(1)$ on average
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 ...
D.W.♦
- 156k
7
votes
Hash table collisions: why use a linked list if we can use a hash set?
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 ...
- 72k
7
votes
Accepted
Hash-Table in Practice
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 ...
- 275k
7
votes
Accepted
Building static hash table with particular collisions
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 \...
- 275k
7
votes
Why is a (collision-less) hashtable lookup really O(1)?
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 ...
- 9,425
6
votes
Accepted
Understanding hashtable performance in the worst-case
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 ...
6
votes
Accepted
Hash functions and pathological data sets
An easy way to visualize this is to imagine a hash table of size $n$ (implemented with chaining) that contains all of the elements of $U$ (even though this is unrealistic in practice because $U$ ...
- 3,674
6
votes
Why use binary search trees when hash tables exist?
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 ...
- 161
6
votes
Accepted
How to count in linear time worst-case?
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-...
- 38.6k
6
votes
Why isn't an edge-map graph implementation used in practice?
Assume we are dealing with the representation of a weighted graph. I will use Python as the programming language to illustrate the points, which will remain true largely if another programming ...
- 38.6k
5
votes
Hash table collisions: why use a linked list if we can use a hash set?
You absolutely can do this. You just have to be careful with how you set things up.
There's a type of hash table called a dynamic perfect hash table that, with some modifications, is essentially what ...
- 9,037
5
votes
Accepted
How to resize a large, distributed hash table?
Yes, after storing many items in a distributed hash table spread over a hundred computers, if hypothetically we used the sort of hash function popular for in-RAM hash table, adding another computer ...
- 886
5
votes
Hash table collision probability
What are the odds of a collision given a fixed hash table size?
Size of hashtable
When hashing $k$ items into a hash table with $n$ slots, the expected number of collisions is
$n - k + k(1-{\frac{...
- 1,040
5
votes
Why is it best to use a prime number as a mod in a hashing function?
First of all, the question is phrased incorrectly. The following are equivalent and correct expressions of the intended question:
why must we use a prime number as the modulo of the hash value (not "...
- 51
5
votes
Accepted
Quadratic probing maximum load factor with $c_1 = c_2 = 0.5$ to guarantee successful insertion
For the case you describe ($c_1=c_2=1/2$, $m=2^k$), you can reach a load factor of 1. The probe sequence touches all the cells in the table.
As a practical matter, you probably don't want to get ...
- 166
5
votes
Accepted
What is an example of a weakly universal hash function that is not pairwise independent?
Let $U = [m]$, and let $h$ be the identity function.
If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by
$$
h_i(x) = \begin{...
- 275k
5
votes
How do you find a hash function that respects a custom equality function?
The way I can think of to do this is by some sort of normalization: that is, you need to find a function $f$ such that, if $\equiv$ is your custom equality and $==$ is the normal C++ (or whatever ...
- 29.7k
4
votes
Hash tables versus binary trees
GCC C++ case study
Let's also get some insight from one of the most important implementations in the world. As we will see, it actually matches out theory perfectly!
As shown at https://stackoverflow....
4
votes
How are hash tables O(1) taking into account hashing speed?
The tale that hash tables are amortized $\Theta(1)$ is a lie an oversimplification.
This is only true if:
- The amount of data to hash per item is trivial compared to the number of Keys and the ...
- 1,040
4
votes
What is the advantage of seperate chaining over open addressing?
In addition to what everyone else has said, you can get some of the locality back in a separate chaining scenario by unrolling the linked list.
Assuming a C-esque language, separate chaining might ...
- 21.7k
4
votes
Why is a (collision-less) hashtable lookup really O(1)?
To expand on David Richerby's answer, the term "hash function" is a little overloaded. Often, when we talk about a hash function we think of MD5, SHA-1, or something like Java's ...
- 173
4
votes
Confusion with analysis of hashing with chaining
The reason that we are using $\Theta(1+\alpha)$ rather than $\Theta(\alpha)$ is that $\alpha$ could be very small. Imagine for example that the hidden constant in both $\Theta$s is one, and that $\...
- 275k
4
votes
Does my simple, static hash table have O(1) worst case lookup?
Yes, your access time is $\mathcal{O}(1)$. Your construction time is a bit more complicated. Let $P(k)$ be the propability, that a set structure containing $k$ elements has a bucket with more than ...
- 529
Only top scored, non community-wiki answers of a minimum length are eligible