Skip to main content

# Tag Info

## Hot answers tagged hash-tables

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 ...
• 3,734
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 ...
• 16.7k
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 ...
• 22.3k
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
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 ...
• 162k
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,734
6 votes

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,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 ... 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 ### 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 ... • 916 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 ... 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{... • 278k 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.8k 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,080 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 ... • 22.3k 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 ... • 30.7k 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 ... • 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 ... • 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 ... • 12.1k 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,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 ... • 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 ... • 278k 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,148 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 ...

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