Hash Tables или BST?

Question

В настоящее время у меня есть проблема, что я пытаюсь выяснить, но не уверен, что мои ответы верны.

У вас есть 1 миллион записей. В этих записях вам часто нужно искать по два критерия: идентификатор сотрудника и заработная плата (но не оба одновременно). У вас есть следующие ограничения:

• каждая запись является очень большой и из-за того, что вы можете держать только одну копию этих данных.

• Ваша программа должна быть достаточно быстрой. Простое сканирование всех элементов для каждого поиска будет слишком медленным.

Какая структура данных вы бы использовали?

Мой ответ?

Я хотел бы использовать хэш-таблицу, потому что в худшем случае будет O (+1000000) = O (1)

Как вы извлекаете записи при поиске по ID?

Как вы получите запись при поиске по зарплате?

Answer 1

Я ожидал бы многих проблем с столкновением для хэш-таблицы на основе зарплаты, но один для ID мог бы работать без столкновений довольно легко, используя небольшую криптографическую теорию. Кажется странным хотеть найти по зарплате, а не сортировать или получить некоторый диапазон, который можно было бы сделать намного проще на BST.

Недостаток этого заключается в том, что если вы хотите выполнить поиск по двум независимым объектам, вам придется поддерживать две структуры. К счастью, существуют указатели, поэтому вам не нужно хранить несколько копий. Лично я бы держать хэш-таблицу идентификаторов ссылок, затем BST зарплаты до ссылки, но если я ограничен одним типом данных я должен был бы сделать BST с узлами, как это:

Node { 
     int id; 
     Node idLessThan; 
     Node idGreaterThan; 

     int salary; 
     Node salaryLessThan; 
     Node salaryGreaterThan; 

     Data fileInfo; 
    } 

Создание по существу двух BST на одном наборе узлов.