elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Слайды с доклада про быстрые структуры данных
elizarov

По просьбе организаторов Application Developer Days выкладываю слайды своего доклада про быстрые структуры данных на SlideShare. Смотреть cлайды по этой ссылке.

Организаторы, в свою очередь, уже выложили видео запись моего выступления.

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

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

Я готов осветить и другие смежные темы — задавайте вопросы.

UPDATE: Первый пункт сделал.


  • 1
(Deleted comment)
Исправил эту оЧеПятку.

Edited at 2012-06-20 08:01 am (UTC)

Я правильно понимаю что для того чтобы реализовать удаление в thread safe hash map c открытой адресацией придётся делать readLock в операциях чтения?

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

"Во-вторых, можно так реализовать операции удаления с блокировками, чтобы операции поиска можно было продолжать делать без блокировок."
Видимо вот это, да?
http://en.wikipedia.org/wiki/Lazy_deletion

  • 1
?

Log in

No account? Create an account