Страниц: [1]
  Печать  
Автор Тема: Единая хэш-таблица  (Прочитано 8450 раз)
captain cobalt
Участник
*
Offline Offline

Сообщений: 0


Просмотр профиля
« : Октября 11, 2005, 04:04:50 pm »

Как известно, существуют системы, в которых целостность обеспечивается не аппаратной защитой памяти, а безопасным языком программирования.

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

Идея: использовать единую хэш-таблицу на всю систему.

Рассмотрим подробнее.

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

Теперь мы соединяем все эти отдельные таблицы в единую таблицу. Получаем единую таблицу, которая на логическом уровне всё равно состоит из нескольких отдельных таблиц, принадлежащих возможно разным клиентам. В результате получаем умеренную заполненность единой таблицы и одинаково быстрый поиск для каждой из отдельных таблиц. Свободное пространство единой таблицы может использовать для своего роста любая отдельная таблица.

При объединении отдельных таблиц в единую их данные перемешиваются. Возникающие при этом коллизии обрабатывает рантайм единой таблицы. Чтобы при обращении к данным одной отдельной таблицы не происходило ошибочного обращения к данным другой отдельной таблицы, может использоваться безопасный язык программирования. Также потребуется средство для удаления отдельных таблиц - освобождения принадлежащих им участков единой таблицы.

Другое преимущество единой таблицы - её можно динамически увеличивать и уменьшать, адаптируясь к нагрузке. Причём делать это прозрачно для всех клиентов. Это немного напоминает "сборку мусора".

Архитектура системы, построенной на единой хэш-таблице, будет довольно существенно отличаться от обычной. При наличии возможности использовать сколько угодно ассоциативных отображений (с очень быстрым поиском) существенно уменьшается потребность в других структурах данных - списках, деревьях и даже массивах.

Вопрос: существуют ли такие системы на единой хэш-таблице и где о них можно прочитать?
Записан
klalafuda
QOR.Team
****
Offline Offline

Сообщений: 1


Просмотр профиля
« Ответ #1 : Октября 11, 2005, 04:15:17 pm »

пардон, а хеш функция у вас то-же будет "единой" на всю систему и, как следствие, все типы данных.. ?

// wbr
Записан
AG
QOR.Moderator
*****
Offline Offline

Сообщений: 872



Просмотр профиля WWW
« Ответ #2 : Октября 11, 2005, 04:20:18 pm »

Хорошо объяснил тему, но плохо сказал зачем

На сколько я знаю таких систем нет (в широком распространении). Возможно они есть для закрытых или специальных применений. С другой стороны для "закрытых" или "специальных" применений такие вещи можно легко реализовать аппаратно... т.е. заказать соотв. чипу у TI...

ИМХО ОС писать, построенную на таком механизме не интересно, ибо быстрый поиск чего либо не еси основная задача ОС. Для БД может и подойдет такая идея, но локально...

Ответ: Не слышал такого. Врядли есть.
Записан

captain cobalt
Участник
*
Offline Offline

Сообщений: 0


Просмотр профиля
« Ответ #3 : Октября 11, 2005, 04:51:00 pm »

klalafuda
> пардон, а хеш функция у вас то-же будет "единой" на всю систему и, как следствие, все типы данных.. ?

Более точно: область значений хэш функции будет единой на всю систему (меняться в момент изменения размера). Будет низкоуровневая процедура вычисления значения хэш-функции от произвольного объекта (скорее всего, от его двоичного машинного представления), которая будет предоставлять "наружу" безопасный типизированный интерфейс.

AG
> быстрый поиск чего либо не еси основная задача ОС

Однако поиск широко используется в прикладном коде.
И если платформа предоставляет для этого единообразный и эффективный механизм, то это может быть весьма полезно.
Записан
lestat
QOR.Moderator
*****
Offline Offline

Сообщений: 985


I don't trust anything


Просмотр профиля WWW
« Ответ #4 : Октября 11, 2005, 05:02:28 pm »

Как я понял это просто теория. Если заглянуть в практическую сторону, то:

1) Вычисление хэш-функции от данных есть как минимум вычитка всех данных + математические операции, что процессоро-емко. Хорошая хэш-функция будет замедлять работу, плохая создавать множество коллизий.

2) Использование хэш'ей приведет к изрядной фрагментации памяти, как следствие выборка данных будет просто не попадать в кэш CPU. Постоянные cache-misses плачевно скажутся на производительности.

Если все-таки имеется теоритеческий интерес, либо применение хеш-функций в программах, а не в ОС, то рекомендую посмотреть sparse hash от google:

http://goog-sparsehash.sourceforge.net/
Записан

AG
QOR.Moderator
*****
Offline Offline

Сообщений: 872



Просмотр профиля WWW
« Ответ #5 : Октября 11, 2005, 05:29:13 pm »

lestat
1) Вычисление хэш-функции от данных есть как минимум вычитка всех данных + математические операции, что процессоро-емко. Хорошая хэш-функция будет замедлять работу, плохая создавать множество коллизий.

2) Использование хэш'ей приведет к изрядной фрагментации памяти, как следствие выборка данных будет просто не попадать в кэш CPU. Постоянные cache-misses плачевно скажутся на производительности.


ИМХО без аппаратной реализации ХЭШ-механизма реализовывато на нем ОС не имеет смысла ибо накладно... Собственно по этому никто такую ОС и не пишет...
Записан

captain cobalt
Участник
*
Offline Offline

Сообщений: 0


Просмотр профиля
« Ответ #6 : Октября 11, 2005, 05:55:26 pm »

lestat

1)
а) Хэширование используется для поиска. Вычитка данных будет происходить в любом случае -- должны же мы прочитать, что надо искать.
б) Например известный elfhash Алена Голуба использует только операции сложения и сдвига, и эксперименты показывают, что создаёт распределение, очень близкое к равномерному.

2)
Опять же, хэширование используется для поиска. Например, когда хэширование только-только изобрели, Ершов сразу вывел элементарный факт: если заполненность таблицы меньше 2/3, то среднее число обращений при поиске меньше 2. Другие методы поиска требуют на представительных объемах перебора заметно больше, чем двух элементов, для которых тоже нужно место в кэше. В любом случае, когда мы нашли данные, мы видимо собираемся к ним обратиться.

Безусловно, в других задачах можно организовать данные так, чтобы к ним обращаться последовательно. Но это не поиск.

> рекомендую посмотреть sparse hash от google

Интересно.
Записан
captain cobalt
Участник
*
Offline Offline

Сообщений: 0


Просмотр профиля
« Ответ #7 : Октября 11, 2005, 06:13:29 pm »

AG
> ИМХО без аппаратной реализации ХЭШ-механизма реализовывато на нем ОС не имеет смысла ибо накладно...

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

Единая хэш-таблица решает эту проблему. Более того, поскольку теперь имеется работающий в масштабах всей системы эффективный механизм поиска, его можно использовать там, где раньше применялся менее эффективный поиск.
Записан
Страниц: [1]
  Печать  
 
Перейти в: