insert, remove and search operations can be implemented in O(1), as long as the load factor of the hash table is a constant strictly less than one. In more detail, the time for any particular operation (a search, insertion, or deletion) is proportional to the length of the contiguous block of occupied cells at which the operation starts. If all starting cells are equally likely, in a hash table with cells, then a maximal block of occupied cells will have probability of containing the starting location of a search, and will take time whenever it is the starting location. Therefore, the expected time for an operation can be calculated as the product of these two terms, , summed over all of the maximal blocks of contiguous cells in the table. A similar sum of squared block lengths gives the expected time bound for a random hash function (rather than for a random starting location into a specific state of the hash table), by summing over all the blocks that could exist (rather than the ones that actually exist in a given state of the table), and multiplying the term for each potential block by the probability that the block is actually occupied. That is, defining to be the event that there is a maximal contiguous block of occupied cells of length beginning at index , the expected time per operation is This formula can be simplified by replacing by a simpler necessary condition , the event that at least elements have hash values that lie within a block of cells of length . After this replacement, the value within the sum no longer depends on , and the factor cancels the terms of the outer summation. These simplifications lead to the bound But by the multiplicative form of the Chernoff bound, when the load factor is bounded away from one, the probability that a block of length contains at least hashed values is exponentially small as a function of , causing this sum to be bounded by a constant independent of . It is also possible to perform the same analysis using Stirling's approximation instead of the Chernoff bound to estimate the probability that a block contains exactly hashed values. In terms of the load factor , the expected time for a successful search is , and the expected time for an unsuccessful search (or the insertion of a new