Linked List
We create a linked list, then sequentially searches items. Linked list is simple, it is best for tiny symbol tables, but slow for large symbol tables.
sequential search
Ordered Array
We keep an ordered array all the time, then use binary search to find an item. Ordered array has optimal search and space, it also supports order-based operations. However, inserting a new item is slow.
Binary Search
Binary Search Tree
Ordered Array is too expensive to maintain. We maintain linked list based structure instead, but still use binary search to find an item. We build a binary search tree. Binary search tree is fast but still easy to build, it also supports order-based operations.
Binary Search
Balanced Binary Search Tree
Binary Search Tree is fast, but it can be slow if unlucky. We balance the binary search tree with colored links and rotation operations. Balanced BST has all the benefits of BST, while it is robust, always fast no matter what.
binary search
hash table
We keep our items in an un-ordered array, so maintaining the collection is not expensive. However, the search don't have to be expensive. We use a hash function to quickly find the array index for any item. The hash table is the fastest for search and insertion, but it doesn't support order based operations.
Hash
