Stack Overflow
Stack Overflow

Questions tagged [quadratic-probing]

Quadratic probing is an open addressing scheme in computer programming for resolving collisions in hash tables

Quadratic probing is an open addressing scheme in computer programming for resolving collisions in hash tables.

When an incoming data's hash value indicates it should be stored in an already-occupied slot or bucket, quadratic probing operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found.

Wiki: https://en.wikipedia.org/wiki/Quadratic_probing

33 questions
40
votes
3 answers

What is primary and secondary clustering in hash?

What is the difference between primary and secondary clustering in hash collision management?
Rickx
  • 591
  • 1
  • 5
  • 7
5
votes
3 answers

Quadratic probing over Linear probing

For a given hash value, the indices generated by linear probing are as follows: h, h+1, h+2, h+3, etc.. For a given hash value, the indices generated by quadratic probing are as follows: h, h+1, h+4, h+9, etc.. There will be cluster formed in…
hoder
  • 257
  • 1
  • 3
  • 14
4
votes
3 answers

How can quadratic probing fail to find a location on the next insertion while linear probing always finds one?

    I am doing a practice question from Data Structures Practice The Question    1.Linear Probing will (circle one):         i.gradually degrade in performance as more values are inserted        ii.May not find a location on the next…
committedandroider
  • 8,711
  • 14
  • 71
  • 126
4
votes
1 answer

how is this hash probing method quadratic?

I'm having a problem distinguishing between quadratic and linear probing algorithms. When I'm reading conceptual explanations, I see I^2 being repeatedly added to the last index tried. How is that the case here? What would linear probing change…
rcj
  • 631
  • 2
  • 11
  • 27
3
votes
2 answers

Moving from Linear Probing to Quadratic Probing (hash collisons)

My current implementation of an Hash Table is using Linear Probing and now I want to move to Quadratic Probing (and later to chaining and maybe double hashing too). I've read a few articles, tutorials, wikipedia, etc... But I still don't know…
rfgamaral
  • 16,546
  • 57
  • 163
  • 275
3
votes
0 answers

Linear probing vs. Quadratic probing

Under what load factors is linear probing just as good as quadratic probing? When does quadratic begin to win out?
user3466494
  • 33
  • 4
3
votes
2 answers

Reasons as to use Quadratic Probing for Hash table implementation

I have been learning about Hash Tables lately. There are a couple of examples of Collision Resolutions and one of them is Quadratic probing.Why would someone use quadratic probing? Does he know that the hash table will always be less than half full?…
user2278279
  • 65
  • 1
  • 7
2
votes
1 answer

Counting probes for quadratic probing

I'm trying to count the number of probes (or number of indices that must be passed over) when inserting keys into a list using quadratic probing I have def hash_quadratic(key, values): tablesize=len(values) index=key%tablesize probes=0 …
Sharw
  • 81
  • 2
  • 8
2
votes
1 answer

Quadratic probing doesn't hit all elements in prime numbered hash table

Say I have a hash table with 59 elements (each element value is an integer). Index 15 is blank and the rest of the table is full of data. Depending on the number I want to insert, the quadratic probing formula never hits element 15! Assume I want to…
kevmalek
  • 1,373
  • 2
  • 12
  • 13
2
votes
2 answers

Time complexity to fill hash table?

This is a homework question, but I think there's something missing from it. It asks: Provide a sequence of m keys to fill a hash table implemented with linear probing, such that the time to fill it is minimum. And then Provide another sequence of…
Heathcliff
  • 3,048
  • 4
  • 25
  • 44
1
vote
1 answer

How clustering in linear probing affect the search time

I understand the problem in linear probing that because of subsequent indexing there will be cluster of element. But I don't understand this statement The bigger the cluster gets, more it reduces the performance. How it reduces performance in…
Vishal Kamlapure
  • 590
  • 4
  • 16
1
vote
0 answers

Where are quadratic probing, double hashing, and cuckoo hashing actually used?

Where are quadratic probing, double hashing, and cuckoo hashing actually used? From what I can tell Java HashMap uses Separate Chaining, and the hash table underlying C++ unordered_map uses linear probing. Are there any commonly used languages /…
Zack
  • 6,232
  • 8
  • 38
  • 68
1
vote
2 answers

Why does this implementation of Quadratic Probing fail when not overriding values on collision?

My current implementation of Quadratic Probing overrides the item being stored at the current index with the new item when a collision occurs. I insert three Person objects which are stored by using their lastname as key. To test the collision…
user24028
  • 39
  • 1
  • 7
1
vote
1 answer

How to convert from linear probe in hash table to quadratic probe?

Hi I'm new to python and I have a hash table that uses linear probing to resolve collisions. I know linear probe is when N+1 ,N+2, N+3, but quadratic probe is when n+1, n+4, n+9 ... This is my set item function for linear probe def __setitem__(self,…
Sook Lim
  • 541
  • 6
  • 28
1
vote
1 answer

Proof the quadratic probing function

I would really appreciate if someone could help solve this problem. The question is: Consider the following hash function: h(k, i) = (h’(k) + (1/2) (i + i^2 )) mod m, where m = 2^p for some positive integer p. Prove or disprove that for any k, the…
Jamal Ahmed
  • 23
  • 4
1
2 3