Questions tagged [hash-tables]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
12 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 <...
1
vote
1answer
24 views

Number of unique values in array in $\theta(n)$ average expected time

My idea is to initialize a hash table (with chaining) with $n$ cells, having load factor $\alpha = 1$ hence having $\theta(1)$ expected number of values in each cell in the hash table, then go cell by ...
0
votes
0answers
46 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
0answers
17 views

Counting distinct elements in array using hash table and measuring efficiency

I need to implement an algorithm to solve the Count-distinct problem given an array of $N$ elements using a hash table, and devise metrics with which to measure my algorithm efficiency. I was told I ...
2
votes
2answers
48 views

What kind of data structure should be used for working with dynamic sets where elements follow “normal distribution” and why?

I am wondering if Hash tables would be a good choice as it mentions dynamic sets to store data which follows normal distribution. I have doubt in this because normal distribution has bell shaped curve ...
0
votes
2answers
66 views

Find distinict elements in an array in $O(n)$ time

Given this pseudo-code that finds the number of distinct elements in the given array: ...
2
votes
0answers
29 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 ...
1
vote
1answer
54 views

Time complexity of checking whether a string exists in a HashSet

From what I know hash sets generally have complexity of $O(1)$ (unless the hash function is bad, but let's just ignore that for this question). However, sets need to either read the full data so as to ...
2
votes
1answer
41 views

How do we pick and switch hash functions from a universal family?

When we have a universal family of hash functions, it gives us a few useful mathematical guarantees. But, if we pick a specific function from the family and use it all the time it's effectively like ...
0
votes
0answers
18 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 ...
0
votes
0answers
27 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)] ←...
2
votes
1answer
22 views

find the strong component containing the vertex v

I'm trying to solve this question for practising purposes: "Describe a linear-time algorithm for computing the strong component containing a given vertex v. On the basis of that algorithm, ...
0
votes
0answers
37 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 ...
0
votes
0answers
21 views

If the load factor is a decimal (say 3.6), what is the length of each chain in a hash table that utilizes separate chaining?

I understand that if the load factor were 2, then the length of the chain would be 2 for each index in the array, but what happens if the load factor is a decimal? Do we round up or down?
0
votes
0answers
41 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
votes
1answer
25 views

Find best value for size of the table in hashing

Given a set of keys $\{i^2|0\leq i\leq 100\}$, and a hash table such that collision resolve by chaining. Our hash function is $ k \mod m$ . What is option is best for $m$ to decrease our search for ...
2
votes
2answers
431 views

Number of probes in a successful search in open address hashing

Given an open-address hash table with $\alpha$ < 1, the expected number of probes in a successful search is at most $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$ I read this in a book and the proof ...
1
vote
1answer
48 views

How 'Avalanche Effect' got its name?

I wonder how or why Avalanche Effect got its name. Avalanche Effect is a desirable property of cryptographic algorithms, wherein if an input is changed slightly (...
0
votes
0answers
13 views

What are overlay & underlaying topologies in DHT?

We are covering Distributed Hash Tables in my "Networks" class and one of the subsections is about the improvements that can be made to increase the performance of the chord. Here, the ...
1
vote
1answer
60 views

Counting letter frequency in array in O(1) with hash function

I want to calculate the frequency of each character in an array. (e.g ['a', 'b', 'o', 'p'] There are several ways to do this: A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ ...
4
votes
1answer
125 views

Why do we need hashed page tables for Paging in Operating Systems?

I understand that we might need hierarchical paging to handle page tables with sizes greater than the size of one frame, but what is the use of Hashed Page tables then? I would understand if we were ...
1
vote
1answer
46 views

Asymptotic growth of a series

How we can prove that: $$ \sum_{k=1}^{c \log n-1}\:k\cdot \left(\frac{1}{2}\right)^{\frac{k}{3}}\in O\left(1\right) \quad \mbox{?} $$
0
votes
1answer
32 views

How all values hash to the same value with a given formula

When looking at hashing, and given the following question: ...
0
votes
0answers
25 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 ...
0
votes
0answers
39 views

Quadratic probing in hash tables

I need to construct a hash table with initially $7$ empty entries. Now add $6$ values to the table using the quadratic probing function $$ s(j,k) = \lceil j/2 \rceil^2 (-1)^j $$ such that for some ...
0
votes
0answers
19 views

Bad data for hash function

Is it possible to choose such a nontrivial set of queries so that the amortized running time for a hash table with a public key and a function like $(a_{N − 1}k^{N − 1} +... + A_{1}k + a_0) (mod \: p)$...
0
votes
1answer
30 views

Why is this implementation of the hash function bad?

I have a task of hashing DNA sequences. Let the DNA be long sequences of four amino acids, which we will denote by the letters $A, T, G$ and $C$. My hash function $h$ take DNA as an input and return ...
0
votes
2answers
48 views

Two-Sum - Range Allowance Algorithm Design

🧩 What is the best way to find if there are two individual capacities that sum to a total capacity within a range of plus and minus the total capacity? Optimize for runtime over memory complexity. ...
0
votes
1answer
19 views

Choosing the right function

I'm trying to hash integers n = 4k(0,4,8,12,16...) into an array of linked lists of size 4 (chaining). What is a good hasing function that guarantees a good ...
0
votes
0answers
205 views

How does secondary clustering occur in hashing?

One of my friends said me that secondary clustering is the phenomenon occurring when the probe sequence has the same initial value. This definition shows that secondary clustering occurs in linear ...
0
votes
2answers
110 views

Two-Sum - Pre-sort Optimization Algorithm Design

🧩 Is it possible to optimize the runtime of a two-sum solution by receiving a pre-sorted input either in ascending or descending order? 🚀 Original Two-Sum Determine whether there are two items whose ...
0
votes
0answers
42 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: ...
0
votes
1answer
17 views

Bits needed to send parameters of perfect hash functions

Suppose that there is a server that has $n$ files. The server is used to construct a perfect hash function for those files and then the computed parameters will be sent to a user. These parameters ...
2
votes
0answers
38 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
vote
1answer
87 views

Uniform Hashing. Understanding space occupancy and choice of functions

I'm having troubles understanding two things from some notes about Uniform Hashing. Here's the copy-pasted part of the notes: Let us first argue by a counting argument why the uniformity property, we ...
1
vote
2answers
343 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
0answers
68 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 ...
2
votes
2answers
133 views

Double hashing constraints

For double hashing, we have some constraints on $h'(k)$ (1) It should never evaluate to 0 (2) It should be relatively prime to m How to show that all slots in an open addressing table will be ...
0
votes
1answer
39 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.
0
votes
4answers
195 views

What is the best hash functions for millions of String keys?

I have a situation where there are a million Keys of type String and I want to use the Symbol table to store the key and the value. The problem that the retrieval process is too slow and I want to ...
1
vote
1answer
40 views

Is there a way to hash a turing machine?

If we have a Turing machine with various $\delta(q_i, a_i) = (q_j, a_j, Direction)$ where Direction can be L or R(denoting the movement of head), can we encode it uniquely to some natural number(which ...
1
vote
2answers
50 views

Theoretical question about Zobrist hashing and chances of collision with slight modification

I have a hash table that uses zobrist hashing to calculate the hash for various positions. The hash table is used to look up various transpositions. For some positions I do not want to allow any ...
1
vote
1answer
31 views

Lower bound time complexity for obtaining an arbitrary entry in a hashtable

I just answered this question on StackOverflow, which asks for an efficient algorithm such that given a nonempty hashtable, the algorithm should return a pointer to an arbitrary nonempty entry in the ...
0
votes
1answer
130 views

Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list

Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus ...
0
votes
1answer
395 views

Separate Chaining hashing: time complexity of successful search

In a simple uniform hashing with chaining collision, the time complexity of a successful search is: $Θ(1 + (1 + \frac{α}{2} - \frac{α}{2n}))$ where $α=\frac{n}{m}$, but I don't understand how to ...
0
votes
2answers
29 views

Error handling in a size_t hashfunction

For school I have a big assignment on hashtables etc. One of the functions is a size_t function where we calculate the hash value. (Keep in mind the structure of every function is given so we are not ...
0
votes
0answers
51 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 ...
0
votes
1answer
33 views

What is the best of given hashfunctions?

In our exam on algorithms there was a question, where given 3 hashfunctions we had to chose one and explain why it's the best. h_1(x,i)=(x+5*i) mod 1000 h_2(x,i)=(x+17*i) mod 1000 h_3(x,i)=(x+32*i) ...
0
votes
1answer
48 views

Primary clusting in linear probing coliision resolution: there can only be one cluster/block, right?

I believe primary clustering is a problem with the linear probing method of hash collision resolution. But the description makes it sound like there can be multiple clusters of contiguous blocks. I ...
1
vote
2answers
1k views

Quadratic Probing Infinite Loop?

I understand the definition of Load Factor and how Quadratic Probing works. But what happens in the case where quadratic probing cannot find an empty slot for a new element? According to https://en....

1
2 3 4 5