mechanisms for defining abstract data types but notice thatas opposed to specification in plain englishsuch as the abovea definition of an interface is only partial specification of an abstract data typebecause it does not explain what the methods are supposed to doit only explains how they are called implementations of the table data structure there are three key approaches for implementing the table data structure the first two we have studied alreadyand the third is the topic of this implementation via sorted arrays let us assume that we want to implement the table data structure using sorted array whether it is full or empty can easily be determined in constant time if we have variable for the size then to insert an element we first have to find its proper positionwhich will take on average the same time as finding an element to find an element (which is necessary for all other operations apart from traversal)we can use binary search as described in in section so this takes (log nthis is also the complexity for retrieval and update howeverif we wish to delete or insert an itemwe will have to shift what is 'to the rightof the location in question by oneeither to the left (for deletionor to the right (for insertionthis will take on average / stepsso these operations have (ncomplexity traversal in order is simpleand is of (ncomplexity as well implementation via binary search trees possible alternative implementation would involve using binary search trees howeverwe know already that in the worst casethe tree can be very deep and narrowand that these trees will have linear complexity when it comes to looking up an entry we have seen that there is variant of binary search trees which keeps the worst case the same as the average casethe so-called self-balancing binary search treebut that is more complicated to both understand and program for those treesinsertiondeletionsearchretrieval and updatecan all be done with time complexity (log )and traversal has (ncomplexity implementation via hash tables the idea here is thatat the expense of using more space than strictly neededwe can speed up the table operations the remainder of this will describe how this is doneand what the various computational costs are hash tables the underlying idea of hash table is very simpleand quite appealingassume thatgiven keythere was way of jumping straight to the entry for that key then we would never have to search at allwe could just go thereof coursewe still have to work out way for that to be achieved assume that we have an array data to hold our entries now if we had function (kthat maps each key to the index (an integerwhere the associated entry will be storedthen we could just look up data[ ( )to find the entry with the key it would be easiest if we could just make the data array big enough to hold all the keys that might appear for exampleif we knew that the keys were the numbers from to then we could just create an array of size and store the entry with key in data[ ]