Pull to refresh

Семейство хеш-функций CityHash от Google

Algorithms *
Google выложил под свободной лицензией новое семейство хеш-функций CityHash для строк. Пока представлены функции CityHash64 и CityHash128 для получения 64- и 128-битных хеш-кодов.

Как сообщают разработчики, в реальных условиях CityHash64 превосходит по скорости аналогичные хеш-функции как минимум на 30%.

В силу своей простоты данные хеш-функции не подходят для криптографических применений, но теоретически это идеальный вариант для хеш-таблиц. Правда, код пока сыроват, недостаточно оттестирован (см. warning) и нуждается в некоторой доработке.
Читать дальше →
Total votes 45: ↑41 and ↓4 +37
Views 11K
Comments 15

Trove 4.0? Примитивы в стандартном каркасе коллекций из Java 8

Java *Algorithms *
Translation
Около месяца назад на Хабре была статья про Trove — самую часто упоминаемую библиотеку, когда спрашивают про структуры данных с примитивами на Java. Примерно за пару дней до этого я сел эту библиотеку переписывать. Время решительно кончилось, поэтому делюсь поиском с вами, хотя не очень-то надеюсь, что кто-то продолжит это дело.

На данный момент сделаны хеш-таблицы 6 типов: множества примитивов, объектов и все 4 варианта мапов: примитив — примитив, примитив — объект, объект — примитив и объект — объект, над которыми нависает туча обобщающих интерфейсов.

Меня всегда удивляло, почему все подобные библиотеки создают еще одну иерархию типов, а не встраиваются в давно уже зарекомендовавший себя стандартный каркас коллекций Явы. Никаких принципиальных проблем с этим я не видел и не вижу. Поэтому над моей тучей интерфейсов, как на пантеоне, возвышаются java.lang.Iterable, java.util.Collection и java.util.Map. Я не зря дал ссылки на документацию по Java 8. Реализованы почти все методы из будущих интерфейсов, кроме spliterator(). Можно начинать привыкать.
Читать дальше →
Total votes 21: ↑18 and ↓3 +15
Views 9.3K
Comments 31

Как я ошибся при написании хеш-таблицы и какие выводы из этого сделал

Programming *Debugging *FPGA *
Для ясности теоретического понимания нет лучшего пути, чем учиться на своих собственных ошибках, на собственном горьком опыте. (Фридрих Энгельс)

Всем привет!


Несколько недель назад мне в линкедине написал коллега и сообщил, что в моем проекте на гитхабе не совсем верно работает хеш-таблица.


Мне прислали тесты и фикс, и действительно создавалась ситуация, где система "зависала". При расследовании проблемы я понял, что допустил несколько ошибок при верификации. На Хабре тема верификации RTL-кода не слишком подробна расписана, поэтому я и решил написать статью.


Из статьи вы узнаете:


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

Добро пожаловать под кат!

Читать дальше →
Total votes 39: ↑37 and ↓2 +35
Views 24K
Comments 9

Что нужно знать об устройстве коллекций, основанных на хешировании

OTUS corporate blog Programming *Java *Algorithms *Industrial Programming *
Всем привет. На связи Владислав Родин. В настоящее время я являюсь руководителем курса «Архитектор высоких нагрузок» в OTUS, а также преподаю на курсах, посвященных архитектуре ПО.

Помимо преподавания, как вы могли заметить, я занимаюсь написанием авторского материала для блога OTUS на хабре и сегодняшнюю статью хочу посвятить запуску нового потока курса «Алгоритмы для разработчиков».





Введение


Хеш-таблицы (HashMap) наравне с динамическими массивами являются самыми популярными структурами данных, применяемыми в production'е. Очень часто можно услышать вопросы на собеседованиях касаемо их предназначения, особенностей их внутреннего устройства, а также связанных с ними алгоритмов. Данная структура данных является классической и встречается не только в Java, но и во многих других языках программирования.
Читать дальше →
Total votes 16: ↑14 and ↓2 +12
Views 10K
Comments 4

Тесты своей реализации ассоциативных массивов vs хеш-таблица

Programming *Algorithms *

Приветствую, читатель. Я являюсь автором языка программирования Shar. В стандартном модуле Shar есть несколько реализаций ассоциативных массивов и при написании данного модуля я подумал: "А какую структуру данных для реализации ассоциативных массивов мне выбрать?". Являясь любителем слушать различные конференции по программированию, я периодически натыкаюсь на выступления людей, принимающих участие в разработке популярных языков программирования. На основании таких выступлений, у меня сложилось субъективное восприятие того, что в большинстве случаев для реализации ассоциативных массивов используется хеш-таблица. Хеш таблица действительно является очень хорошим выбором, но тогда почему я начал задумываться о выборе подходящей структуры данных? А причина в том, что ...

Читать далее
Total votes 7: ↑5 and ↓2 +3
Views 3.2K
Comments 5