Insert

[Jesse Sum]

Will we ever get the case where every slot is full and then we insert
something? and if we do, what should we do to handle it?

[cs240]

If you have read the assignment specification more carefully, you would
have found this case covered in it already: you can safely assume that the
table will never be completely full.

Vivian
CS240 Tutor

Post by Jesse Sum
Will we ever get the case where every slot is full and then we insert
something? and if we do, what should we do to handle it?

[Jesse Sum]

Post by cs240
If you have read the assignment specification more carefully, you would
have found this case covered in it already: you can safely assume that the
table will never be completely full.
Vivian
CS240 Tutor

Post by Jesse Sum
Will we ever get the case where every slot is full and then we insert
something? and if we do, what should we do to handle it?

Also another question,

If we have R = 3 and f = 1, d = 1, e = 1, and we insert another
number, do we use up the empty slot first or the deleted slot first?

[Alan Tang]

Post by Jesse Sum

Post by cs240
If you have read the assignment specification more carefully, you would
have found this case covered in it already: you can safely assume that the
table will never be completely full.
Vivian
CS240 Tutor

Post by Jesse Sum
Will we ever get the case where every slot is full and then we insert
something? and if we do, what should we do to handle it?

Also another question,
If we have R = 3 and f = 1, d = 1, e = 1, and we insert another
number, do we use up the empty slot first or the deleted slot first?

The assignment spec also says that all deleted slots precede empty
slots, so when you look for a non-filled slot, the first ones you would
find are deleted slots, if any.

[cs240]

Exactly. You should always insert it in the deleted cells if there are
any.

Vivian
CS240 Tutor

Post by Jesse Sum

Post by cs240
If you have read the assignment specification more carefully, you would
have found this case covered in it already: you can safely assume that the
table will never be completely full.
Vivian
CS240 Tutor

Post by Jesse Sum
Will we ever get the case where every slot is full and then we insert
something? and if we do, what should we do to handle it?

Also another question,
If we have R = 3 and f = 1, d = 1, e = 1, and we insert another
number, do we use up the empty slot first or the deleted slot first?

The assignment spec also says that all deleted slots precede empty slots, so
when you look for a non-filled slot, the first ones you would find are
deleted slots, if any.

[Su Zhang]

Post by Jesse Sum
and if we do, what should we do to handle it?

In that case we need to extend the table and rehash all the filled
slots.[1] Generally hash tables with open addressing perform good when
the load factor is around 70% or so, so it is common to do a full
rehashing whenever the table size exceeds this threshold. There exists
other techniques such as incremental rehashing, which resizes the table
gradually.

[1] Filled slots could be moved to new locations, if the hash function
being used is not consistent, i.e., the hash values computed change
after resizing the table.