hash tables of courseif there are many items on the listsaccess time is reduced because access to specified item requires searching through an average of half the items on the list finding the initial cell takes fast ( timebut searching through list takes time proportional to mthe average number of items on the list this is (mtime thuswe don' want the lists to become too full load factor of as shown in the initial workshop appletis common with this load factorroughly one-third of the cells will be emptyone-third will hold one itemand one-third will hold two or more items in open addressingperformance degrades badly as the load factor increases above one-half or two-thirds in separate chaining the load factor can rise above without hurting performance very much this makes separate chaining more robust mechanismespecially when it' hard to predict in advance how much data will be placed in the hash table duplicates duplicates are allowed and may be generated in the fill process all items with the same key will be inserted in the same listso if you need to discover all of themyou must search the entire list in both successful and unsuccessful searches this lowers performance the find operation in the applet finds only the first of several duplicates deletion in separate chainingdeletion poses no special problems as it does in open addressing the algorithm hashes to the proper list and then deletes the item from the list because probes aren' usedit doesn' matter if the list at particular cell becomes empty we've included del button in the workshop applet to show how deletion works table size with separate chainingmaking the table size prime number is not as important as it is with quadratic probes and double hashing there are no probes in separate chainingso we don' need to worry that probe will go into an endless sequence because the step size divides evenly into the array size on the other handcertain kinds of key distributions can cause data to cluster when the array size is not prime number we'll have more to say about this problem when we discuss hash functions buckets another approach similar to separate chaining is to use an array at each location in the hash tableinstead of linked list such arrays are sometimes called buckets this approach is not as efficient as the linked list approachhoweverbecause of the