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
0answers
10 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
42 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)$ ...
3
votes
0answers
32 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
42 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
30 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
24 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
32 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
17 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
27 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 ...
1
vote
2answers
42 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
18 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
75 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
87 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
20 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
32 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, ...
0
votes
0answers
20 views

In Hashing-collison resolved by chaining: Intuition behind $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$

Hashing-collison resolved by chaining: $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$ I was going through the text Introduction to Algorithms by Cormen et. al. and in the ...
1
vote
1answer
68 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
202 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
61 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
70 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
34 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
3answers
100 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
37 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
40 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
25 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
84 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
0answers
15 views

Describe a procedure that selects a key uniformly at random from among the keys in the hash table and returns it in expected time O(L⋅(1+1/α))

This question is from CLRS. The following is what I understand: The procedure is as follows: 1. First we randomly choose one index in T[m] 2. Let nk denote the number of elements in the chosen slot T[...
0
votes
1answer
214 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
27 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
28 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
29 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
41 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
586 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
votes
1answer
61 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
0answers
40 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 ...
1
vote
1answer
132 views

Independence of order of insertion hashtable with open addressing

I'm taking a data-structure class, and the lecturer made the following assertion: the number of attempts needed to insert n keys in a hash table with linear probing is independent of their order. ...
0
votes
2answers
64 views

Is this a misleading or undesirable implementation of a hash map?

I read a C++ implementation of a hash map here. https://www.geeksforgeeks.org/implementing-hash-table-open-addressing-linear-probing-cpp/ Let's say key k1 has a ...
3
votes
1answer
109 views

Choosing an independent hash function, given hash function value

Supposed we have a function $h:U\to [m_1]$. Given this hash function, can we generate without using randomization or a universal hash collection another hash $h':U \to [m_2]$, which depends on $h$ ...
0
votes
1answer
32 views

Pairwise hash functions that are independent from each other

Is there there a way to build a collection of universal hash functions $H=\{h| h:U\to D \}$ where the values of two hash functions are independent one from another? i.e., $\Pr_{h_1,h_2\in H}(h_1(x)=y ...
2
votes
1answer
49 views

HashTable open-addressing is used for main array or buckets

I am trying to understand the HashTable open-addressing technique. I see there are three approaches: linear, quadratic and double hashing. I'm wondering are these techniques used: to find an index of ...
3
votes
1answer
54 views

Are all data structures in the von Neumann architecture based on the array, or array-like?

I am an old Pythonista now learning C and how various data structures and types are implemented, such as binary trees and hash tables. Learning about the latter, leads me understand that the hash ...
5
votes
4answers
195 views

How do you find a hash function that respects a custom equality function?

I've been tasked with hashing arbitrary types in C++, with the caveat that A == B implies hash(A) == hash(B) even if equality of ...
0
votes
1answer
68 views

Perfect Hash Function: How does it cope with lookups outside the set of keys?

I'm currently looking at perfect hash functions. One thing I miss from the texts I've read so far is, how they cope when attempting to look up with a key that is outside of the set from which the ...
4
votes
0answers
29 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$. ...
1
vote
2answers
62 views

What does “prime” mean in this context?

In a lecture video the instructor introduced the quadratic probing method for hash tables. The formula he gave was the following: $h(k,i) = (h'(k) + c_1 + c_2i^2)$ $\% M$ where $h'$ was h "prime". ...
1
vote
0answers
30 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 ...
1
vote
0answers
35 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(...
3
votes
3answers
847 views

Simple Uniform Hashing Assumption and worst-case complexity for hash tables

Is the Simple Uniform Hashing Assumption (SUHA) sufficient to show that the worst-case time complexity of hash table lookups is O(1)? It says in the Wikipedia article that this assumption implies ...
0
votes
0answers
34 views

Construction of hash function with a given distribution

Two questions about the construction of a hash function: Let $U = \{u_1,...,u_n\}$ be a set of size $n$, and suppose that one is interested in a function $h\colon U \rightarrow [0,1]$ such that $h$ "...

1
2 3 4 5