Questions tagged [hash-tables]
A finite map data structure that addresses stored values using a function that maps many values to few addresses.
62
questions with no upvoted or accepted answers
7
votes
0
answers
935
views
Double Hashing and Variations for Bloom Filters
I am reading a few papers on Bloom Filters – Bloom Filters in Probabilistic Verification (Dillinger and Manolios) suggests the following allocations for double and triple hashing respectively
...
- 387
4
votes
0
answers
37
views
Data structure for identifying elements while keeping track of relation
I'm looking for a data structure representing a finite set $I$ and a $d$-relation $R \subseteq I^d$ such that the following operations can be implemented efficiently:
Add a new element $i$ to $I$.
...
3
votes
0
answers
54
views
What data structure should I use for storing my data?
I am currently looking for a way in which I can store my data, and quickly look it up.
What currently seem to be the best idea is to use a hash map.
reasons:
To identify what item I am looking for, ...
- 131
3
votes
0
answers
713
views
How to sort an array $A[1..n]$ with $\sqrt n$ distinct elements in $\Theta(n)$ time and $\Theta(\sqrt n)$ space?
I need to write an algorithm which will sort an array $A[1..n]$ with $\sqrt n$ distinct elements in $\Theta(n)$ time and $\Theta(\sqrt n)$ space?
The solution must use hash-tables and advanced data ...
- 517
2
votes
1
answer
53
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,034
2
votes
0
answers
43
views
Finding the longest power subsequence
A power sequence is a sequence containing consecutive powers of a number starting from power one. for example $3^1, 3^2, 3^3$ is a power sequence. The question is to find the length of the longest ...
- 21
2
votes
0
answers
69
views
In Universal Hashing- probability of poor performance is small and is the same for any set of keys of the same size
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following claim:
Universal Hashing uses randomization.For the example of a compiler's symbol table, ...
- 1,034
2
votes
0
answers
1k
views
Open hashing vs closed hashing
What are advantages of closed hashing over open hashing?
I know the difference between those two but can't figure out why would closed hashing be better in any way.
Thanks.
- 21
2
votes
0
answers
420
views
hash-table subsets
Having trouble figuring this out.
If I have 2 sets of integers how would I use a hash table to test if set A is a subset of set B (in pseudocode).
I think I understand that basically I would need to ...
- 51
2
votes
0
answers
103
views
What is the easiest solution to check if a rational number is in the Cantor set?
To check that a rational number is in the Cantor set, I have written an algorithm to obtain its base-3 representation. To verify if the representation is periodic, I used a hash table in order to save ...
- 21
2
votes
0
answers
93
views
What are the substitues for Kolmogorov Complexity to analyse Hashing
The paper "Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses" <http://www.itu.dk/people/pagh/papers/sparse.pdf> is the only one that uses Kolmogorov Complexity to obtain ...
- 137
2
votes
0
answers
177
views
Storing variable length Keys in hash table itself
I wrote a custom hash table for a project I'm working on. The core functionality was pretty simple rolling table:
In each table there is a memory section for HashItemReference(integer SecondHash, ...
- 21
2
votes
0
answers
828
views
Improve the runtime of hashtable operations by keeping lists in sorted order
The following is a question from the textbook Introduction to Algorithms, however a solution to the problem is not given...
Professor Marley hypothesizes that he can obtain substantial performance ...
- 179
2
votes
0
answers
76
views
Tradoff between space and false positive rate when using bloom filters
Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is ...
- 109
1
vote
2
answers
31
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
1
vote
2
answers
596
views
Double Hashing with Strings as key
How would you choose the second hash function with for double hashing with string as key?
My first hash function is the scalar product of a random int array with the 16 bit number of each char. Is ...
- 11
1
vote
0
answers
89
views
Variance of chain length in hashtable
I have a hashtable with length $m$. Initially it's empty. Next, $n/2$ unique random numbers $\in [0, n]$ are added to it.
What would be variance of chain length when such $n/2$ numbers are being added ...
- 11
1
vote
0
answers
40
views
Linear probing and tabulation hashing
I'm currently reading the paper "The Power of Simple Tabulation Hashing" by Mihai Patrascu and Mikkel Thorup [1] because I want to adapt the proof of the constant time complexity of linear probing for ...
- 285
1
vote
0
answers
40
views
Cuckoo hashing with a stash: how tight are the bounds on the failure probability?
I was reading this very good summary of Cuckoo hashing.
It includes a result (page 5) that:
A stash of constant sizes reduces the probability of any failure to
fall from $\Theta(1/n)$ to $\Theta(...
- 111
1
vote
0
answers
99
views
Can hash tables handle variable sized entries?
Let's say I have a hash table of 10 buckets where each bucket is of a number of bits. However each bucket doesn't have to have the same number of bits. Is it possible to achieve this? Or does it ...
- 121
1
vote
0
answers
155
views
Direct addressing on a huge array
A Question from CLRS book:
(CLRS 11.1-4) We wish to implement a dictionary by using direct addressing on a
huge array. At the start, the array entries may contain garbage, and initializing the
...
- 11
1
vote
0
answers
23
views
How to chose the condition for expand in hash-table?
How can I chose the condition for expanding of the array in chain-hashing if I want that given some cell (that contains elements) , the number of cells that I need to move about them is O(1) until the ...
- 11
1
vote
0
answers
1k
views
Why is the module of the second function in double hashing a prime number?
When using double hashing, the second hash function is defined as $$h_2(x)=A-x\mod A,$$ where $A$ is a prime number less than the capacity of the hash table. But why must $A$ be a prime number?
(This ...
- 11
1
vote
0
answers
156
views
why does message authentication using 2-universal family of hash functions require a prime number of possible hash values?
I am self-studying the book Intro to Algorithms 3ed by CLRS. One of the problems seems to give a piece of information that is not necessary, Problem 11-4 in the book states
Let H be class of hash ...
- 818
1
vote
0
answers
123
views
Bloom filters vs storing hashes as numbers
In competitive programming there is a trick for storing a set of strings(or objects really) to reduce memory - you only keep the hashes of the strings in a hash-table (usually as 32 or 64 bit integers)...
- 1,277
1
vote
0
answers
78
views
Find unique vectors by linear algorithm
I was thinking about the homework problem:
Given $n$ vectors in 3D: $(\mathbf{v_1},\mathbf{v_2},\dots,
\mathbf{v_n})$. Their coordinates are positive integers and less than $10^9$.
We should ...
- 131
1
vote
0
answers
32
views
Problem occurring when changing hash table size
I'm practicing an exam for a data structures course. There's a question about a hash table with hash function:
$$h'(k,i)=h_1(k)+i*h_2(k) \mod{11}$$ where
$$h_1(k)=k \mod{13}$$ and $$h_2(k) = 1 + k \...
- 11
1
vote
0
answers
406
views
What needs to be done after deleting an item in a hash table built under opening addressing with linear probing
In some textbook problems, the problem asks me to insert a bunch of elements and remove a bunch of elements.
Insertion is done using linear probing, i.e. h = XmodR + I, when there is a collision, I ...
- 809
0
votes
0
answers
22
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):
...
- 101
0
votes
0
answers
23
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 ...
- 21
0
votes
0
answers
37
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
0
votes
1
answer
71
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 ...
0
votes
0
answers
32
views
Split-Ordered Lists: Lock-Free Extensible Hash Tables
I am reading the research paper "Split-Ordered Lists: Lock-Free Extensible Hash Tables" by Nir Shavit and Ori Shalev.
https://dl.acm.org/doi/10.1145/1147954.1147958
I was just wandering if ...
0
votes
0
answers
11
views
Comparing the added cost of replacing a map with an extra Merkle tree to provide non-membership proofs
Here is the trade-off:
-Merkle trees that append leaves to the right tend to have a better Locality of reference, and thus shorter batch proofs (a lot of sibling nodes will be common and thus fetched ...
- 140
0
votes
1
answer
244
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
0
votes
0
answers
48
views
Order-preserving perfect hashing of integer tuples
There is an $M \times N$ integer matrix $A = [a_{ij}]$, $M \gg N \ $,
$\forall j \ \exists a_{max_j} \leq M \ \forall i : 0 \leq a_{ij} < a_{max_j} \ $,
$\forall j \ \forall n \in [0, a_{max_j}) \ ...
- 181
0
votes
0
answers
55
views
Confused about a corollary in MIT.Introduction.to.Algorithms(CLRS), seek help
Desc'
I was reading CLRS Book's chapter 11 Hash Tables, and encountering some problems.
There is an corollary in CLRS book, in Page 275 (quoted on the bottom of post), which discussed the expected ...
- 3
0
votes
0
answers
27
views
What is the time complexity of comparing two Merkle trees?
I have a simple recursive function that compares two merkle trees and accumulates the differences in the leaf nodes. However, I am unable to measure the time complexity of it. Specifically, I would ...
- 101
0
votes
1
answer
33
views
Detecting and correcting collisions in (Zorbist) hashing to avoid errors in transposition table
Context
Say I have a transposition table that uses keys produced by (e.g. Zorbist) hashing game positions.
The table has a finite recycled memory (key % p is the <...
- 175
0
votes
0
answers
55
views
The Most efficient algorithm for a program that returns true if the two strings only differ by one character
We have a list of strings with the same length. Each string only contains a, b and c.(For instance : aabcc)
The program gets a string and returns true if the two strings(input and the list of strings) ...
0
votes
0
answers
23
views
Hash tables for storing data in an application that supports partial search
Is a hash table a good data structure for storing data in an application that support partial search such as "select * from MyTable where name like 'John%'. If not, what is?
I would have thought ...
- 143
0
votes
0
answers
59
views
Bloom filter variant(using only half of it)
A Bloom filter is an array $B[1..m]$ of bits, together with a collection of $k$ independent ideal random hash functions $h_1,h_2,...,h_k$. To insert an item $x$ into a Bloom filter, we set $B[h_i(x)] ←...
- 141
0
votes
0
answers
96
views
Why is LRU cache not implemented using doubly linked list with just two nodes? Do we even need double linked list?
I don't understand why do we need to have more than two nodes in doubly linked list when all we need to maintain is the most recent and least recently accessed nodes.
I was going through solutions for ...
- 101
0
votes
0
answers
62
views
Algorithm question: Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1
Algorithm question:
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
Example 1:
Input: [0,1] Output: 2
Explanation: [0, 1] is the longest ...
- 1
0
votes
0
answers
29
views
Why is deleting from a hashtable when there is a linked list at h O(1)?
I am currently studying hashtables and whilst the concept of chaining makes perfect sense, as does why searching is O(n) and also inserting (at head) is O(1), I dont understand why deleting an item is ...
- 83
0
votes
0
answers
92
views
String membership in hash set time complexity
Given a string s and a hashset of strings words, what is the time complexity of the operation: ...
- 101
0
votes
1
answer
55
views
Does making the keys of a hashtable the same length make the hashtable any better?
The question popped up in my head. The hash function used is Murmur3.
- 101
0
votes
0
answers
77
views
How to generate unique keys for different two dimensional matrices having different sizes?
No. of rows in the table (as given in image) is not known beforehand . The problem I am dealing with generates different 2-D matrices based on the input data given. As soon as a matrix generates it ...
- 21
0
votes
1
answer
121
views
Need help with adding elements to hashtable with linear probing
Here is an example problem which I have having trouble figuring out. The red text is the answer.
I get how the values are added before the hashtable is resized... that is common sense. (Insert 0 at ...
0
votes
0
answers
76
views
Formula for number of attempts to insert a value into a hash table using linear probing
Suppose I have the simple hash-probe function and we are using linear probing
(k,i) = (k + i) mod m
Assume that there are 3 keys that need to be inserted(k1,k2,k3).
Is there a formula for the ...
- 101