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.

0
votes
0answers
15 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
50 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
550 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
23 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
50 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
83 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 ...
1
vote
0answers
22 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
49 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
263 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
73 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
34 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
49 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
68 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
199 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
280 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
67 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
101 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
37 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
64 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
78 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
119 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
90 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
99 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
54 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
62 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
76 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
134 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
41 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
289 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)
1
vote
1answer
36 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
364 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
77 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
273 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
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
996 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
302 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
252 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
6k 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
41 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
72 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
639 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
90 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 ...