figure hash table with linear probing with input as an examplesuppose the elements and are inserted into linear probing hash table of size the hash function is (xx mod the resulting hash table appears in figure if is inserted into the tablethe resulting table in figure will be over percent full because the table is so fulla new table is created the size of this table is because this is the first prime that is twice as large as the old table size the new hash function is then (xx mod the old table is scannedand elements and are inserted into the new table the resulting table appears in figure this entire operation is called rehashing this is obviously very expensive operationthe running time is ( )since there are elements to rehash and the table size is roughly nbut it is actually not all that badbecause it happens very infrequently in particularthere must have been / insertions prior to the last rehashso it essentially adds constant cost to each insertion this is why the new table is made twice as large as the old table if this data structure is part of the programthe effect is not noticeable on the other handif the hashing is performed as part of an interactive systemthen the unfortunate user whose insertion caused rehash could see slowdown figure hash table with linear probing after is inserted