advantages of using sorted array

[london-G]

Hello,

I am going to build a program using one data structure, I am trying to figure out what are the advantages of using a sorted array over using a hashtable with chaining?

Thanks

[deceptikon]

Realistically, a sorted array would be advantageous if you want to get a sorted listing of items, or do a ranged search or anything except an exact match. If all you're doing is searching onesie twosie, the hash table is conceptually faster. In practice the array and a binary search may be faster due to caching though.

[london-G]

I don't really understand, why would the sorted array be advantageous?

[deceptikon]

I don't really understand, why would the sorted array be advantageous?

Take a hash table, regardless of implementation, and print out all of the items in sorted order. You'll discover that it's not as simple as just traversing the table, and that's the first advanage that comes to mind for a sorted array, where it is as simple as just traversing the array.

[rubberman]

Depending upon the hash algorithm and the order of the table, collisions are common, so you have to traverse the chain to determine if you have a match if you are doing a lookup/comparison. With a sorted array, searches are nominally slower, but as deceptikon said, range searches and ordered output is a LOT simpler. I have written both types of collections in my past, and except for certain situations (random lookups, and low chance of collision), I have found that sorted arrays are preferable in the general case.

So, the rules are probably thus:

• if you are doing random lookups and don't need range searches, use a hash table.
• if you need to acces things in sorted order (range searches, etc), then a sorted array or some sort of B-Tree is preferable.