both the list sort method and the sorted function provide stable sorts this means that if two elements are equal with respect to the comparison used in the sorttheir relative ordering in the original list (or other iterable objectis preserved in the final list hash tables if we put merge sort together with binary searchwe have nice way to search lists we use merge sort to preprocess the list in ( *log( )timeand then we use binary search to test whether elements are in the list in (log( )time if we search the list timesthe overall time complexity is ( *log(nk*log( )this is goodbut we can still askis logarithmic the best that we can do for search when we are willing to do some preprocessingwhen we introduced the type dict in we said that dictionaries use technique called hashing to do the lookup in time that is nearly independent of the size of the dictionary the basic idea behind hash table is simple we convert the key to an integerand then use that integer to index into listwhich can be done in constant time in principlevalues of any immutable type can be easily converted to an integer after allwe know that the internal representation of each object is sequence of bitsand any sequence of bits can be viewed as representing an integer for examplethe internal representation of 'abcis the string of bits which can be viewed as representation of the decimal integer , , of courseif we want to use the internal representation of strings as indices into listthe list is going to have to be pretty darn long what about situations where the keys are already integersimaginefor the momentthat we are implementing dictionary all of whose keys are social security numbers if we represented the dictionary by list with elements and used social security numbers to index into the listwe could do lookups in constant time of courseif the dictionary contained entries for only ten thousand ( peoplethis would waste quite lot of space which gets us to the subject of hash functions hash function maps large space of inputs ( all natural numbersto smaller space of outputs ( the natural numbers between and hash functions can be used to convert large space of keys to smaller space of integer indices since the space of possible outputs is smaller than the space of possible inputsa hash function is many-to-one mappingi multiple different inputs may be mapped to the same output when two inputs are mapped to the same outputit is called collision-- topic which we will to return shortly good hash function produces uniform distributioni every output in the range is equally probablewhich minimizes the probability of collisions united states social security number is nine-digit integer