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
Filter by
Sorted by
Tagged with
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 ...
user avatar
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$. ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
  • 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$. ...
user avatar
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 ...
user avatar
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, ...
user avatar
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.
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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(...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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)...
user avatar
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 ...
user avatar
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 \...
user avatar
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 ...
user avatar
  • 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): ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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}) \ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 <...
user avatar
  • 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) ...
user avatar
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 ...
user avatar
  • 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)] ←...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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: ...
user avatar
  • 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.
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar