CODEWITHSUNDEEP
c++data-structureshashhashtable
Riptyde4
Riptyde4

Reputation: 5460

What are the concerns with using a hash table with a low # of inputs?

What are the concerns with using a hash table with a low # of inputs? Are there better options in terms of what ADT to use with similar properties?

Upvotes: 3

Views: 99

Answers (2)

Tony Delroy
Tony Delroy

Reputation: 106096

For small numbers of entries, vectors tend to work very well - crucially, the objects are stored contiguously which tends to work best with memory caching - in modern systems that can be so beneficial it overwhelms costs of brute-force searching, and moving objects when erasing/sorting etc..

If you need to minimise moving/copying of the objects then a vector of (smart) pointers or linked list may suit.

Hash tables have to hash the element keys, while std::map and std::find in vector etc. do element comparisons. For example, high quality hashing of ints is more expensive than just comparing the values, but a one-off hash of a large matrix of values is then much faster to compare against other matrices than the maxtrix comparisons would be - particularly if they only differ in data well into the comparison.

Upvotes: 1

Elliott Frisch
Elliott Frisch

Reputation: 201437

Even if every operation in a hash table was O(1), it would still have a fairly high constant cost in terms of construction (e.g. constructing buckets). With only a few elements, many other ADTs (e.g. LinkedList) will perform better in practice (even if using those data structures has a O(n log n) or even a O(n2) complexity).

Upvotes: 2

Related Questions