22 questions linked to/from (When) is hash table lookup O(1)?
528 views

Why isn't an edge-map graph implementation used in practice?

Wikipedia states that three different graph implementations are used in practice: Adjacency Lists Adjacency Matrix Incidence Matrix While I was learning about these structures, another option ...
36 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 ...
7k views

"For small values of n, O(n) can be treated as if it's O(1)"

I've heard several times that for sufficiently small values of n, O(n) can be thought about/treated as if it's O(1). Example: The motivation for doing so is based on the incorrect idea that O(1) is ...
3k views

Time complexity of Hash table lookup

Suppose I have a hash table which stores the some strings. Let the index/key of this hash table be the length of the string. what is the time complexity of checking if the string of length K exists in ...
1k views

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

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 assumption implies ...
1k views

What is the average search complexity of perfect hashing?

The lookup time in perfect hash-tables is $O(1)$ in the worst case. Does that simply mean that the average should be $\leq O(1)$?
124 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 ...
574 views

Best data structure for a queue with random reads?

Well, it's not exactly a queue if it allows for random reads. This question is about a data structure which behaves like a queue for insertions and a sorted dictionary for reads. Imagine an algorithm ...
2k views

Average number of collisions before successful insertion into hash table

I want to compute the average number of collisions before sucessfully adding an item into a hash table. Let $m$ be the size of a hash table $H$. I was thinking that since it is a linear probing and ...
3k views

How are hash tables O(1) taking into account hashing speed?

Hash tables are said to be amortized $\Theta(1)$ using say simple chaining and doubling at a certain capacity. However, this assumes the lengths of the elements are constant. Computing the hash of an ...
2k views

Can element uniqueness be solved in deterministic linear time?

Consider the following problem: Input: lists $X,Y$ of integers Goal: determine whether there exists an integer $x$ that is in both lists. Suppose both lists $X,Y$ are of size $n$. Is there a ...
385 views

Does my simple, static hash table have O(1) worst case lookup?

Will the following simple hash table construction algorithm be able to construct a static hash table in $O(n)$ expected time, and will the worst case access time be $O(1)$? If not, what are the ...
3k views

Hash table collisions: why use a linked list if we can use a hash set?

One way to deal with the problem of collisions for a hash table is to have a linked list for each bucket. But then the lookup time is no longer constant. Why not use a hash set instead of a linked ...
From the answers to (When) is hash table lookup O(1)?, I gather that hash tables have $O(1)$ worst-case behavior, at least amortized, when the data satisfies certain statistical conditions, and there ...