В структурах данных хэш-таблицы и связанные списки часто используются в сочетании.Если вы знакомы с java, вы найдете LinkedHashMap, часто используемый контейнер, который также объединяет хэш-таблицы и связанные списки. Как хеш-таблица и связанный список используются вместе, и с какими искрами они могут столкнуться, пожалуйста, следуйте по моим стопам и узнайте вместе.
Давайте сначала подумаем над таким вопросом, как использовать связанный список для реализации кэша LRU? Если вы не знакомы с LRU, вы можете прочитать эту статью.Вы изучили алгоритм замены страницы?
Мы можем поддерживать упорядоченный односвязный список, и к узлам, расположенным ближе к концу связанного списка, обращаются раньше. При доступе к новой части данных мы последовательно переходим от начала списка. Результат обхода имеет два случая.
- Если эти данные ранее были кэшированы в связанном списке, мы переходим, чтобы получить узел, соответствующий этим данным, а затем перемещаем его из этой позиции в начало связанного списка.
- Если этих данных нет в связанном списке, он будет разделен на два случая. Если связанный список кеша в это время не заполнен, мы вставляем узел непосредственно в заголовок связанного списка. Если в это время связанный список кеша заполнен, мы удаляем узел из хвоста связанного списка, а затем вставляем новый узел данных в начало связанного списка.
Таким образом, мы реализовали LRU-кэш со связанным списком.Проанализируем временную сложность доступа к кешу. Поскольку независимо от того, заполнен ли кеш или нет, нам нужно пройти по связанному списку один раз, поэтому кеш LRU, реализованный на основе связанного списка, временная сложность доступа к кешу составляет O (n).
Есть ли способ уменьшить временную сложность? Давайте сначала проанализируем общие операции кэша. Для кэша в основном задействованы следующие три операции:
- Добавляет элемент в кеш.
- Удалить элемент из кеша.
- Найти элемент в кеше.
Эти три операции будут включать операции поиска.Если вы просто используете связанный список, временная сложность может быть только O (n). Всем известно, что операция поиска в хеш-таблице выполняется за O(1), поэтому можем ли мы объединить хеш-таблицу и связанный список, чтобы уменьшить временную сложность этих трех распространенных операций кэширования до O(1)? Ответ - да, давайте посмотрим, как они все сочетаются друг с другом.
Как показано на рисунке, для хранения данных мы используем двусвязный список.Помимо данных (data), указателя-предшественника (pre) и указателя-последователя (next), каждый узел в связанном списке также добавляет специальное поле hnext. Что это делает дальше? Поскольку наша хеш-таблица разрешает коллизии хэшей с помощью метода связанного списка, каждый узел будет состоять из двух цепочек. Одна цепочка — это только что упомянутый двусвязный список, а другая цепочка — это молния в хеш-таблице. Указатель на предшественника и преемника используется для связывания узлов в двусвязном списке, а указатель hnext используется для связывания узлов в застежке-молнии хэш-таблицы.
После понимания комбинированной структуры хранения этой хеш-таблицы и двусвязного списка давайте посмотрим, как три операции кэша, упомянутые выше, достигают временной сложности O (1)?
Во-первых, давайте посмотрим, как найти часть данных. Как мы упоминали ранее, временная сложность поиска данных в хеш-таблице близка к O(1), поэтому с помощью хеш-таблицы мы можем быстро найти данные в кеше. Когда данные найдены, нам также нужно переместить их в конец двусвязного списка.
Во-вторых, давайте посмотрим, как удалить часть данных. Нам нужно найти узел, в котором находятся данные, а затем удалить узел. С помощью хеш-таблицы мы можем найти узел для удаления за время сложности O(1). Поскольку наш связанный список является двусвязным списком, двусвязный список может получить предшествующий узел через указатель предшественника O (1) временной сложности, поэтому в двусвязном списке удаление узла требует только O (1) временной сложности.
Наконец, давайте посмотрим, как добавить файл data. Добавить данные в кеш немного сложно, нам нужно посмотреть, есть ли данные уже в кеше. Если он уже есть в нем, его нужно переместить в начало двусвязного списка, если его нет в нем, то это зависит от того, заполнен ли кеш. Если он заполнен, удалите узел в конце двусвязного списка, а затем поместите данные в начало связанного списка; если он не заполнен, сразу поместите данные в начало связанного списка. Операции поиска, задействованные во всем этом процессе, можно выполнять с помощью хеш-таблицы.
Другие операции, такие как удаление головного узла, вставка данных в конец связанного списка и т. д., могут быть выполнены за время сложности O(1). Следовательно, временная сложность этих трех операций составляет O(1). К настоящему моменту мы реализовали прототип эффективной системы кэширования, которая поддерживает алгоритм ликвидации кэша LRU за счет комбинации хеш-таблицы и двусвязного списка.
Следовательно, кэш LRU с временной сложностью O(1) может быть реализован путем объединения хэш-таблицы и связанного списка.
*Для получения дополнительной информации, пожалуйста, обратите внимание на общедоступный номер"Программист старший".