Skip to main content
Share Your Experience: Take the 2024 Developer Survey
128 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 ...
Mario Cervera's user avatar
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 ...
Pål GD's user avatar
  • 16.6k
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 ...
Pseudonym's user avatar
  • 22.2k
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 ...
ddyer's user avatar
  • 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 ...
Derek Elkins left SE's user avatar
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.'s user avatar
  • 161k
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$ ...
Mario Cervera's user avatar
6 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{...
Johan's user avatar
  • 1,080
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 ...
Philip Becker's user avatar
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 ...
user2369284's user avatar
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-...
John L.'s user avatar
  • 39k
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 ...
John L.'s user avatar
  • 39k
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 ...
David Cary's user avatar
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 "...
bking's user avatar
  • 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 ...
Keith Randall's user avatar
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{...
Yuval Filmus's user avatar
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 ...
Joey Eremondi's user avatar
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....
Ciro Santilli OurBigBook.com's user avatar
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 ...
Johan's user avatar
  • 1,080
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 ...
Martin Glauer's user avatar
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 ...
Pseudonym's user avatar
  • 22.2k
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 ...
gnasher729's user avatar
  • 30.4k
4 votes

improving java 8's implement to hash map using avl tree

This page on Oracle's website says: The alternative String hash function added in 7u6 has been removed from JDK 8, along with the jdk.map.althashing.threshold system property. Instead, hash bins ...
tsleyson's user avatar
  • 3,128
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 ...
jbapple's user avatar
  • 3,380
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 ...
rici's user avatar
  • 12k
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 ...
Evil's user avatar
  • 9,465
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 ...
adrianN's user avatar
  • 5,951
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 ...
Yuval Filmus's user avatar
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 ...
RandomPerfectHashFunction's user avatar
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 ...
Draconis's user avatar
  • 7,138

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