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
1
vote
0answers
12 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
22 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(...
1
vote
2answers
64 views

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

My question: 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 ...
0
votes
0answers
30 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
0answers
17 views

Time complexity of website access analysis using Hash Tables

I would like to calculate the time complexity of an algorithm which returns the number of accesses of a website and the number of different users who entered. Each user is represented by a unique ...
0
votes
1answer
77 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
572 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
36 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
52 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
85 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
25 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
54 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
274 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
107 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
35 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
73 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
73 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
291 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
419 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
2answers
91 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
108 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
45 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
36 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
71 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 ...
1
vote
1answer
80 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
166 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
91 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
159 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
59 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
64 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
81 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 ...
6
votes
1answer
154 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
21 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 ...
3
votes
1answer
51 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
357 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
34 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)
1
vote
1answer
43 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
427 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
83 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
312 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 ...
4
votes
4answers
1k 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
1k 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
335 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
41 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
275 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 ...
1
vote
1answer
7k 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
8 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
42 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
79 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
724 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 ...