129
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,764
29
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 ...
- 17.1k
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 ...
- 23.8k
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 ...
- 12.1k
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,764
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-...
- 39.1k
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 ...
- 39.1k
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
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
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{...
- 279k
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 ...
- 30.1k
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
What Exactly Does the Term "Key" Mean with Regards to a Hash Table?
A hash table is an implementation of a more general principle: A key/value table. In a key/value table you can insert values according to a key, you cannot add two values under the same key. You can ...
- 31.6k
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 ...
- 23.8k
4
votes
Hash functions and pathological data sets
Assume there is no such bucket. Then each bucket has at most $|U|/n - 1$ items. There are $n$ buckets, so the total number of items is at most $n*(|U|/n - 1) = |U| - n$. This is less than $|U|$, which ...
- 3,390
4
votes
How exactly Hashing performs better than a Binary Search?
You are asking excellent questions!
The answer to your first question, regarding the difference between $O(\log n)$ and $O(1)$, is that whereas binary search scales with the size of the array, ...
- 279k
4
votes
Static hash tables
You can use the (minimal) perfect hash function, which is like in your case static (because dynamic insertions / deletions require rehashing), so there is no collision resolution - there are none. The ...
- 9,495
4
votes
Static hash tables
It is always possible to build a static hash table which has guaranteed O(1) lookup time, provided you allow O(N) empty slots.
For example, a cuckoo hash table will give you a definite found or not ...
- 12.1k
4
votes
"Hash" Probing?
Your scheme is very similar to Cuckoo Hashing. In Cuckoo Hashing you have two (or, in variations, more) independent hash functions $h,g$. To insert an item $x$ you check at location $h(x)$. If that ...
- 5,981
4
votes
Accepted
Knuth's proof of O(1) for linear probing
Let $p_i$ be the probability that position $i$ is empty. A simple coupling (detailed below) shows that $p_i = p_j$ for all $i,j$, and so $Mp_0 = p_0 + \cdots + p_{M-1}$. Now let $X_i$ be the indicator ...
- 279k
4
votes
Accepted
BST representation of Hash Tables
What the author means by implementing a HashTable as a BST is simply implementing a BST with $insert(), \space delete() \space and \space search()$ with slight modifications
The node of the BST would ...
4
votes
Accepted
When retrieving values from a hash table with linear probing, how do we know if the wanted value had not been shifted?
With linear probing, the appropriate bucket stores both the value and the literal key. So when retrieving, you start in the bucket determined by the hash code and check if the key is the same. If it's ...
- 7,176
4
votes
Accepted
Bin packing first-fit problem in $O(n \log n)$ time
Your solution has $O(n)$ computational complexity but it doesn't implement the first fit algorithm. The thought behind your solution is to insert the items one by one in the given order (that's ...
- 371
4
votes
Accepted
How 'Avalanche Effect' got its name?
The term first described by Horst Feistel (1973)
As the input moves through successive layers the pattern of 1's generated is amplified and results in an unpredictable avalanche.
It is rather very ...
- 1,171
3
votes
Average number of collisions before successful insertion into hash table
1 / (1 - alpha) is about right, if you ignore that for the second slot the chance is (m - 1 - n) / (m - 1) and so on. But when that difference becomes relevant, you should have increased the size of ...
- 31.6k
3
votes
Accepted
Hash functions producing uniform outputs
What are the quadratic residues in $\mathbb{Z}_{10}$? What about the cubic residues? What are the orders of $[11]$ and $[12]$ in the group $(\mathbb{Z}_{10}, +)$?
A brief solution follows.
For the ...
- 4,272
3
votes
Accepted
Do cryptographic hash function solve clustering problems with linear probing?
Cryptographic hash functions are not better than any hash functions with good distribution and "avalanche effect" (eg xxHash) on this regard.
Do they ensure "best possible" lookup performance? In the ...
- 385
Only top scored, non community-wiki answers of a minimum length are eligible