operation list getitem setitem delitem len iter (no(no(no( (nhash table expected worst case ( (no( (no( (no( ( (no(ntable comparison of the running times of the methods of map realized by means of an unsorted list (as in section or hash table we let denote the number of items in the mapand we assume that the bucket array supporting the hash table is maintained such that its capacity is proportional to the number of items in the map in practicehash tables are among the most efficient means for implementing mapand it is essentially taken for granted by programmers that their core operations run in constant time python' dict class is implemented with hashingand the python interpreter relies on dictionaries to retrieve an object that is referenced by an identifier in given namespace (see sections and the basic command involves two calls to getitem in the dictionary for the local namespace to retrieve the values identified as and band call to setitem to store the result associated with name in that namespace in our own algorithm analysiswe simply presume that such dictionary operations run in constant timeindependent of the number of entries in the namespace (admittedlythe number of entries in typical namespace can almost surely be bounded by constant in academic paper [ ]researchers discuss the possibility of exploiting hash table' worst-case performance to cause denial-of-service (dosattack of internet technologies for many published algorithms that compute hash codesthey note that an attacker could precompute very large number of moderate-length strings that all hash to the identical -bit hash code (recall that by any of the hashing schemes we describeother than double hashingif two keys are mapped to the same hash codethey will be inseparable in the collision resolution in late another team of researchers demonstrated an implementation of just such an attack [ web servers allow series of key-value parameters to be embedded in url using syntax such as ?key =val &key =val &key =val typicallythose key-value pairs are immediately stored in map by the serverand limit is placed on the length and number of such parameters presuming that storage time in the map will be linear in the number of entries if all keys were to collidethat storage requires quadratic time (causing the server to perform an inordinate amount of workin spring of python developers distributed security patch that introduces randomization into the computation of hash codes for stringsmaking it less tractable to reverse engineer set of colliding strings