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
16 views

Two-Sum - Many Sums Algorithm Design Refactor

🧩 How to convert a two-sum item solution to have as many items as possible based on a given total capacity and optimizing for runtime complexity? 🚀 Original Two-Sum Determine whether there are two ...
0
votes
0answers
16 views

Two-Sum - Range Allowance Algorithm Design

🧩 What is the best way to find a two-sum solution within a range plus/minus of a total capacity provided, optimizing for runtime over memory complexity? 🚀 Original Two-Sum Determine whether there ...
0
votes
1answer
15 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
22 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
1answer
60 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
13 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
31 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
0answers
15 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 ...
2
votes
1answer
58 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
132 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
60 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 ...
1
vote
1answer
45 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
27 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
87 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
30 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
39 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
59 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
14 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
135 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
25 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
36 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
401 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
52 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
39 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
128 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
30 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
41 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
51 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
181 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
66 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
27 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
60 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
34 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
715 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$ "...
0
votes
1answer
668 views

Bin packing first-fit problem in $O(n \log n)$ time

Suppose we have $n$ objects with weights $w_i \in (0,1]$ and we must insert them into bins with the constraint that every bin must contain objects which weight less than $1 \, kg$. The first-...
8
votes
3answers
740 views

How to count in linear time worst-case?

This question and this question got me thinking a little bit. For sorting an array of length $n$ with $k$ unique elements in $O(n + k \log k)$, we need to be able to store counts of values in the ...
1
vote
1answer
239 views

Implementing a symbol table with a hash table and a stack

I was in class today, in a Language Translations course, thinking about the best way to write a symbol table for a compiler. My professor showed us a hash-table with linked-lists connecting different ...
0
votes
2answers
71 views

Hash function orders ships from closest to furthest from the origin

Suppose we have a circular radar that scans for ships in an area enclosed by $x^2+y^2 \leq z^2$ (a circle). We wish to design a hash function $h$ such that, we can order the $n$ ships from closest to ...
6
votes
1answer
114 views

Index matching algorithm without hash-based data structures?

I am programming in C, so I do not want to implement a hash-based datastructure such as a hashset or hashmap/dictionary. However, I need to solve the following task in linear time. Given two arrays $...
0
votes
0answers
40 views

Search operation in hash table

Suppose that we have a hash table of some size $s$ and we have a set of keys $K$. We decide to hash the keys using chaining. Now assume that we randomly select $k \in \mathbb{N}$ keys from $K$ and ...
3
votes
1answer
130 views

Small space hash functions that are weakly but not strongly universal

This is a follow up to this this question about weakly universal hash functions A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ : $$P_{h \in H_w}(h(x) = h(y)) \...
4
votes
1answer
479 views

What is an example of a weakly universal hash function that is not pairwise independent?

A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ : $$P_{h \in H_w}(h(x) = h(y)) \leq 1/m$$ Here the function $h:U \rightarrow [m]$ is chosen uniformly from the ...

1
2 3 4 5