Мне нужно создать словарь, который имеет следующие черты:
- Никогда не меняется после создания
- поиск ключей должен быть без учета регистра
- поддерживает ""начинается с поиска ключа, где искомый префикс строки возвращает набор элементов, связанных с этим фрагментом
Идеальная карта хеш-функции с хэш-функцией без учета регистра удовлетворяла бы первым двум, ноне удовлетворяет последнему требованию.
Я думал о простом дереве, где каждый узел - это повышенный символ сохраненного ключа, и для нахождения соответствия потребовалось бы пройтись по дереву, выполнить бинарный поиск to-uppered символ из строки поиска.
+---+ +---+
| A | | B |
| | | |
+---+ +---------------------+
| | | |
+---+ +---+ +---+ +---+
| N | | A | | E | | U |
| | | | | | | |
+---+ +------+ +---+ +----+
| | | | |
+---+ +---+ +---+ +---+ +---+
| D | | D | | C | | D | | G |
+val| +val| | | +val| +val|
+---+ +---+ +---+ +---+ +---+
|
+---+
| K |
+val|
+---+
Это может показаться упрощенным и наивным решением.Есть что-нибудь лучше?