109 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 ...
user avatar
26 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 ...
user avatar
  • 13.2k
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 ...
user avatar
17 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 ...
user avatar
  • 18.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 ...
user avatar
  • 379
15 votes
Accepted

What does "non-pathological data" mean?

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 ...
user avatar
  • 19.1k
15 votes

How are hash table's values stored physically in memory?

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$, ...
user avatar
11 votes

What does "non-pathological data" mean?

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 ...
user avatar
  • 3,570
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 ...
user avatar
9 votes
Accepted

How should I design a hash table where all the keys are permutations?

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/...
user avatar
  • 206
9 votes

How are hash table's values stored physically in memory?

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 ...
user avatar
  • 19.1k
9 votes

Memory usage of a BST or hash table?

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: $$...
user avatar
  • 18.7k
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 ...
user avatar
  • 2,994
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 ...
user avatar
  • 140k
7 votes

Why can't hash tables provide O(n) sorting?

The reason you've never heard of hash tables being used like this is that hash tables are either "too much" or "not enough" in this situation. If the range of elements being sorted is small, then you ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 70.8k
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 \...
user avatar
6 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 ...
user avatar
  • 9,325
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 ...
user avatar
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$ ...
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 ...
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-...
user avatar
  • 32.9k
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 ...
user avatar
  • 32.9k
5 votes
Accepted

How to find expected number of slots of a certain size k in hash table?

I assume under "size of slot" you mean length of chain in hash table with separate chaining collision resolution. From Knuth, TAoCP, Vol. 3, 6.4, ex. 34 probability of k-length chain in hash table ...
user avatar
  • 385
5 votes
Accepted

Where does the terminology of open addressing resp. closed hashing come from?

The short answer is that the terms were coined by different people for different purposes, and it's because hash tables historically had two different contexts: in-memory data structures (I believe ...
user avatar
  • 18.7k
5 votes
Accepted

Why does appending permutations of servers at the end of hash table avoid bottlenecks?

Adding permutations isn't about preventing slow servers from becoming bottlenecks, rather it's about dispersing a convoy once one forms behind a slow server. Because of the way tract locations are ...
user avatar
  • 7,833
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{...
user avatar
  • 1,000
5 votes
Accepted

What exactly is a hash function?

A hash function is a pseudorandom function with a constant range. Ideally, one would like two central properties: The hash function should be easy (fast) to compute. The probability that two inputs $...
user avatar
5 votes
Accepted

Why can't hash tables provide O(n) sorting?

The algorithm you give is exponential time, not linear. If you're given $n$ $b$-bit entries, the size of your input is $nb$ bits but the algorithm takes time $\Theta(2^b)$, which is exponential in the ...
user avatar

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