# 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
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
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$. ...
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
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
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
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 ...
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
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
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
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
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
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, ...
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
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
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
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 ...
1 vote
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
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
40 views

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 ...
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 ...
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
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) ...
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
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
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
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 ...
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
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
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.
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