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 only finds 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 chaining it' not so important to make the table size prime numberas it is with quadratic probes and double hashing there are no probes in separate chainingso there' no 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 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 called buckets this approach is not as efficient as the linked list approachhoweverbecause of the problem of choosing the size of the buckets if they're too small they may overflowand if they're too large they waste memory linked listswhich allocate memory dynamicallydon' have this problem java code for separate chaining the hashchain java program includes sortedlist class and an associated link class sorted lists don' speed up successful searchbut they do cut the time of an unsuccessful search in half (as soon as an item larger than the search key is reachedwhich on average is half the items in listthe search is declared failure deletion times are also cut in halfhoweverinsertion times are lengthenedbecause the new item can' just be inserted at the beginning of the listits proper place in the ordered list must be located before it' inserted if the lists are shortthe increase in insertion times may not be important in situations where many unsuccessful searches are anticipatedit may be worthwhile to use the slightly more complicated sorted listrather than an unsorted list howeveran unsorted list is preferred if insertion speed is more important the hashchain java programshown in listing begins by constructing hash table with table size and number of items entered by the user the user can then insertfindand delete itemsand display the list for the entire hash table to be viewed on the screenthe size of the table must be no greater than or so listing the hashchain java program