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
0 votes
0 answers
24 views

Effect of Insertion order on number of collisions in Double Hashing

How is the number of collisions affected by the order of insertion of elements in a hash table using double hashing? I've tried uing different hash function for double hashing with different set of ...
user avatar
0 votes
1 answer
34 views

Collisions in hash table - Is this table wrong?

I have the following hash table with hashcodes being quadratic numbers. Why do 0, 16, and 64 have different number of collisions when they map to the same number (line %16). Also how is it possible ...
Rubus's user avatar
  • 121
1 vote
0 answers
34 views

How to properly save Zobrist Keys?

In a project of mine, I want to represent states as efficiently as possible. Initially, I went ahead with a BitBoard representation and some clever tricks to speed up the evaluation of the game tree. ...
J. M. Arnold's user avatar
0 votes
2 answers
23 views

Chord Ring with limited table size of 3

In the normal case of a chord ring the big O notation of the look up is O(logn) because of long haul pointers of the Finger Table (or Routing Table). In this question what if the Finger Table has a ...
DarkArtistry's user avatar
0 votes
1 answer
114 views

Simple Uniform hashing with chances of no collision

I know that if I have $n$ different values in an array of size $m$ (where $m>n$) under simple uniform hashing, the average probability of the total number of collisions is: $$\sum_{i=1}^{n-1}\frac{...
Mike's user avatar
  • 33
1 vote
2 answers
93 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) ...
Andrey Godyaev's user avatar
0 votes
0 answers
64 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 ...
Saku's user avatar
  • 141
1 vote
2 answers
143 views

How to deal with a very big hash table?

I'm building an implementation of the dynamo paper, yottastore. Given a key, I need to find which NVMe block stores the data. To do that I hash the key to find the shard where I have an in memory ...
Mascarpone's user avatar
0 votes
1 answer
54 views

Universal family of hash functions — dependent on table size?

Given the following family of hash functions: $$ \mathbb{H} = \{h_c(x) = (12x + c) \bmod m \mid c \in \mathbb{N} \}, $$ where $m$ is the key size. Prove that $\mathbb{H}$ is not a universal ...
blox2212's user avatar
0 votes
1 answer
101 views

Is there a hash-map implementation optimized to favor key lookups based on frequency (if key is referenced the most then it is searched first)?

I have started to play around with HTTP3 which relies on QUIC for transport. I have noticed that I very often have a finite number of Web Transport sessions stream data continuously along side burst-y ...
Liam Kelly's user avatar
1 vote
3 answers
322 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 ...
Bam's user avatar
  • 11
0 votes
1 answer
115 views

Consistent Hashing Algorithm Without Distribution / Load Balancing

I need some help finding or creating a consistent hashing algorithm with the following properties: Given N buckets, only distributes keys to bucket N. When number of buckets are increased from N to N+...
scroobius's user avatar
1 vote
2 answers
637 views

Averege time complexity of open addressing

I get that it depends from the number of probes, so by how many times the hash code has to be recalculeted, and that in the best case there will only be one computation of the hash code and the ...
Spyromancer's user avatar
11 votes
2 answers
2k 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 ...
Bender's user avatar
  • 347
0 votes
1 answer
29 views

Confused about the appropriate slot in linear probing

The following paragraph is from the book CLRS: Given an ordinary hash function $h' : U \rightarrow \{0, 1, ..., m - 1\}$, which we refer to as an auxiliary hash function, the method of linear probing ...
Emad's user avatar
  • 411
1 vote
2 answers
94 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 ...
Petok Lorand's user avatar
1 vote
2 answers
134 views

Hash maps vs extending structs / classes

A hash map that maps keys of type $K$ into values of type $V$, is essentially equivalent to "extending" this type $K$ to also contain an Option<V> ...
nir shahar's user avatar
  • 11.4k
0 votes
0 answers
23 views

Unusual approach to tabulation algorithm

Consider simple tabulation algorithm firstly for Fibonacci numbers. We will use the dictionary as a cache (and Python as example PL): ...
lesobrod's user avatar
  • 111
2 votes
1 answer
110 views

Analysis of a calculation of expected number of collisions in hashing

For a formal problem statement, I quote from the text Introduction to Algorithms by Cormen et. al Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. ...
Abhishek Ghosh's user avatar
0 votes
0 answers
26 views

worst case time for adding values to a hash table

A certain hash table uses external chaining, and is resized each time its load factor exceeds 3. Also, if an addition does not cause the load factor to exceed 3, but does cause some bucket to exceed 6 ...
daniel's user avatar
  • 121
0 votes
0 answers
55 views

Does DHT (Distributed Hash Table) allow to list ALL (not only nearest) nodes?

As I know any local DHT keeps only some of nodes - if the network is small/very small then all nodes, otherwise only some of them (nearest?). So, when I checked different Golang implementations of DHT ...
RandomB's user avatar
  • 101
13 votes
4 answers
2k 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. ...
Caleb Stanford's user avatar
0 votes
3 answers
132 views

How do i delete one single unequal element from an array of equal elements without using hashing?

The rules of the question state that: Only one element is different. Rest are all same. Array A size is 8. I need to find the different element and remove it (Hashing cannot be used). I have not ...
Swarnava Chandra Bose's user avatar
1 vote
1 answer
149 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. ...
RJL's user avatar
  • 11
0 votes
1 answer
288 views

Build a priority queue using dictionary

QUESTION: Can we Implementing priority queue with hash table please? As I understand, dictionary/hash table does not have sorting mechanism inside. It adds pairs of $<key,value>$ to hash table. ...
Avv's user avatar
  • 493
0 votes
2 answers
210 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 ...
Jake Jackson's user avatar
0 votes
1 answer
396 views

hash-tables - Expected-time for an unsuccessful search

The following question is from MIT-OCW 6.006, Spring-2008, Problem-Set 2, Q-3.c. Suppose you have a hash table where the load-factor $\alpha$ is related to the number $n$ of elements in the table by ...
x.projekt's user avatar
  • 101
1 vote
1 answer
93 views

How does the Go language implements maps?

To what extent is the MAP data type implementation language dependant??? If we know that C++ implements maps as Red Black Trees, unordered maps as hash tables, How C++ and alike maps are actually ...
ShAr's user avatar
  • 138
0 votes
1 answer
38 views

The interpretation of expected time bound for searches in a hash table

As CLRS book,page 260 stated, Thus, the total time required for a successful search is $\Theta{\left(2+\alpha/2-\alpha/2n\right)}=\Theta{(1+\alpha)}$ I wouldn't have any problem if the author says ...
absuu's user avatar
  • 103
1 vote
1 answer
262 views

If $(h_2(k),m) = 1$ then $h_1(k)+ih_2(k) \bmod{m}$ is a permutation of $0,\ldots,m-1$

The following question appears in Introduction to Algorithms (CLRS): Suppose that we use double hashing to resolve collisions; that is, we use the hash function $ h(k, i) = (h_1(k) + ih_2(k)) \bmod{m}...
Avv's user avatar
  • 493
0 votes
0 answers
55 views

Confused about a corollary in MIT.Introduction.to.Algorithms(CLRS), seek help

Desc' I was reading CLRS Book's chapter 11 Hash Tables, and encountering some problems. There is an corollary in CLRS book, in Page 275 (quoted on the bottom of post), which discussed the expected ...
absuu's user avatar
  • 103
0 votes
1 answer
176 views

Detecting and correcting collisions in (Zorbist) hashing to avoid errors in transposition table

Context Say I have a transposition table that uses keys produced by (e.g. Zorbist) hashing game positions. The table has a finite recycled memory (key % p is the <...
Vepir's user avatar
  • 105
1 vote
1 answer
56 views

Number of unique values in array in $\theta(n)$ average expected time

My idea is to initialize a hash table (with chaining) with $n$ cells, having load factor $\alpha = 1$ hence having $\theta(1)$ expected number of values in each cell in the hash table, then go cell by ...
user183748292's user avatar
0 votes
0 answers
55 views

The Most efficient algorithm for a program that returns true if the two strings only differ by one character

We have a list of strings with the same length. Each string only contains a, b and c.(For instance : aabcc) The program gets a string and returns true if the two strings(input and the list of strings) ...
emma funkhouser's user avatar
2 votes
2 answers
75 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 ...
Yukti Kumari's user avatar
0 votes
2 answers
117 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: ...
Omri Braha's user avatar
2 votes
0 answers
73 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 ...
user136515's user avatar
2 votes
1 answer
926 views

Time complexity of checking whether a string exists in a HashSet

From what I know hash sets generally have complexity of $O(1)$ (unless the hash function is bad, but let's just ignore that for this question). However, sets need to either read the full data so as to ...
asharpharp's user avatar
2 votes
1 answer
67 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 ...
snatchysquid's user avatar
0 votes
0 answers
27 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 ...
Trajan's user avatar
  • 143
0 votes
0 answers
94 views

Bloom filter variant(using only half of it)

A Bloom filter is an array $B[1..m]$ of bits, together with a collection of $k$ independent ideal random hash functions $h_1,h_2,...,h_k$. To insert an item $x$ into a Bloom filter, we set $B[h_i(x)] ←...
kings's user avatar
  • 141
2 votes
1 answer
131 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, ...
Mika2019's user avatar
0 votes
0 answers
156 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 ...
SamuraiJack's user avatar
0 votes
0 answers
97 views

Algorithm question: Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1

Algorithm question: Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: Input: [0,1] Output: 2 Explanation: [0, 1] is the longest ...
ayuken's user avatar
  • 1
-1 votes
1 answer
95 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 ...
user avatar
2 votes
2 answers
4k views

Number of probes in a successful search in open address hashing

Given an open-address hash table with $\alpha$ < 1, the expected number of probes in a successful search is at most $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$ I read this in a book and the proof ...
Titan's user avatar
  • 59
1 vote
1 answer
56 views

How 'Avalanche Effect' got its name?

I wonder how or why Avalanche Effect got its name. Avalanche Effect is a desirable property of cryptographic algorithms, wherein if an input is changed slightly (...
Midhunraj R Pillai's user avatar
1 vote
1 answer
210 views

Counting letter frequency in array in O(1) with hash function

I want to calculate the frequency of each character in an array. (e.g ['a', 'b', 'o', 'p'] There are several ways to do this: A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ ...
HelloWorld's user avatar
4 votes
1 answer
1k views

Why do we need hashed page tables for Paging in Operating Systems?

I understand that we might need hierarchical paging to handle page tables with sizes greater than the size of one frame, but what is the use of Hashed Page tables then? I would understand if we were ...
Soumya Sen's user avatar
1 vote
1 answer
48 views

Asymptotic growth of a series

How we can prove that: $$ \sum_{k=1}^{c \log n-1}\:k\cdot \left(\frac{1}{2}\right)^{\frac{k}{3}}\in O\left(1\right) \quad \mbox{?} $$
user avatar

1
2 3 4 5 6