Клас Hashtable

Хеш-таблиці являють собою поширений механізм для зберігання пар ключ / елемент Вони володіють такими перевагами, як універсальність і простота, а також висока ефективність при добре продуманої генерації хеш-коду реалізує інтерфейс Dictionary Він володіє певною ємністю і засобами, визначальними момент збільшення таблиці Розширення хеш-таблиці вимагає повторного хешування всіх її елементів відповідно до їх новим положенням в збільшеній таблиці, так що важливо забезпечити однократна зміна таблиці

Інший фактор, що впливає на ефективність хеш-таблиці, – процес генерації хеш-коду по ключу Конфлікти хеш-кодів повинні відбуватися якомога рідше Хеш-коди зобовязані рівномірно розподілятися по діапазону можливих значень, який для класу Hashtable збігається з повним діапазоном типу int Якщо різні ключі часто призводять до одних і тих же хеш-кодами, то деяка частина хеш-таблиці швидко переповниться, в результаті чого постраждає ефективність

Значення хеш-коду повертається методом hashCode для обєкта, що є ключем За замовчуванням кожен обєкт має унікальний хеш-код Використання як ключів випадково вибраних обєктів призводить до породження різних хеш-кодів Класи String, BitSet і більшість інших, переобумовленої метод equal, зазвичай перевизначають і hashCode Це важливо, оскільки клас Hashtable використовує хеш-код

для знаходження набору ключів, які можуть збігатися з заданим, і викликає equal для кожного з таких обєктів, поки не буде знайдений співпадає Якщо для деяких обєктів equal і hashCode виявляться несумісними, то при використанні обєктів цього типу в якості ключів Hastable їх поведінку виявиться непередбачуваним

Приклад використання класу Hastable приведений у класі Attributed Impl (див розділ Реалізація інтерфейсів), в якому обєкт Hashtable використаний для зберігання атрибутів обєкта У цьому прикладі ключами є строкові обєкти, що представляють собою імена атрибутів, а обєкти Attr були значеннями атрибутів

Крім методів, що входять в клас Dictionary (get, put, remove, size, isEmpty, keys і

elements), Hastable містить наступні методи:

public synchronized boolean containsKey(Object key)

Повертає true, якщо хеш-таблиця містить елемент із заданим ключем public synchronized boolean contains(Object element)

Повертає true, якщо заданий element є елементом хеш-таблиці Дана операція є більш складною, ніж метод containsKey, оскільки хеш-таблиця

спроектована з розрахунком на ефективний пошук ключів, а не елементів public synchronized void clear()

Робить хеш-таблицю порожній

public synchronized Object clone()

Створює дублікат хеш-таблиці Ключі та елементи при цьому НЕ дублюються

Обєкти Hashtable автоматично збільшуються, коли вони стають занадто заповненими Під виразом занадто заповненими розуміється перевищення показника завантаження таблиці, який являє собою відношення кількості елементів до поточної ємності таблиці Коли таблиця збільшується, її нова ємність приблизно вдвічі перевищує поточну Для підвищення ефективності слід вибирати ємність, представлену простим числом, щоб при збільшенні обєкта Hastable також було вибрано найближчим просте число Вихідна ємність хеш-таблиці і показник завантаження можуть задаватися в конструкторах Hashtable:

public Hashtable()

Конструює нову, порожню хеш-таблицю з прийнятої за замовчуванням вихідної ємністю і показником завантаження, рівним 0, 75

public Hashtable(int initialCapacity)

Конструює нову, порожню хеш-таблицю з заданою ємністю initial Capacity і прийнятим за замовчуванням показником завантаження, рівним 0,75

public Hashtable(int initialCapacity, float loadFactor)

Конструює нову, порожню хеш-таблицю з заданою ємністю і показником завантаження loadFactor, який являє собою число, яке лежить в діапазоні 0,0-1,0 і визначальне момент збільшення хеш-таблиці Якщо кількість елементів хеш-таблиці перевищує поточну ємність, помножену на показник завантаження, то хеш-таблиця автоматично збільшується

Ємність за умовчанням вибирається розумної, причому критерій розумності залежить від реалізації Після конструювання обєкта Hashtable неможливо змінити показник завантаження або явно задати нову ємність

При збільшенні обєкта Hashtable повторне хешування здійснюється методом rehash Метод rehash є захищеним, так що розширені класи можуть викликати його на свій розсуд, коли вони вирішать, що настав час збільшити ємність таблиці Задати новий розмір при цьому неможливо – він завжди обчислюється методом rehash

При реалізації метод HashtabletoString повертає рядок, яка повністю описує вміст таблиці, включаючи результати виклику to String для всіх ключів і елементів, що входять в неї

Вправа 123

У класі WhichChars, мається проблема з позначкою символів у верхній частині діапазону Unicode, оскільки високі значення символів залишають багато невикористаних бітів в нижній частині діапазону Вирішіть цю проблему за допомогою класу Hashtable, зберігаючи обєкт Character для кожного виявленого символу Не забудьте написати свій клас-перерахування

Вправа 124

Тепер скористайтеся класом Hashtable, щоб зберігати обєкт BitSet для кожного нового старшого байта (старші 8 біт), що зустрічається у вхідному рядку, причому кожен BitSet повинен містити молодші байти разом з даними старшим байтом Не забудьте написати свій клас-перерахування

Вправа 125

Напишіть програму, яка користується обєктом StreamTokenizer для розбиття вхідного файлу на слова і підрахунку кількості слів у файлі, з виведенням результату

Джерело: Арнольд К, Гослінг Д – Мова програмування Java (1997)

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*