mapshash tablesand skip lists class mapbase(mutablemapping) """our own abstract base class that includes nonpublic item class "" nested item class class item """lightweight composite to store key-value pairs as map items ""slots _key _value def init (selfkv) self key self value def eq (selfother)compare items based on their keys return self key =other key def ne (selfother) return not (self =otheropposite of eq def lt (selfother)compare items based on their keys return self key other key code fragment extending the mutablemapping abstract base class to provide nonpublic item class for use in our various map implementations simple unsorted map implementation we demonstrate the use of the mapbase class with very simple concrete implementation of the map adt code fragment presents an unsortedtablemap class that relies on storing key-value pairs in arbitrary order within python list an empty table is initialized as self table within the constructor for our map when new key is entered into the mapvia line of the setitem methodwe create new instance of the nested item classwhich is inherited from our mapbase class this list-based map implementation is simplebut it is not particularly efficient each of the fundamental methodsgetitem setitem and delitem relies on for loop to scan the underlying list of items in search of matching key in best-case scenariosuch match may be found near the beginning of the listin which case the loop terminatesin the worst casethe entire list will be examined thereforeeach of these methods runs in (ntime on map with items