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: 56
  • hash2.png
    hash2.png
    1.1 KB · Views: 56
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)
 

1. 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.

2. 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.

3. 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.

4. 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.

5. 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

Comp Sci Expected number of collisions for hashing with chaining
    • Engineering and Comp Sci Homework Help
Replies
1
Views
978
MHB Union of Disjoint Sets with at Most k Sets - Algorithm
    • Programming and Computer Science
Replies
2
Views
2K
Question about a Hash Function
    • Programming and Computer Science
Replies
9
Views
3K
Difference between resonance in undamped vs damped mass-spring-dashpot
    • Introductory Physics Homework Help
Replies
17
Views
390
Avg. Num. Probes to Insert in Hash Table w/ Random Collision Res. Strat.
    • General Math
Replies
3
Views
3K
I Optimization problem with multiple outputs: impossible?
    • General Math
Replies
6
Views
1K
I A short derivation of the relativistic forms of energy and momentum
    • Special and General Relativity
2
Replies
36
Views
3K
MHB How to Solve a Boundary Value Problem Using the Finite Difference Method?
    • General Math
Replies
1
Views
1K
Challenge Basic Math Challenge - September 2018
    • Math Proof Training and Practice
2
Replies
38
Views
6K
LaTeX How to insert page number in footer in latex
    • MATLAB, Maple, Mathematica, LaTeX
Replies
2
Views
3K

Hot Threads

Recent Insights

Back
Top