Как без перебора находятся данные в Dictionary?
Как без перебора в Dictionary происходит поиск данных без перебора O(1)? Я знаю, что есть некая хэш-таблица, где есть соответствие ключ (хэш) => значение.
| ключ | значение |
|---|---|
| a95c530a7af5f492a74499e70578d151 | значение 1 |
| a95c530a71f5f492a74499e70578d152 | значение 2 |
| a12c530a7af5f492a74499e70578d153 | значение 3 |
| ..... | ..... |
Но!!! Как без перебора он находит нужно ему значение по ключу??? Допустим я хочу найти значение по "a95c530a71f5f492a74499e70578d152". Как он без перебора это делает?
Ответы (1 шт):
Автор решения: SurfaceStack
→ Ссылка
Если кратко: хэш работает как индекс в массиве, а получение значения по определенному индексу (адресу) происходит за O(1).
Также есть несколько моментов:
- Хэш может быть равен очень большому числу (н-р 100500) и хранить столь большой массив смысла нет, поэтому в качестве индекса берется остаток от деления хэша на размер массива (
index = hash() % dict.Count()) - Могут происходить коллизии хэшей (совпадения), которые решаются так: хранением нескольких элементов с одинаковым индексом в связном списке внутри одной ячейки массива. При поиске перебираются элементы этого списка для нахождения точного совпадения ключа.