All Questions
Tagged with hash-tables data-structures
108 questions
1
vote
1
answer
68
views
How bad re-hashing can cost?
Lets assume that the load factor of a hash table of size $n$ became inappropriate.
The process of re-hashing involves choosing a new hash function.
A good choice of a new function will make the cost ...
- 191
1
vote
1
answer
72
views
Efficient data structure for fast Insertions, lookups, and union operations on sets
I need data structure that is able to perform the following operations efficiently:
Insert a new element into a set.
Lookup element in set.
Compute the union of two sets.
Union operation should ...
0
votes
1
answer
124
views
Find a substring length $k$ with maximum occurrences
Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string.
We want $O(S)$ time complexity in an average case.
I think the solution lies in sophisticated ...
- 183
1
vote
2
answers
134
views
Order-preserving hashtable for integer tuples
There are integer tuples which index cells of a sparse multi-dimensional array (points inside n-parallelepiped), $n \le 32$.
The array itself is a BST with keys formed as $key = (...((a_0 * S_1 + a_1) ...
- 297
0
votes
0
answers
134
views
Slot implementation of LRU cache
Usually LRU cache is implemented with double linked list to fast remove oldest visited, push to front, and move from any place to front; also uses map to fast find element by key.
In 64bit systems ...
- 141
1
vote
3
answers
945
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
11
votes
2
answers
3k
views
Why is the Java HashMap load factor 0.75?
I can't understand why the Java HashMap load factor is 0.75. If I understand well, the formula for the load factor is n/m, where n is the number of key and m is the number of position in the hash ...
- 367
1
vote
2
answers
175
views
Iterable hash table
I'm currently working on implementing all the major data structures from C++ to better understand them and I arrived at the unordered_map, which should be a hash table implementation (it's actually ...
- 113
15
votes
4
answers
4k
views
Why are graphs represented as adjacency lists instead of adjacency sets?
In answering this question, I was looking for references (textbooks, papers, or implementations) which represent a graph using a set (e.g. hashtable) for the adjacent vertices, rather than a list. ...
- 7,248
1
vote
1
answer
296
views
A hash function for a 2D hash table with a scattering property?
I have an $n\times n$ matrix, and want to find a bijective function $h:[n^2] \to [n]\times [n]$ that can act as a hash function to map the numbers 1 through $n^2$ to row/column indices in my matrix. ...
- 11
0
votes
2
answers
346
views
How does a hash table not require all the keys to be looked through to find a value, i.e. O(N)?
Before starting, I want to say that I understand time complexity, and I understand how a hash table is considered O(1) vs an array having a time comp. of O(N) in terms of what you learn. What I don't ...
- 156
2
votes
2
answers
84
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 ...
- 17
0
votes
2
answers
134
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:
...
- 29
2
votes
0
answers
123
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 ...
- 21
2
votes
1
answer
102
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 ...
- 155
0
votes
0
answers
34
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
2
votes
1
answer
195
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, ...
- 55
0
votes
0
answers
208
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
-1
votes
1
answer
110
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 ...
user132812
1
vote
1
answer
251
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 ...
- 281
0
votes
0
answers
197
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
0
votes
3
answers
214
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 ...
1
vote
1
answer
162
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.
...
- 11
0
votes
2
answers
93
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 ...
- 173
3
votes
1
answer
116
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 ...
- 131
0
votes
1
answer
175
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 ...
- 111
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$.
...
1
vote
0
answers
54
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 ...
- 275
5
votes
2
answers
919
views
Why isn't an edge-map graph implementation used in practice?
Wikipedia states that three different graph implementations are used in practice:
Adjacency Lists
Adjacency Matrix
Incidence Matrix
While I was learning about these structures, another option ...
- 151
0
votes
2
answers
1k
views
My professor claims that inserting the same key into a hash table again will lead to a collision … – Is he really right?
My whole life I thought
a collision is a situation that occurs when two distinct pieces of data have the same hash value.
Everything looks a little bit different now: A few days ago we had to ...
1
vote
2
answers
6k
views
Determining an appropriate number of buckets for a hash function
I would like to select an appropriate number of buckets in my hash table for this scenario:
A hash table with collision resolved is required to hold about 10000 records. Each record is to be indexed ...
- 37
0
votes
1
answer
446
views
Calculate the average length of the linked lists in a hash table
I am learning hash tables, and I would like to know how to determine the average length of the linked lists.
For example: A hash table holds about 10,000 employee records. Each record is indexed by ...
- 37
1
vote
0
answers
176
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
...
- 11
1
vote
3
answers
274
views
Is the capacity of a hash table a constant value?
In this paper, page 4, it is said:
"...there is always a constant expected number of elements that map to the same slot"
Assume we have a set $S$ of $n$ values, and we want to insert them into a ...
- 111
7
votes
1
answer
306
views
Most space-efficient lossy dictionary?
Short version: What is the most space-efficient lossy dictionary (with given false positive and false negative rates)?
Long version: A lossy dictionary is a data structure $D$ that encodes a set $S$ ...
- 391
1
vote
0
answers
36
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 ...
- 11
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 ...
- 21
5
votes
4
answers
4k
views
Why use binary search trees when hash tables exist?
Hash tables perform lookup, insertion, and deletion in O(1) time (expected and amortized) while the different variants of binary search tree (BST) - treap, splay, AVL, red-black - offer at best O(log ...
- 581
1
vote
0
answers
210
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 ...
- 858
2
votes
0
answers
479
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
3
votes
0
answers
56
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
4
votes
2
answers
477
views
How to store $n$ numbers with space $O(n)$ bits and access time $O(1)$?
I want to store a subset of $\{1,2,\dots,n\}$ in a data structure such that the total space used is $O(n)$ bits and accessing a particular element can be done in $O(1)$ time. I have tried binary ...
- 1,205
2
votes
1
answer
359
views
"Hash" Probing?
While there are many types of probing in hash tables, such as linear probing,
quadratic probing, and more, I haven't encountered a so-called "hash-probing" (maybe this method which I describe below ...
- 563
4
votes
2
answers
6k
views
How exactly Hashing performs better than a Binary Search?
The time complexity of a Binary Search is O(log n) and Hashing is O(1) - so I've read. I have also read that Hashing outperforms Binary search when input is large, for example in millions. But I see ...
- 193
0
votes
1
answer
150
views
Limit on table size - perfect hashing
Let us define a "root universal family" as a family of hash function which for every two items $k_i,k_j$ the probability $P(h(k_i)=h(k_j)) \le \frac{1}{\sqrt m}$ where $m$ is the size of the table.
...
- 563
2
votes
2
answers
1k
views
Static hash tables
Assume one wants to store $1000$ distinct integers of $5$ digits in a hash table that is defined once for all (the intent is to hard-code it).
We have some freedom to change its behavior by changing ...
user16034
0
votes
0
answers
22
views
are these functions for open address hashing, proper?
I want to use these two functions in two hash-tables with open-addressing. Is there any problems with these functions? If yes, why they are not appropriate?
...
- 273
1
vote
1
answer
257
views
Hash table where items can fall into multiple buckets. What's the name of the data scrtucture? [closed]
I have a task to search through an array of items. I want to narrow the search down to some partitions. I thought of hash tables, but the difference in my case is that the "hash-function" is not ...
- 113
1
vote
2
answers
236
views
Hash functions producing uniform outputs
I've seen this question in a past exam paper, and I know that the answer given is (b), but I'm not sure why.
Which one of the following hash functions on integers will distribute keys
most ...
- 121
2
votes
1
answer
3k
views
Average number of collisions before successful insertion into hash table
I want to compute the average number of collisions before sucessfully adding an item into a hash table. Let $m$ be the size of a hash table $H$.
I was thinking that since it is a linear probing and ...
- 21