Why it is faster to search data using hash table?

Question

Why it is faster to search data using hash table? Because hash function converts string keys to integer keys, but integer numbers can be sorted making search faster?

For example I have associative array:

array 
(
   [str.key1] => value1
   [str.key2] => value2
   [str.key3] => value3
   [str.key4] => value4 
);

So to find value3 by using str.key3, it is necessary to run over all str.keys to compare, and therefore search has complexity O(n). But if I hash every str.key I receive numbers:

array
(
   [5] => value1
   [2] => value2
   [7] => value3
   [3] => value4    
);

then occur sorting:

array
(
   [2] => value1
   [3] => value2
   [5] => value3
   [7] => value4    
);

And therefore it is faster to find value. Do I understand correctly?

score 1 · Accepted Answer · edited May 23 '17 at 10:26

No. After convertion of string key to integer (hash value) hashtable implementations calculate a specific location (index) in a simple flat array, at which corresponding entry (key-value pair) is stored with the highest probability. While hashtable construction, if the calculated location is empty, the entry is inserted into, otherwise this situation is called collision and there are a plenty of strategies to resolve them.

Thus in typical cases hashtables perform one or very few (amortized constant O(1)) key comparsions per request. There is no sorting and anything like binary search.

However, if you think about PHP arrays (I guess), it is a flexible data structure and I'm not sure it behaves as pure hashtable in your case (or ever?). See How is the PHP array implemented on the C level? for more details.

Why it is faster to search data using hash table?

1 Answers1