# Tag Info

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

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

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

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

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

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

### 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 "...
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 ...
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{...

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

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

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

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