hash tables without linked lists separate chaining hashing has the disadvantage of using linked lists this could slow the algorithm down bit because of the time required to allocate new cells (especially in other languagesand essentially requires the implementation of second data structure an alternative to resolving collisions with linked lists is to try alternative cells until an empty cell is found more formallycells ( ) ( ) ( )are tried in successionwhere hi ( (hash(xf( )mod tablesizewith ( the functionfis the collision resolution strategy because all the data go inside the tablea bigger table is needed in such scheme than for separate chaining hashing generallythe load factor should be below for hash table that doesn' use separate chaining we call such tables probing hash tables we now look at three common collision resolution strategies linear probing in linear probingf is linear function of itypically (ii this amounts to trying cells sequentially (with wraparoundin search of an empty cell figure shows the result of inserting keys { into hash table using the same hash function as before and the collision resolution strategyf(ii the first collision occurs when is insertedit is put in the next available spotnamelyspot which is open the key collides with and then before an empty cell is found three away the collision for is handled in similar manner as long as the table is big enougha free cell can always be foundbut the time to do so can get quite large worseeven if the table is relatively emptyblocks of occupied cells start forming this effectknown as primary clusteringmeans that any key that hashes into the cluster will require several attempts to resolve the collisionand then it will add to the cluster although we will not perform the calculations hereit can be shown that the expected number of probes using linear probing is roughly ( /( ) for insertions and empty table after after after after after figure hash table with linear probingafter each insertion