Хэш-таблицы предоставляют полезный способ оптимизации производительности приложений.
Хэш-таблицы не являются новой концепцией в компьютерной области. Они были разработаны для ускорения компьютерной обработки, которая по сегодняшним стандартам очень медленная, и позволяют быстро найти конкретную запись при запросе большого количества записей данных. Хотя современные машины в тысячи раз быстрее, хеш-таблицы по-прежнему остаются полезным инструментом для достижения максимальной производительности ваших приложений.
Представьте, что у вас есть файл данных, содержащий около тысячи записей (скажем, записи клиентов малого бизнеса) и программа, которая считывает записи в память для обработки. Каждая запись содержит уникальный пятизначный идентификационный номер клиента, имя клиента, адрес, баланс счета и т. д. Предположим, что записи не отсортированы по идентификационному номеру клиента. Поэтому, если программа хочет использовать номер клиента в качестве «ключа» для поиска конкретной записи о клиенте, единственный способ найти ее — это искать в каждой записи последовательно. Иногда она найдет нужную вам запись быстро, но иногда, прежде чем программа найдет нужную вам запись, она уже почти ищет последнюю запись. Если вы хотите выполнить поиск среди 1000 записей, то для поиска любой одной записи программа должна проверить в среднем 500,5 ((1000 + 1)/2) записей. Если вам часто приходится искать данные, вам может понадобиться более быстрый способ поиска записи.
Один из способов ускорить поиск — разбить записи на части, чтобы вместо поиска в одном большом списке вы выполняли поиск в нескольких коротких списках. Для наших числовых идентификационных номеров клиентов вы можете создать 10 списков: один список для идентификационных номеров, начинающихся с 0, другой список для идентификационных номеров, начинающихся с 1, и так далее. Таким образом, чтобы найти идентификационный номер клиента 38016, вам нужно всего лишь выполнить поиск по списку, начинающемуся с 3. Если имеется 1000 записей и средняя длина каждого списка равна 100 (1000 записей разделены на 10 списков), то среднее количество сравнений для поиска записи падает примерно до 50 (см. рисунок 1).
Конечно, если примерно один из десяти номеров клиентов начинается с 0, другой десятый — с 1 и так далее, то этот подход будет работать хорошо. Если 90% номеров клиентов начинаются с 0, то в этом списке будет 900 записей, что потребует в среднем 450 сравнений за один поиск. Кроме того, 90% поисков, которые необходимо выполнить программе, приходится на числа, начинающиеся с 0. Следовательно, среднее число сравнений выходит далеко за рамки простых математических операций.
Было бы лучше, если бы мы могли распределить записи в наших списках таким образом, чтобы в каждом списке были примерно одинаковые записи, независимо от распределения чисел в значениях ключей. Нам нужен способ объединить количество клиентов и лучше распределить результаты. Например, мы могли бы взять каждую цифру числа, умножить ее на какое-то большое число (которое варьируется в зависимости от положения цифры), сложить результаты, чтобы получить сумму, разделить это число на 10 и выдать остаток в виде индекса. значение (индекс). Когда запись считывается, программа запускает хэш-функцию для номера клиента, чтобы определить, к какому списку принадлежит запись. Когда пользователю необходимо выполнить запрос, та же хеш-функция используется в качестве «ключа» для номера клиента, чтобы можно было найти правильный список. Подобная структура данных называется хеш-таблицей.
Хэш-таблицы в Java
Java содержит два класса: java.util.Hashtable и java.util.HashMap , которые предоставляют многоцелевой механизм хеш-таблицы. Эти два класса очень похожи и обычно предоставляют один и тот же общедоступный интерфейс. Но у них есть некоторые важные различия, о которых я расскажу позже.
Объекты Hashtable и HashMap позволяют объединить ключ и значение и ввести пару ключ/значение в таблицу с помощью метода put (). Затем вы можете получить значение, вызвав метод get(), передав ключ в качестве параметра. Ключом и значением могут быть любые объекты, если они соответствуют двум основным требованиям. Обратите внимание: поскольку ключи и значения должны быть объектами, примитивные типы необходимо преобразовать в объекты с помощью таких методов, как Integer(int).
Чтобы использовать объект определенного класса в качестве ключа, класс должен предоставить два метода:quals() и hashCode(). Эти два метода находятся в java.lang.Object , поэтому все классы могут наследовать эти два метода, однако реализация этих двух методов в классе Object обычно бесполезна, поэтому вам обычно приходится перегружать эти два метода самостоятельно;
Метод Equals() сравнивает свой объект с другим объектом и возвращает true, если два объекта представляют одну и ту же информацию. Этот метод также проверяет, принадлежат ли оба объекта одному и тому же классу. Object.equals() возвращает true, если два ссылочных объекта являются идентичными объектами, что объясняет, почему этот метод обычно не подходит. В большинстве случаев вам нужен способ сравнения полей по полям, поэтому мы считаем разные объекты, представляющие одни и те же данные, равными.
Метод HashCode() генерирует значение int, выполняя хеш-функцию, используя содержимое объекта. Hashtable и HashMap используют это значение, чтобы определить, в каком сегменте (или списке) находится пара ключ/значение.
В качестве примера можно рассмотреть класс String, поскольку у него есть свои методы, реализующие эти два метода. String.equals() сравнивает два объекта String посимвольно и возвращает true, если строки одинаковы:
Скопируйте код кода следующим образом:
String myName = "Эйнштейн";
// Следующий тест
// всегда правда
if ( myName.equals("Эйнштейн"))
{ ...
String.hashCode() запускает хеш-функцию для строки. Числовой код каждого символа строки умножается на 31, а результат зависит от позиции символа в строке. Результаты этих расчетов затем суммируются и дают общую сумму. Этот процесс может показаться сложным, но он обеспечивает лучшее распределение значений. Он также демонстрирует, как далеко вы можете зайти при разработке собственного метода hashCode(), будучи уверенным в уникальности результата.
Например, предположим, что я хочу использовать хеш-таблицу для реализации каталога книг и использовать номер ISBN книги в качестве ключа поиска. Я могу использовать класс String для хранения подробностей и подготовить методы Equals() и hashCode() (см. листинг 1). Мы можем добавить пары ключ/значение в хеш-таблицу с помощью метода put () (см. листинг 2).
Метод Put () принимает два параметра, оба типа Object. Первый параметр является ключевым; второй параметр — значение. Метод Put () вызывает метод hashCode() ключа и делит результат на количество списков в таблице. Используйте остаток в качестве значения индекса, чтобы определить, в какой список добавляется запись. Обратите внимание, что ключ уникален в таблице; если вы вызываете put () с существующим ключом, соответствующая запись изменяется так, что она ссылается на новое значение, и возвращается старое значение (Когда ключ не существует в таблице , put () возвращает нулевое значение).
Чтобы прочитать значение из таблицы, мы используем ключ поиска с методом get(). Он возвращает ссылку на объект, преобразованную в правильный тип:
Скопируйте код кода следующим образом:
КнигаЗапись br =
(BookRecord)isbnTable.get(
«0-345-40946-9»);
System.out.println(
"Автор: " + бр.автор
+ "Заголовок:" + бр.заголовок);
Еще один полезный метод — remove(), который используется почти так же, как и get(). Он удаляет запись из таблицы и возвращает ее вызывающей программе.
твой собственный класс
Если вы хотите использовать примитивный тип в качестве ключа, вам необходимо создать объект того же типа. Например, если вы хотите использовать целочисленный ключ, вам следует использовать конструктор Integer(int) для создания объекта из целого числа. Все классы-оболочки, такие как Integer, Float и Boolean, рассматривают примитивные значения как объекты и перегружают методыquals() и hashCode(), поэтому их можно использовать в качестве ключей. Многие другие классы, представленные в JDK, похожи на этот (даже классы Hashtable и HashMap реализуют свои собственные методыquals() и hashCode()), но вам следует проверить документацию, прежде чем использовать объекты любого класса в качестве ключей хеш-таблицы. Также необходимо проверить исходный код класса, чтобы увидеть, как реализованы методы равенства() и hashCode(). Например, Байт, Символ, Короткое и Целое число возвращают представленное целочисленное значение в виде хеш-кода. Это может соответствовать или не соответствовать вашим потребностям.
Использование хэш-таблиц в Java
Если вы хотите создать хеш-таблицу, которая использует объекты класса, который вы определяете в качестве ключей, вам следует убедиться, что методыquals() и hashCode() этого класса предоставляют полезные значения. Сначала посмотрите на расширяемый класс, чтобы определить, соответствует ли его реализация вашим потребностям. Если нет, вам следует перегрузить метод.
Основное ограничение конструкции любого методаquals() заключается в том, что он должен возвращать true, если переданный ему объект принадлежит к тому же классу и в его полях данных установлены значения, представляющие одни и те же данные. Вы также должны убедиться, что если вы передаете методу пустой аргумент, ваш код возвращает
Скопируйте код кода следующим образом:
false: общедоступное логическое значение равно (Объект o)
{
если ( (о == ноль)
|| !(о экземпляр моего класса))
{
вернуть ложь;
}
// Теперь сравниваем поля данных...
Кроме того, при разработке метода hashCode() следует учитывать некоторые правила. Во-первых, метод должен возвращать одно и то же значение для конкретного объекта, независимо от того, сколько раз он вызывается (конечно, до тех пор, пока содержимое объекта не меняется между вызовами). При использовании объекта в качестве ключа хеш-таблицы это должно следует избегать). Во-вторых, если два объекта, определенные вашим методом Equals(), равны, они также должны генерировать один и тот же хэш-код. В-третьих, и это скорее рекомендация, чем принцип: вам следует попытаться спроектировать свой метод так, чтобы он давал разные результаты для разного содержимого объекта. Не имеет значения, если иногда разные объекты генерируют один и тот же хэш-код. Однако если метод может возвращать значения только в диапазоне от 1 до 10, то можно использовать только 10 списков, независимо от того, сколько списков находится в хеш-таблице.
Еще один фактор, который следует учитывать при разработке методаquals() и hashCode(), — это производительность. Каждый вызов put () или get() включает вызов hashCode() для поиска правильного списка. Когда get() просматривает список в поисках ключа, он вызывает методquals() для каждого элемента в списке. Реализуйте эти методы так, чтобы они работали как можно быстрее и эффективнее, особенно если вы планируете сделать свой класс общедоступным, поскольку другие пользователи могут захотеть использовать ваш класс в высокопроизводительном приложении, где скорость выполнения важна.
Производительность хеш-таблицы
Основным фактором, влияющим на эффективность хэш-таблицы, является средняя длина списков в таблице, поскольку среднее время поиска напрямую связано с этой средней длиной. Очевидно, что для уменьшения средней длины вам придется увеличить количество списков в хеш-таблице. Наибольшую эффективность поиска вы получите, если количество списков настолько велико, что большинство или все списки содержат только одну запись; Однако это может зайти слишком далеко. Если в вашей хеш-таблице гораздо больше списков, чем записей данных, вам не нужно делать такие затраты памяти, а в некоторых случаях люди не могут принять этот подход.
В нашем предыдущем примере мы заранее знали, сколько записей у нас есть — 1000. Зная это, мы можем решить, сколько списков должна содержать наша хеш-таблица, чтобы достичь наилучшего компромисса между скоростью поиска и эффективностью использования памяти. Однако во многих случаях вы не знаете заранее, сколько записей вы будете обрабатывать; файл, из которого считываются данные, может постоянно расти, или количество записей может значительно меняться изо дня в день.
Классы Hashtable и HashMap решают эту проблему путем динамического расширения таблицы по мере добавления записей. Оба класса имеют конструкторы, которые принимают исходное количество списков в таблице и коэффициент загрузки в качестве параметра:
общедоступная хэш-таблица(
int начальная емкость,
плавающий коэффициент загрузки)
публичный HashMap(
int начальная емкость,
плавающий коэффициент загрузки)
Умножьте эти два числа, чтобы вычислить критическое значение. Каждый раз, когда в хеш-таблицу добавляется новая запись, счетчик обновляется, а когда счетчик превышает критическое значение, таблица сбрасывается (перехешируется). (Размер списка увеличивается в два раза по сравнению с предыдущим плюс 1, и все записи перемещаются в правильный список.) Конструктор по умолчанию устанавливает начальную емкость 11, а коэффициент загрузки — 0,75, поэтому критическое значение равно 8. Когда в таблицу добавляется девятая запись, хеш-таблица масштабируется так, что в ней становится 23 списка, и новое критическое значение будет равно 17 (целая часть 23*0,75). Вы можете видеть, что коэффициент загрузки — это верхняя граница среднего количества списков в хеш-таблице, а это означает, что по умолчанию хеш-таблица редко имеет много списков, содержащих более одной записи. Сравните наш исходный пример, где у нас было 1000 записей, распределенных по 10 спискам. Если мы используем значения по умолчанию, эта таблица расширится и будет содержать более 1500 списков. Но вы можете это контролировать. Если количество списков, умноженное на коэффициент загрузки, превышает количество обрабатываемых вами записей, таблица никогда не будет переработана, поэтому мы можем следовать примеру ниже:
Скопируйте код кода следующим образом:
// Таблица не будет перехешироваться, пока не будет
// имеет 1100 записей (10*110):
Хэш-таблица myHashTable =
новая хэш-таблица (10, 110.0F);
Вероятно, вы не захотите этого делать, если только вы не хотите экономить память для пустых списков и не возражаете против дополнительного времени поиска, что может иметь место во встроенных системах. Однако этот подход может быть полезен, поскольку сброс требует больших вычислительных затрат, и этот подход гарантирует, что сброс никогда не произойдет.
Обратите внимание: хотя вызов put () может привести к увеличению таблицы (увеличению количества списков), вызов Remove() не будет иметь обратного эффекта. Итак, если у вас большая таблица и вы удалили из нее большую часть записей, вы получите большую, но в основном пустую таблицу.
Хеш-таблица и HashMap
Между классами Hashtable и HashMap есть три важных различия. Первое отличие обусловлено главным образом историческими причинами. Hashtable основан на старом классе Dictionary, а HashMap — это реализация интерфейса Map, представленного в Java 1.2.
Возможно, самое важное отличие заключается в том, что методы Hashtable являются синхронными, а методы HashMap — нет. Это означает, что хотя вы можете использовать Hashtable в многопоточном приложении, не предпринимая никаких специальных действий, вы должны аналогичным образом обеспечить внешнюю синхронизацию для HashMap. Удобный метод — использовать статический методsyncdMap() класса Collections, который создает потокобезопасный объект Map и возвращает его как инкапсулированный объект. Методы этого объекта позволяют синхронно получать доступ к базовому HashMap. В результате вы не можете отключить синхронизацию в хэш-таблице, когда она вам не нужна (например, в однопоточном приложении), а синхронизация добавляет много накладных расходов на обработку.
Третье отличие состоит в том, что только HashMap позволяет использовать нулевые значения в качестве ключа или значения записи таблицы. Только одна запись в HashMap может быть пустым ключом, но любое количество записей может быть пустым значением. Это означает, что если ключ поиска не найден в таблице или если ключ поиска найден, но имеет нулевое значение, то get() вернет значение null. При необходимости используйте метод containsKey(), чтобы различать эти две ситуации.
Некоторая информация предполагает, что когда требуется синхронизация, используйте Hashtable, в противном случае используйте HashMap. Однако, поскольку HashMap при необходимости можно синхронизировать, HashMap имеет больше функций, чем Hashtable, и не основан на старом классе, некоторые люди думают, что HashMap предпочтительнее Hashtable в различных ситуациях.
О свойствах
Иногда вам может потребоваться использовать хеш-таблицу для сопоставления строк ключей со строками значений. Есть несколько примеров строк среды в DOS, Windows и Unix. Например, ключевая строка PATH сопоставляется со строкой значений C:/WINDOWS;C:/WINDOWS/SYSTEM. Хэш-таблицы — это простой способ их представления, но Java предлагает другой способ.
Класс Java .util.Properties является подклассом Hashtable, предназначенным для использования со строковыми ключами и значениями. Использование объекта Properties аналогично использованию Hashtable, но класс добавляет два метода экономии времени, о которых вам следует знать.
Метод Store() сохраняет содержимое объекта Properties в файл в читаемой форме. Метод Load() является противоположностью: он используется для чтения файла и установки объекта Properties, содержащего ключи и значения.
Обратите внимание: поскольку Properties расширяет Hashtable, вы можете использовать метод put () суперкласса для добавления ключей и значений, которые не являются объектами String. Это не рекомендуется. Кроме того, если вы используете store() с объектом Properties, который не содержит объект String, store() завершится ошибкой. В качестве альтернативы put () и get() вам следует использовать setProperty() и getProperty(), которые принимают параметры String.
Хорошо, надеюсь, теперь вы знаете, как использовать хеш-таблицы для ускорения обработки.