hash tables these formulas are graphed in figure average probe length unsuccessful successful load factor figure separate-chaining performance for an ordered listonly half the items must be examined in an unsuccessful searchso the time is the same as for successful search in separate chaining it' typical to use load factor of about (the number of data items equals the array sizesmaller load factors don' improve performance significantlybut the time for all operations increases linearly with load factorso going beyond or so is generally bad idea insertion if the lists are not orderedinsertion is always immediatein the sense that no comparisons are necessary the hash function must still be computedso let' call the insertion time if the lists are orderedthenas with an unsuccessful searchan average of half the items in each list must be examinedso the insertion time is loadfactor open addressing versus separate chaining if open addressing is to be useddouble hashing seems to be the preferred system by small margin over quadratic probing the exception is the situation in which plenty of memory is available and the data won' expand after the table is createdin this case linear probing is somewhat simpler to implement andif load factors below are usedcauses little performance penalty