java.util.Hashtable from inside
На собеседованиях любят спрашивать про то, как устроена Hashtable. Есть на эту тему хорошая статья в вики.
1. Реализован метод "с цепочками".
2. Каждая пара "ключ-значение" хранится в объекте типа Hashtable.Entry(имплементация Map.Entry), который по сути, является элементом односвязного списка.
3. Элементы хранятся во внутреннем массиве типа Hashtable.Entry. Первично его размер = initialCapacity, по достижении порога (count*loadFactor) производится операция rehash
4. Индекс для сохранения пары "ключ-значение" во внутреннем массиве определяется по формуле:
int index = (key.hashCode() & Integer.MAX_VALUE) % array.length;
5. При коллизии индексов(хеши могут отличаться), в массив записывается новая Hashtable.Entry, которая ссылается на бывшее значение массива по этому индексу. Таким образом, каждый элемент массива представляет собой односвязный список в чистом виде. Голова этого списка - последняя добавленная Hashtable.Entry
6. При операции rehash, длина массива увеличивается в 2 раза:
int newlength = (oldlength << 1) + 1;Индекс каждого элемента в новом массиве вычисляется по формуле (см п.4)
Теперь с примерами:
Пусть есть Hashtable с текущей capacity=3 (определена при создании, т.к. по умолчанию capacity=11, и это значение не уменьшается со временем).
В нее уже добавлены элементы типа String, с соответствующими ключами типа String. Короче:
Hashtable hashtable = new Hashtable(3,100F);// такой большой load_factor, чтобы не было rehash
hashtable.put("A","book");
hashtable.put("B","test");
hashtable.put("C","random");Обратите внимание на операцию вычисления индекса во внутреннем массиве.
Теперь вставляем новый элемент в Hashtable:
hashtable.put("D","jump");Видим, что во внутреннем массиве, для разных элементов, операция вычисления индекса дала один и тот же результат. Налицо коллизия индексов. Поэтому, во внутреннем массиве, по индексу 2, теперь находится элемент "D", который ссылается на элемент "A". Получился односвязный список.
Теперь какой нибудь злой человек вставляет в Hashtable вот такое:
hashtable.put("\0A","dr.evil");Он-то явно знает (смотрел в исходник String.hashCode), что "A".hashCode()="\0A".hashCode(). Таким образом, этот мерзкий тип устроил коллизию хешей. Естественно, индекс во внутреннем массиве остается тот же. Но Hashtable опять на высоте - он сравнивает ключи не только hashCode, но еще и по equals !
На закуску - операция rehash.
Создается новый внутренний массив, размер = (oldlength << 1) + 1; Далее пересчитываются индексы для всех Hashtable.Entry, таким образом, происходит перераспределение Hashtable.Entry во внутреннем массиве.
Выводы:
1. Для успешного хранения элементов в Hashtable желательна правильная реализация hashCode и необходима правильная реализация equals
2. Свистопляска с внутренними вычислениями индексов помогает экономить память
3. Для эффективной (быстрой) работы Hashtable желательно не допускать цепочек, установив load factor <= 1F, и соответственно избегать коллизий хешей ключа.
4. Для экономии памяти, наоборот, можно снижать initialCapacity и увеличивать load factor
5. Для въедливых(и незнающих), которые скажут, что "внутренняя реализация может измениться", сообщаю что эта внутренная реализация не менялась со времен JDK 1.2. Максимум что изменялось - это имплементация сериализации (writeObject/readObject).
Хак:
1. Задав initialCapacity=1 и load_factor=100000F можно пользоваться Hashtable как списком. Порядок возврата элементов - LIFO.
1. Реализован метод "с цепочками".
2. Каждая пара "ключ-значение" хранится в объекте типа Hashtable.Entry(имплементация Map.Entry), который по сути, является элементом односвязного списка.
3. Элементы хранятся во внутреннем массиве типа Hashtable.Entry. Первично его размер = initialCapacity, по достижении порога (count*loadFactor) производится операция rehash
4. Индекс для сохранения пары "ключ-значение" во внутреннем массиве определяется по формуле:
int index = (key.hashCode() & Integer.MAX_VALUE) % array.length;
5. При коллизии индексов(хеши могут отличаться), в массив записывается новая Hashtable.Entry, которая ссылается на бывшее значение массива по этому индексу. Таким образом, каждый элемент массива представляет собой односвязный список в чистом виде. Голова этого списка - последняя добавленная Hashtable.Entry
6. При операции rehash, длина массива увеличивается в 2 раза:
int newlength = (oldlength << 1) + 1;Индекс каждого элемента в новом массиве вычисляется по формуле (см п.4)
Теперь с примерами:
Пусть есть Hashtable с текущей capacity=3 (определена при создании, т.к. по умолчанию capacity=11, и это значение не уменьшается со временем).
В нее уже добавлены элементы типа String, с соответствующими ключами типа String. Короче:
Hashtable hashtable = new Hashtable(3,100F);// такой большой load_factor, чтобы не было rehash
hashtable.put("A","book");
hashtable.put("B","test");
hashtable.put("C","random");Обратите внимание на операцию вычисления индекса во внутреннем массиве.
Теперь вставляем новый элемент в Hashtable:
hashtable.put("D","jump");Видим, что во внутреннем массиве, для разных элементов, операция вычисления индекса дала один и тот же результат. Налицо коллизия индексов. Поэтому, во внутреннем массиве, по индексу 2, теперь находится элемент "D", который ссылается на элемент "A". Получился односвязный список.
Теперь какой нибудь злой человек вставляет в Hashtable вот такое:
hashtable.put("\0A","dr.evil");Он-то явно знает (смотрел в исходник String.hashCode), что "A".hashCode()="\0A".hashCode(). Таким образом, этот мерзкий тип устроил коллизию хешей. Естественно, индекс во внутреннем массиве остается тот же. Но Hashtable опять на высоте - он сравнивает ключи не только hashCode, но еще и по equals !
На закуску - операция rehash.
Создается новый внутренний массив, размер = (oldlength << 1) + 1; Далее пересчитываются индексы для всех Hashtable.Entry, таким образом, происходит перераспределение Hashtable.Entry во внутреннем массиве.
Выводы:
1. Для успешного хранения элементов в Hashtable желательна правильная реализация hashCode и необходима правильная реализация equals
2. Свистопляска с внутренними вычислениями индексов помогает экономить память
3. Для эффективной (быстрой) работы Hashtable желательно не допускать цепочек, установив load factor <= 1F, и соответственно избегать коллизий хешей ключа.
4. Для экономии памяти, наоборот, можно снижать initialCapacity и увеличивать load factor
5. Для въедливых(и незнающих), которые скажут, что "внутренняя реализация может измениться", сообщаю что эта внутренная реализация не менялась со времен JDK 1.2. Максимум что изменялось - это имплементация сериализации (writeObject/readObject).
Хак:
1. Задав initialCapacity=1 и load_factor=100000F можно пользоваться Hashtable как списком. Порядок возврата элементов - LIFO.