Stack Overflow
Stack Overflow

Questions tagged [linear-probing]

Questions about linear probing, the technique for resolving collisions in hash tables.

52 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
18
votes
1 answer

In Python Dictionaries, how does ( (j*5)+1 ) % 2**i cycle through all 2**i

I am researching how python implements dictionaries. One of the equations in the python dictionary implementation relates the pseudo random probing for an empty dictionary slot using the equation j = ((j*5) + 1) % 2**i which is explained here. I…
Fairly Nerdy
  • 863
  • 1
  • 8
  • 9
8
votes
3 answers

How does linear probing handle deletions without breaking lookups?

Here is my understanding of linear probing. For insertion: - We hash to a certain position. If that position already has a value, we linearly increment to the next position, until we encounter an empty position, then we insert there. That makes…
Radoradek
  • 93
  • 1
  • 5
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
3
votes
1 answer

Hash Table and Collision Calculation result

I know I don't have a working code/minimal, but I am not asking for more help in the code. I am going to try to summarize as much as possible. The test runs for 1000 times trying to insert 50 persons into the table. The trial randomly generates keys…
jacob
  • 31
  • 1
3
votes
0 answers

Remove function in linear probing hash table

I'm trying to write a proper remove function for my hash table using linear probing collision resolution method. I run a tester that removes several records from my hash table. At certain point, my find function cannot find an element to delete.…
Yochert
  • 85
  • 9
2
votes
1 answer

Unable to find out why my HashInsert and HashFind functions are wrong

The question is about coalesced hashing. It is for a school assignment, I have no one to ask. I managed to pass the sample case but unable to pass any of the hidden test cases. I am dying inside now. Please send help. I have attached the full code,…
soh junze
  • 33
  • 4
2
votes
1 answer

Inserting in hash table with linear probing

I was studying about hash tables on hackerearth , where I encounter this code for Implementing the Hash Table with Linear Probing. I have two doubts in this code:- 1) Why they declare hashTable of size 21 (and not of size 20) to hold maximum of 20…
amangupta
  • 87
  • 7
2
votes
2 answers

Linear probing huge sequences of keys with unequal hash

There is one thing about linear probing (hash tables) that is not intuitive to me. If I put key1 which hash results to array index 1. Then I put key2 -> array index 2. Then I put key3 -> again array index 1, this will go to array index 3. Then when…
John
  • 329
  • 1
  • 20
2
votes
1 answer

How to retrieve values from hashtable after resolving collision using linear probing?

I am trying to implement a hash program in go, I did insertion and resolved collisions using linear probing. When I'm trying to retrieve values back, i'm getting different values as I used linear probing to fix collisions. This is my program :…
codinggirl
  • 159
  • 1
  • 3
  • 8
2
votes
1 answer

Python MyHashTable class: search method with linear probing

I need help implementing a method for my "MyHashTable" class: def search(self, search_key): The method is supposed to use linear probing to handle collision resolution. If the search_key is in the hash table then the method returns the slot number…
Newbie
  • 378
  • 2
  • 12
  • 23
2
votes
1 answer

how to Compute the average probe length for success and failure - Linear probe (Hash Tables)

I'm doing an assignment for my Data Structures class. we were asked to to study linear probing with load factors of .1, .2 , .3, ...., and .9. The formula for testing is: The average probe length using linear probing is roughly Success--> ( 1 +…
fang_dejavu
  • 625
  • 2
  • 15
  • 22
1
vote
2 answers

Resizing Hash Map with Linear Probing

Problem Screenshotstrong text I am not sure why my answer is incorrect. Can anyone tell me whay I am doing wrong without giving my the answer? Thanks in advance. The problem states: Suppose we have the following HashMap using linear probing, where…
GoodHeartWilcox
  • 11
  • 2
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
2 3 4