Stack Exchange Network

Stack Exchange network consists of 174 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.

2
votes
1answer
55 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
67 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?
-1
votes
0answers
68 views

Hash Table Linked List Length

A hash table with chaining is required to hold 10000 records. Each record is indexed by the 2-character initials of the user's name, transformed into integers using the mapping: A=01, B=02,...,Z=26. ...
-1
votes
0answers
38 views

Average runtime for search in AVL tree

The Question: Suppose there is a hash table implemented with an array of AVL trees. Assume the hash function was very bad for our data, and half of the keys got mapped to one position/bucket, and the ...
0
votes
1answer
37 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
79 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
26 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
31 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
40 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
47 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
82 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
48 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
40 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
56 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
70 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
118 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
17 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
36 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
144 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
32 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
153 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
34 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
289 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
64 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
185 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
621 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
643 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
242 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
38 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
230 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
4k 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
39 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
69 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
472 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
74 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
50 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
392 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
488 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 ...
4
votes
2answers
208 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 ...
0
votes
0answers
252 views

Expected time of unsuccessful search: chaining and linear probing

We use a simple uniform hash function to insert 300 keys into two tables of size 1000, we use chaining at one table and linear probing at the other. We are given that the keys were mapped into 290 ...
2
votes
1answer
128 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 ...
1
vote
1answer
115 views

Probability that all indices divisible by 100 in a hash table with linear probing are occupied

I am trying to solve this question on Sedgewick's and Wayne's Algorithms book: Suppose that a linear-probing table of size 10^6 is half full, with occupied positions chosen at random. Estimate the ...
2
votes
2answers
863 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 ...
0
votes
1answer
75 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. ...
2
votes
2answers
379 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 ...