hash tables in this sectionwe introduce one of the most practical data structures for implementing mapand the one that is used by python' own implementation of the dict class this structure is known as hash table intuitivelya map supports the abstraction of using keys as indices with syntax such as [kas mental warm-upconsider restricted setting in which map with items uses keys that are known to be integers in range from to for some > in this casewe can represent the map using lookup table of length nas diagrammed in figure figure lookup table with length for map containing items ( , )( , )( , )and ( ,qin this representationwe store the value associated with key at index of the table (presuming that we have distinct way to represent an empty slotbasic map operations of getitem setitem and delitem can be implemented in ( worst-case time there are two challenges in extending this framework to the more general setting of map firstwe may not wish to devote an array of length if it is the case that secondwe do not in general require that map' keys be integers the novel concept for hash table is the use of hash function to map general keys to corresponding indices in table ideallykeys will be well distributed in the range from to by hash functionbut in practice there may be two or more distinct keys that get mapped to the same index as resultwe will conceptualize our table as bucket arrayas shown in figure in which each bucket may manage collection of items that are sent to specific index by the hash function (to save spacean empty bucket may be replaced by none ( , ( , ( , ( , ( , ( , ( , figure bucket array of capacity with items ( , )( , )( , )( , )( , )( , )and ( , )using simple hash function