O'Reilly logo

C++ Footprint and Performance Optimization by G. Bensley, R. Alexander

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Hash Tables

The previous paragraphs showed that arrays and linked lists each have their own strengths and weaknesses. The array provides fast access to its elements but is difficult to extend; the linked list is easy to extend but does not provide very fast access to its elements. For bases of data with a large number of elements, you of course want the best of both worlds. The hash table provides a means to bring this about. By combining the implementations of arrays and lists, a hash table that is set up well is both fast to access and easy to extend.

Hash tables come in as many shapes and sizes as implementers and designers can imagine, but the basic premise is graphically explained in Figure 11.4.

Figure 11.4. Hash table example.

The hash ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required