Linear hashing complexity

I was going through Linear hashing article on Wiki. One line puzzled me and here it is: " The cost of hash table expansion is spread out across each hash table insertion operation, as opposed to being incurred all at once.[2]"

In case of linear hashing if hash value of item to be inserted is smaller than split variable then a new node (or bucket) is created and value inserted in that.And according to above line( the time complexity is measured over each "insertion operation" which if compared to "dynamic array" implementation where we do amortized analysis , the insertion in Linear hashi开发者_如何学运维ng must take O(n) time. Please correct me if i am wrong. One more thing: Second line on wiki says "Linear hashing is therefore well suited for interactive applications."

Can i compare B+ tree with Linear hashing in "interactive cases" (since both are extendible searching techniques) ?

---

From what I know O(n) is the worst time complexity but in most cases a hash table would return results in constant time which is O(1). As oppose to B+ tree where one must traverse the tree hash tables work on hashing function where the result of hashing function points to the address of a stored value. In the worst case if all the keys have same hashing results then the time complexity might become O(n) because all the results will be stored in one bucket.

According to wikipedia b plus tree has following time complexities.

Inserting a record requires O(logbn) operations Finding a record requires O(logbn) operations

---

An LH implementation can guarantee strictly bounded insertion time. There's no reason for the split location and the key-hash location to be related, if collisions are handled by overflows. The trick is to link the creation of overflow slots to the split operation.

For example, if every Nth slot is always reserved to be an overflow slot, then you need to do at most N-1 splits to create a new overflow slot. In practice it's fewer than (N-1)/2 splits, because splitting one slot may free up an overflow slot.

http://goo.gl/6dbuH for a description, https://github.com/mischasan/hx for source code.