Как хеш-таблица работает? Это быстрее, чем “ВЫБОР * от..”
В сообщении указывалось, что это связано с ключами (секретами) уровня хоста в вашей функции.
Поэтому, хотя у меня нет чёткого решения этой проблемы (поскольку я никогда не сталкивался с этой проблемой), я бы посоветовал вам проверить папку host.json в D:\home\data\Functions\secrets и посмотреть, есть ли там что-нибудь необычное, например, есть более 10 клавиш - как указано в сообщении об ошибке.
5 ответов
Простая хеш-таблица работает путем хранения объектов в нескольких списках, вместо всего один. Это использует очень быстрое и повторяемое (т.е. неслучайный) метод для выбора который список сохранить каждый объект на. Таким образом, когда пора найти объект снова, это повторяет, что метод для обнаружения, какой список заглянуть, и затем делает нормальный (медленный) линейный поиск в том списке.
Путем деления объектов на 17 списков, поиск становится в 17 раз быстрее, который является хорошим улучшением.
Хотя, конечно, это только верно, если списки являются примерно той же длиной, таким образом, важно выбрать хороший метод распределения объектов между списками.
В Вашей таблице в качестве примера первый столбец является ключом, вещью, мы должны найти объект. И позволяет, предполагают, что мы будем вести 17 списков. Для вставки чего-то мы выполняем операцию на ключе, названном, хешируя. Это просто превращает ключ в число. Это не возвращает случайное число, потому что это должно всегда возвращать то же число для того же ключа. Но в то же время числа должны быть "распространены" широко.
Затем мы берем получающееся число и используем модуль для уменьшения его вниз к размеру нашего списка:
Hash(key) % 17
Это все происходит чрезвычайно быстро. Наши списки находятся в массиве, таким образом:
_lists[Hash(key % 17)].Add(record);
И затем позже, для нахождения объекта с помощью того ключа:
Record found = _lists[Hash(key % 17)].Find(key);
Обратите внимание, что каждый список может просто быть любым контейнерным типом или классом связанного списка, который Вы пишете вручную. Когда мы выполняем a Find в том списке это работает медленный путь (исследуйте ключ каждой записи).
Не волнуйтесь о том, что MySQL делает внутренне для определения местоположения записей быстро. Задание базы данных состоит в том, чтобы сделать такую вещь для Вас. Просто выполненный a SELECT [columns] FROM table WHERE [condition]; запросите и позвольте базе данных генерировать план запросов для Вас. Обратите внимание, что Вы не хотите использовать SELECT *, с тех пор, если Вы когда-нибудь добавляете столбец к таблице, которая повредит все Ваши старые запросы, которые полагались на то, чтобы там быть определенным числом столбцов в определенном порядке.
Если Вы действительно хотите знать то, что продолжается под капотом (хорошо знать, но сделать не, реализуют его сами: это - цель базы данных!), необходимо знать то, что индексы и как они работают. Если таблица не имеет никакого индекса на столбцах, вовлеченных в оператор Where, то, как Вы говорите, база данных должна будет перерыть каждую строку в таблице для нахождения тех соответствующих условию. Но если будет индекс, то база данных будет искать индекс для нахождения точного местоположения строк, которые Вы хотите и переходите непосредственно им. Индексы обычно реализуются как B +-trees, тип дерева поиска, которое использует очень немного сравнений для определения местоположения определенного элемента. Поиск B-дерева для определенного ключа очень быстр. MySQL также способен к использованию индексов хеша, но они имеют тенденцию быть медленнее для использования базы данных. Индексы хеша обычно только работают хорошо на длинных ключах (символьные строки особенно), так как они уменьшают размер ключа к фиксированному размеру хэша. Для типов данных как целые числа и вещественные числа, которые имеют четко определенное упорядочивание и фиксированную длину, легкий searchability B-дерева обычно обеспечивает лучшую производительность.
Вы хотели бы смотреть на главы в руководстве MySQL и руководстве PostgreSQL по индексации.
http://en.wikipedia.org/wiki/Hash_table
Хеш-таблицы могут использоваться в качестве структур данных в оперативной памяти. Хеш-таблицы могут также быть приняты для использования с персистентными структурами данных; индексы базы данных иногда используют находящиеся на диске структуры данных на основе хеш-таблиц, хотя сбалансированные деревья более популярны.
Я предполагаю, что Вы могли использовать хеш-функцию для получения идентификатора, из которого Вы хотите выбрать. Как
ВЫБЕРИТЕ * таблица FROM ГДЕ значение = hash_fn (whatever_input_you_build_your_hash_value_from)
Затем Вы не должны знать идентификатор строки, которую Вы хотите выбрать и можете сделать точный запрос. Так как Вы знаете, что строка будет всегда иметь тот же идентификатор из-за входа, Вы создаете форму значения хэш-функции, и можно всегда воссоздавать этот идентификатор через хеш-функцию.
Однако это не всегда верно в зависимости от размера таблицы и максимального количества значений хэш-функции (у Вас часто есть "X ультрасовременных размеров хеш-таблицы" где-нибудь в Вашем хеше). Для заботы об этом, у Вас должна быть детерминированная стратегия, Вы используете каждый раз, когда Вы получаете два значения с тем же идентификатором. Вы должны проверить Википедию на большее количество информации об этой стратегии, ее названной обработке коллизии и должны быть упомянуты в той же статье как хеш-таблицы.
MySQL, вероятно, использует хеш-таблицы где-нибудь из-за функции O(1) norheim.se упомянутый.
Хеш-таблицы являются замечательными для определения местоположения записей в O (1) стоимость, где ключ (который используется для хеширования) уже известен. Они находятся в широком употреблении и в библиотеках набора и в механизмах базы данных. Необходимо смочь найти много информации о них в Интернете. Почему Вы не запускаете с Википедии, или просто Google ищет?
Я не знаю детали mysql. Если бы существует структура, там названная "хеш-таблицей", которая, вероятно, была бы своего рода таблицей, которая использует хеширование для определения местоположения ключей. Я уверен, что кто-то еще скажет Вам об этом.=)
Править: (в ответ на комментарий)
Хорошо. Я попытаюсь сделать чрезвычайно упрощенное объяснение: хеш-таблица является таблицей, где записи расположены на основе функции ключа. Например, скажите, что Вы хотите сохранить информацию о ряде людей. При хранении его в плоскости неотсортированный массив необходимо было бы выполнить итерации по элементам в последовательности для нахождения записи, которую Вы ищете. В среднем этому будут нужны сравнения N/2.
Если, вместо этого, Вы помещаете все записи в индексы на основе первого символа имени людей. (A=0, B=1, C=2 и т.д.), Вы сразу сможете найти корректную запись, пока Вы знаете имя. Это - основная идея. Вы, вероятно, понимаете, что некоторая специальная обработка (перефразирование или разрешение списков записей) требуется для поддержки многократных въездов, имеющих ту же первую букву. Если у Вас есть хорошо определенная размеры хеш-таблица, необходимо смочь стать прямыми к объекту, который Вы ищете. Это означает приблизительно одно сравнение с правовой оговоркой специальной обработки, которую я просто упомянул.