Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [hash-tables]

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

6
votes
1answer
77 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
23 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 ...
1
vote
0answers
20 views

What's the problem with deletion in FKS perfect hashing?

In FKS perfect hashing we construct two levels of tables. To lookup an element we first check in the first table which points us to the correct second level table that will contain the element if it ...
3
votes
1answer
46 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)) \...
3
votes
1answer
250 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 ...
0
votes
1answer
28 views

Hash table open addressing without dummy

If a hash table is using open addressing as the collision resolution strategy, then during deletion, we mark that slot as dummy. I understand the reason behind ...
1
vote
0answers
33 views

Can hash tables handle variable sized entries?

Let's say I have a hash table of 10 buckets where each bucket is of a number of bits. However each bucket doesn't have to have the same number of bits. Is it possible to achieve this? Or does it ...
0
votes
0answers
20 views

Dynamic perfect hashing, FKS Scheme

The FKS scheme uses a 2-level hash function. The first hash function is to partition the elements of the universe $\mathcal{U}$ into the dictionary $\mathcal{S}$. Obviously many elements of $\mathcal{...
0
votes
1answer
62 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 ...
2
votes
1answer
94 views

How does hashed inverted page table work?

I understand hash function and inverted page table, but then the book I read describes something called hashed inverted page table (use hash to accelerate the finding because IPT is large), with TLB ...
0
votes
2answers
113 views

Is it possible for a hash table's load factor to exceed 100%?

Using probing, is it possible for for a hash table's load factor to exceed 100%? I don't too much about Hash Tables. Is this possible?
0
votes
1answer
53 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 ...
0
votes
1answer
87 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 ...
1
vote
0answers
32 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 ...
1
vote
1answer
33 views

Most efficient way to check if key exist on a table

Imagine a person called Albert. Albert lives in Europe and would love to move to America. One day he got his wish come true. A person called Margareta gave him a key. The value of the key is the same ...
1
vote
1answer
48 views

How hash-table and hash-map are different?

In the context of CS, how the hash-table and hash-map are different? I was watching a part of "Algorithm with Swift" video in Udacity, and I discovered the terms "hash-table" and "hash-map" are ...
0
votes
1answer
66 views

Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time?

The Problem: I am currently analyzing a simple program that takes a file of length $n$, splits it into its individual words (seperated by white space) and adds those words to a set: ...
1
vote
1answer
69 views

When retrieving values from a hash table with linear probing, how do we know if the wanted value had not been shifted?

So, after a collision, a piece of information gets stored in the next bucket. When retrieving the value later with a key, how do we know it has not been shifted due to a collision and that we are in ...
1
vote
2answers
85 views

challenge: Closing hash, linear probing, probe length 1

The challenge says that there is a hash algorithm with a bug, the bug is given if it reaches the end of the array and did not find space to save the element, it discards it directly (that is, it does ...
2
votes
1answer
59 views

BST representation of Hash Tables

I'm reading this book Cracking Coding Interview. In this book author is speaking about BST representation of Hash Tables. I googled a lot for BST Representation of Hash Table. Code in C++ but didn't ...
0
votes
1answer
42 views

Does this excerpt from the linear probing Wikipedia page make an assumption?

Here is the excerpt from the linear probing page at Wikipedia. To search for a given key x, the cells of T are examined, beginning with the cell at index h(x) (where h is the hash function) and ...
2
votes
3answers
58 views

How does hash table search scales with number of keys?

Say, I have one of the standard implementations of a hash table: chaining or open addressing, and my hash key is a pair of strings. Instead of using the hash table with the pair as a key, I can use ...
1
vote
3answers
71 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 ...
5
votes
1answer
123 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$ ...
1
vote
0answers
20 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 ...
0
votes
0answers
18 views

Can I uses with same hashing-function for two hash-tables?

Given 2 hash tables , can I use only one hashing function for the two hash tables? I don't sure if the size of the hash-tables is necessarily affect about the hashing-function that this hash-table ...
3
votes
1answer
37 views

Bounds on probe lengths and number of rehashes with universal hashing

Say I have a family of hash functions that are weakly universal, i.e. the probability of two non-identical keys $x\neq y$ are mapped to the same hash-value is bounded by $k/m$ when I have $m$ bins and ...
-1
votes
2answers
200 views

Perfect (or almost perfect) Hash function for n bit integers with exactly k bits set

I have a a data set with 2598960 elements of of unsigned integers of (at most) 52-bit length. The data set has a property that exactly 5 bits set. This is only 1 data sets – I have similar data sets ...
0
votes
0answers
33 views

how many hash table sequences will produce a given table

given the following hash table with linear probing when the hash function is: $$k mod 10$$ how many different sequences will produce the given table? (starting from an empty table)
0
votes
0answers
164 views

Average number of comparisons for hash/rehash operations

I have the below problem, which I've already been given the answer to, I'm just trying to understand why the answer is the way it is. I've modified the language of the problem significantly so it ...
1
vote
1answer
35 views

Has the problem of finding the most profitable transactions given a set of discrete time series been well-studied?

Overview and Problem Description Suppose I have a set of N discrete time-series (represented as a map from time-interval-index to value/utility), and I would like to identify a sequence of actions in ...
0
votes
1answer
322 views

How to actually implement universal hashing?

I sort of get what it is, but I don't understand how its actually supposed to be used in algorithms. Suppose the hash function is $h_{ab}(x) = ((ax+b) \mod p ) \mod m$ where $a$ not equal to 0. If I ...
0
votes
0answers
70 views

is hash table a magic?

I have no cs background (algorithm and data structure), but need to find a data analysis related job since my major is math / statistics. However, (I am trying to avoid software engineering related ...
0
votes
0answers
235 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 ...
5
votes
4answers
811 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 ...
2
votes
0answers
824 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.
0
votes
1answer
263 views

Can Double Hashing return the same value 2 times?

$h(i,k)=(h^{}_{1}(k)+i * h^{}_{2}(k)) mod |T|$ as it defined in wikipedia I would like to know if it possible that Double Hashing return the same value for given $k$ when $i=1$ and $i=2$. Or from ...
1
vote
0answers
40 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 ...
2
votes
0answers
242 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 ...
0
votes
1answer
5k views

Explain Hashed page tables in operating system

I have a difficult time understanding hashed page tables used in virtual memory management. Here is picture of the slide that I am referring to: I understand that p is hashed and then the hash is ...
0
votes
0answers
7 views

Choosing array size for known number of keys in seperate chaining using mod method

If we know the number of keys that we are going to get ,how do we calculate the size of the array we will need to store our separate chains in the hashtable? All that using the mod hashfunction
3
votes
0answers
40 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, ...
1
vote
2answers
70 views

How to predict the length and offset of the sequence in and array?

I have an input string similar to ABCDEFGHIJK from which a series of sequences has been generated into an array as following: ...
1
vote
1answer
536 views

AVL Tree or HashTable for storing relatively big data?

I have been looking to implement a data structure for my project. I came across AVL tree and Hash Table. As I am a beginner so I'm in dilemma what data structure I use for large data. The main ...
1
vote
0answers
82 views

Bloom filters vs storing hashes as numbers

In competitive programming there is a trick for storing a set of strings(or objects really) to reduce memory - you only keep the hashes of the strings in a hash-table (usually as 32 or 64 bit integers)...
2
votes
2answers
36 views

Cuckoo filters for non powers-of-2

The Cuckoo filters paper (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) claims a 95% load factor, however it seems to make an implicit assumption that the table size is a power of 2, and ...
0
votes
0answers
18 views

Choice of hash table collision resolution depending on key and value type

Which kind of collision resolution for a hash table should I pick if I want to store a mapping from key of type uint64 (word) to value of type uin64 (word) from key of type string to value of type ...
1
vote
1answer
54 views

Print maximum frequency number in an array(with slight modification)

There is an integer array and 2 variables Q and M.The output required is the number which has the maximum frequency in the array, but the catch is that each number in the array can be increased/...
1
vote
1answer
424 views

Hash table: When is it suitable to use modulo power of 2?

I am implementing a hash table that may need to grow and shrink as the number of stored keys varies. I have a hashcode function that uniformly hashes keys to positive 32-bit integers. The table itself ...
3
votes
1answer
515 views

Knuth's proof of O(1) for linear probing

I'm currently reading Knuth's proof about O(1) number of probes in linear probing. I have a small question on the page 536 (Volume 3, 2nd Edition). Knuth says Let $f(M, N)$ be the number of hash ...