The 2024 Developer Survey results are live! See the results

# Questions tagged [hash-tables]

A finite map data structure that addresses stored values using a function that maps many values to few addresses.

270 questions
Filter by
Sorted by
Tagged with
1 vote
63 views

### How bad re-hashing can cost?

Lets assume that the load factor of a hash table of size $n$ became inappropriate. The process of re-hashing involves choosing a new hash function. A good choice of a new function will make the cost ...
• 147
1 vote
42 views

### Do edge lists have O(E) storage if default values are used for absent keys?

Ordinarily, edge list representations of graphs take $O(V+E)$ space, where $V$ is the number of vertices and $E$ is the number of edges. For example, consider a graph with 5 nodes and a single edge ...
• 1,570
57 views

### Time complexity of delete and insert operations in a hash table

Let's take a hash table where the collision problem is solved using a linked list. As we know, in the worst case, due to collisions, searching for an element in the hash table takes O(n). But why does ...
• 11
14 views

### Hash function for use with hash table, given power distributed integers

Suppose I have integers that follows a power distribution: $P(n) \propto 1/(n + 1)^\alpha, n \geq 0$ What hash function is a good choice to avoid collisions. The usecase is keys in an ...
• 149
1 vote
61 views

### Efficient data structure for fast Insertions, lookups, and union operations on sets

I need data structure that is able to perform the following operations efficiently: Insert a new element into a set. Lookup element in set. Compute the union of two sets. Union operation should ...
33 views

### Search times for hash tables using open addressing for collision resolution

With regards to hash tables using open addressing as collision resolution mechanism, Introduction to Algorithms, Chapter 11, page 294 (4th edition, 2022 printing) states the following Deletion from ...
• 13
82 views

### How to select hash functions for cuckoo hashing?

In cuckoo hashing, an insertion failure occurs when there is an infinite loop of displacements. This is detected by a “max iterations” count on the insert function. When the insert fails, the table is ...
• 131
30 views

### What is the probability of no collision in two hash tables, where a key is hashed to both tables and chained to the shortest chain from the tables?

can someone help me with this problem? Consider a hashing scheme that uses r hash tables T1, . . . , Tr of size m, where collisions in each table are resolved by chaining. When a key k arrives, it is ...
25 views

### Create a class or structure like union of ranges

How to create a structure which acts as union of ranges. In that structure new ranges can be inserted beforehand and then some queries are asked to find out if the given point is covered by any of the ...
1 vote
59 views

### Trouble Understanding Yao's "Basic Model" for Hashing

I am trying to understand the probing model proposed by Yao in the paper "Should Tables Be Sorted?". Yao suggests a "Basic Model" (in the section appropriately titled "Basic ...
• 244
93 views

### Find a substring length $k$ with maximum occurrences

Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string. We want $O(S)$ time complexity in an average case. I think the solution lies in sophisticated ...
• 183
59 views

### Effect of Insertion order on number of collisions in Double Hashing

How is the number of collisions affected by the order of insertion of elements in a hash table using double hashing? I've tried uing different hash function for double hashing with different set of ...
38 views

### Collisions in hash table - Is this table wrong?

I have the following hash table with hashcodes being quadratic numbers. Why do 0, 16, and 64 have different number of collisions when they map to the same number (line %16). Also how is it possible ...
• 123
1 vote
94 views

### How to properly save Zobrist Keys?

In a project of mine, I want to represent states as efficiently as possible. Initially, I went ahead with a BitBoard representation and some clever tricks to speed up the evaluation of the game tree. ...
• 111
42 views

### Chord Ring with limited table size of 3

In the normal case of a chord ring the big O notation of the look up is O(logn) because of long haul pointers of the Finger Table (or Routing Table). In this question what if the Finger Table has a ...
• 111
189 views

• 11
140 views

### Is there a hash-map implementation optimized to favor key lookups based on frequency (if key is referenced the most then it is searched first)?

I have started to play around with HTTP3 which relies on QUIC for transport. I have noticed that I very often have a finite number of Web Transport sessions stream data continuously along side burst-y ...
• 101
1 vote
843 views

### What is a good load factor for seperate chaining (closed addressing)?

For open addressing, I know that once you have around 70% table being filled you should resize because more than that you get collision. But for closed addressing, I read that load factor should not ...
• 11
255 views

### Consistent Hashing Algorithm Without Distribution / Load Balancing

I need some help finding or creating a consistent hashing algorithm with the following properties: Given N buckets, only distributes keys to bucket N. When number of buckets are increased from N to N+...
1 vote
2k views

### Averege time complexity of open addressing

I get that it depends from the number of probes, so by how many times the hash code has to be recalculeted, and that in the best case there will only be one computation of the hash code and the ...
• 115
3k views

### Why is the Java HashMap load factor 0.75?

I can't understand why the Java HashMap load factor is 0.75. If I understand well, the formula for the load factor is n/m, where n is the number of key and m is the number of position in the hash ...
• 367
43 views

### Confused about the appropriate slot in linear probing

The following paragraph is from the book CLRS: Given an ordinary hash function $h' : U \rightarrow \{0, 1, ..., m - 1\}$, which we refer to as an auxiliary hash function, the method of linear probing ...
• 411
1 vote
158 views

### Iterable hash table

I'm currently working on implementing all the major data structures from C++ to better understand them and I arrived at the unordered_map, which should be a hash table implementation (it's actually ...
• 113
1 vote
273 views

### Hash maps vs extending structs / classes

A hash map that maps keys of type $K$ into values of type $V$, is essentially equivalent to "extending" this type $K$ to also contain an Option<V> ...
• 11.6k
24 views

### Unusual approach to tabulation algorithm

Consider simple tabulation algorithm firstly for Fibonacci numbers. We will use the dictionary as a cache (and Python as example PL): ...
• 111
178 views

### Analysis of a calculation of expected number of collisions in hashing

For a formal problem statement, I quote from the text Introduction to Algorithms by Cormen et. al Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. ...
• 1,142
29 views

### worst case time for adding values to a hash table

A certain hash table uses external chaining, and is resized each time its load factor exceeds 3. Also, if an addition does not cause the load factor to exceed 3, but does cause some bucket to exceed 6 ...
• 131
93 views

### Does DHT (Distributed Hash Table) allow to list ALL (not only nearest) nodes?

As I know any local DHT keeps only some of nodes - if the network is small/very small then all nodes, otherwise only some of them (nearest?). So, when I checked different Golang implementations of DHT ...
• 101
4k views

In answering this question, I was looking for references (textbooks, papers, or implementations) which represent a graph using a set (e.g. hashtable) for the adjacent vertices, rather than a list. ...
• 7,138
183 views

### How do i delete one single unequal element from an array of equal elements without using hashing?

The rules of the question state that: Only one element is different. Rest are all same. Array A size is 8. I need to find the different element and remove it (Hashing cannot be used). I have not ...
1 vote
231 views

### A hash function for a 2D hash table with a scattering property?

I have an $n\times n$ matrix, and want to find a bijective function $h:[n^2] \to [n]\times [n]$ that can act as a hash function to map the numbers 1 through $n^2$ to row/column indices in my matrix. ...
• 11
583 views

### Build a priority queue using dictionary

QUESTION: Can we Implementing priority queue with hash table please? As I understand, dictionary/hash table does not have sorting mechanism inside. It adds pairs of $<key,value>$ to hash table. ...
• 515
336 views

### How does a hash table not require all the keys to be looked through to find a value, i.e. O(N)?

Before starting, I want to say that I understand time complexity, and I understand how a hash table is considered O(1) vs an array having a time comp. of O(N) in terms of what you learn. What I don't ...
• 156
534 views

### hash-tables - Expected-time for an unsuccessful search

The following question is from MIT-OCW 6.006, Spring-2008, Problem-Set 2, Q-3.c. Suppose you have a hash table where the load-factor $\alpha$ is related to the number $n$ of elements in the table by ...
• 101
1 vote
101 views

### How does the Go language implements maps?

To what extent is the MAP data type implementation language dependant??? If we know that C++ implements maps as Red Black Trees, unordered maps as hash tables, How C++ and alike maps are actually ...
• 138
38 views

### The interpretation of expected time bound for searches in a hash table

As CLRS book,page 260 stated, Thus, the total time required for a successful search is $\Theta{\left(2+\alpha/2-\alpha/2n\right)}=\Theta{(1+\alpha)}$ I wouldn't have any problem if the author says ...
• 103
1 vote