# Questions tagged [hash-tables]

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

261 questions
Filter by
Sorted by
Tagged with
1 vote
56 views

### Trouble Understanding Yao's "Basic Model" for Hashing

I am trying to understand the probing model proposed by Yao in the paper "Should Tables Be Sorted?". Yao suggests a "Basic Model" (in the section appropriately titled "Basic ...
34 views

### Find a substring length $k$ with maximum occurrences

Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string. We want $O(S)$ time complexity in an average case. I think the solution lies in sophisticated ...
42 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 ... 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 ...
1 vote
65 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. ...
31 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 ...
121 views

119 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 ...
1 vote
501 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 ...
139 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+...
1 vote
979 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 ...
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 ...
35 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 ...
1 vote
112 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 ...
1 vote
160 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> ...
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): ...
133 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$. ...
27 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 ...
74 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 ...
3k views

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. ...
147 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 ...
1 vote
176 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. ...
383 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. ...
283 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 ...
460 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 ...
1 vote
97 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 ...
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 ...
1 vote
412 views

148 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, ...
169 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 ...
196 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 ...
99 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 ... 5k 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 ...
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)$ ...