How to Insert Keys in a Hashtable Using Different Collision Resolution Methods?

  • MHB
  • Thread starter evinda
  • Start date
In summary, the conversation discusses the insertion of three elements with keys $22, 15, 8$ in a hashtable of $7$ positions using different collision resolution methods. For the first case, coalesced chaining with the hash function $h(k)=k \mod m$ is used while for the second case, open addressing with primary hash function $h_1(x)=x \mod m$ and secondary hash function $h_2(x)=(x^2+1) \mod{7}$ is used. There is a discussion about the correct placement of the value $22$ in the second case, with the conclusion that it should be inserted in slot 1.
  • #1
evinda
Gold Member
MHB
3,836
0
Hello! (Smile)

There are given three elements with keys $22, 15, 8$. Insert them in the given order in a hashtable of $7$ positions given that as method of treatement of the collisions we use:

  • hashing that follows the method coalesced chaining with the hash fuction $h(k)=k \mod m$
  • ordered hashing with open addressing strategies with the primary hash function $h_1(x)=x \mod m$ and the secondary hash function $h_2(x)=(x^2+1) \mod{7}$

That's what I have tried:

For the first case:

View attachment 3894

For the second case:

View attachment 3895Could you tell me if it is right? (Thinking)
 

Attachments

  • hash1.png
    hash1.png
    1.2 KB · Views: 83
  • hash2.png
    hash2.png
    1.1 KB · Views: 85
Technology news on Phys.org
  • #2
Hey! (Wasntme)

I believe the first case is right. (Nod)

In the second case, the first value of 22 would still be inserted in slot 1 (using the primary hash function), so I think 22 should be there instead of 8. (Shake)
 
  • #3
Did you figure it out? (Wondering)
 
  • #4
I like Serena said:
Did you figure it out? (Wondering)

Yes, I did.. Thanks for your answer! (Smile)
 

FAQ: How to Insert Keys in a Hashtable Using Different Collision Resolution Methods?

What is a hashtable?

A hashtable is a data structure that stores a collection of key-value pairs. It is commonly used for fast lookup and retrieval of data based on a key.

How do you insert keys in a hashtable?

To insert a key-value pair in a hashtable, the key is first hashed to determine its index in the hashtable. The value is then stored at that index in the hashtable. If there is a collision, where two keys have the same hash, the value is either stored in a separate data structure or the existing value is overwritten.

What is the purpose of inserting keys in a hashtable?

The purpose of inserting keys in a hashtable is to efficiently store and retrieve data based on a key. This allows for fast lookup and retrieval of data without the need for iterating through a large dataset.

What is the time complexity of inserting keys in a hashtable?

The time complexity of inserting keys in a hashtable is typically O(1), meaning it is constant time regardless of the size of the hashtable. However, in the worst-case scenario where there are many collisions, the time complexity can be O(n), where n is the size of the hashtable.

Can duplicate keys be inserted in a hashtable?

In most implementations, duplicate keys are not allowed in a hashtable. This is because the key is used to determine the index where the value is stored, and having duplicate keys would result in overwriting the existing value. However, some implementations may allow for duplicate keys and handle collisions differently.

Similar threads

MHB Union of Disjoint Sets with at Most k Sets - Algorithm
Replies
2
Views
2K
How Does the Middle Square Method Hash Function Work?
Replies
9
Views
3K
Comp Sci Expected number of collisions for hashing with chaining
Replies
1
Views
2K
Avg. Num. Probes to Insert in Hash Table w/ Random Collision Res. Strat.
Replies
3
Views
3K
MHB Is ElGamal Signature Scheme Secure Without Using a Hash Function?
Replies
1
Views
2K
Difference between resonance in undamped vs damped mass-spring-dashpot
Replies
17
Views
1K
MHB How to Solve a Boundary Value Problem Using the Finite Difference Method?
Replies
1
Views
2K
MHB Ackermann's function is μ-recursive
Replies
11
Views
4K
I Optimization problem with multiple outputs: impossible?
Replies
6
Views
2K
LaTeX How to insert page number in footer in latex
Replies
2
Views
3K

Hot Threads

Recent Insights

Back
Top