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
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
1
answer
75
views
Hashing a histogram to save the current form of the histogram and reuse it
im trying to think of an algorithm which would "hash a histogram". The problem im trying to solve needs to store all histograms that represent $k$ long sub-strings of a string $S,ドル so that ...
1
vote
1
answer
108
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 ...
1
vote
1
answer
91
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 ...
0
votes
1
answer
239
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 ...
0
votes
1
answer
53
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 ...
1
vote
1
answer
150
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 ...
0
votes
2
answers
99
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 ...
3
votes
3
answers
288
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 ...
0
votes
0
answers
54
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
1
answer
112
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 ...
0
votes
1
answer
180
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 ...
0
votes
0
answers
112
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 ...
user avatar
Nishant Singh
0
votes
1
answer
64
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 ...
1
vote
0
answers
138
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. ...
1
vote
2
answers
111
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 ...