При рассмотрении реализаций поиска нашёл интересную таблицу с характеристиками структур, применяемых для реализации символьных таблиц. Причём рассматриваются худшие и средние случаи.
| худший случай | средний случай | |||||
| вставка | поиск | выбор | вставка | попадание при поиске | промах при поиске | |
| массив, индексированный по ключам | 1 | 1 | M | 1 | 1 | 1 |
| упорядоченный массив | N | N | 1 | N/2 | N/2 | N/2 |
| упорядоченный связный cписок | N | N | N | N/2 | N/2 | N/2 |
| неупорядоченный массив | 1 | N | NlnN | 1 | N/2 | N |
| неупорядоченный связный список | 1 | N | NlnN | 1 | N/2 | N |
| бинарный поиск | N | lnN | 1 | N/2 | lnN | lnN |
| дерево бинарного поиска | N | N | N | lnN | lnN | lnN |
| дерево типа "красное-черное" | lnN | lnN | lnN | lnN | lnN | lnN |
| рандомизованное дерево | N | N | N | lnN | lnN | lnN |
| хеширование | 1 | N | NlnN | 1 | 1 | 1 |
