Нужна внутренняя реализация HashTable в Java

Question

Мне нужна внутренняя реализация HashTable в Java-коде.Далее вы можете объяснить мне Дополнительные комментарии в коде, как это работает.

У меня есть базовые знания о коэффициенте нагрузки и емкости, которые используются в HashTable, где коэффициент загрузки равен 0,75 .Не могли бы вы объяснить с кратким примером.

Я застрял с этим в течение длительного времени.

1> Почему коэффициент загрузки 0,75 для хеш-таблицы , а не какое-либо другое значение, которое меняется.Довольно странно Пожалуйста, уточните.

2> Почему у нас нет коэффициента загрузки для HashMap?
Мне не нужен существующий код.Кто-то, кто написал код лучше, чем написано

Answer 1

Почему у нас нет коэффициента загрузки для HashMap?

Мы делаем - см. HashMap(int initialCapacity, float loadFactor)

Почему коэффициент загрузки 0,75 для хеш-таблицы, а не какое-либо другое значение, которое меняется.

1. Коэффициент загрузки для Hashtable составляет настраиваемый параметр.

2. Javadoc для HashMaps говорит это о значении 0.75.

"Как правило, коэффициент загрузки по умолчанию (.75) предлагает хороший компромисс между временными и пространственными затратами. Более высокие значения уменьшают накладные расходы пространства, но увеличивают стоимость поиска (отражается в большинстве операций Класс HashMap, включая get и put). "

Я понимаю, что число было определено эмпирическим тестированием, а не теоретическим анализом. (Тщательный теоретический анализ будет затруднен. Однако коэффициент загрузки 0,75 в сочетании с хорошей хэш-функцией, вероятно, достаточен для того, чтобы в большинстве случаев поддерживать цепочки хеширования до 1 или 2, и это приводит к быстрому среднему времени поиска. )

Answer 2

Вам никогда не понадобится внутренняя реализация, и именно поэтому Джошуа Блох действительно скрывал это от нас. Я предпочитаю использовать HashMap из стандартного класса API Java Collections для Hashtable. Во-первых, это быстрее (не синхронизировано). Во-вторых, Hashtable был в Java до того, как туда были добавлены реальные коллекции, а затем он был адаптирован (насколько я знаю).

Это выдержка из JavaDoc класса java.util.HashMap<K, V>:

Экземпляр HashMap имеет два параметра, влияющих на его производительность: начальная емкость и коэффициент загрузки . емкость - это количество сегментов в хэш-таблице, а начальная емкость - это просто емкость на момент создания хэш-таблицы. Коэффициент загрузки является мерой того, насколько полной хеш-таблице разрешено получать до того, как ее емкость будет автоматически увеличена. Когда количество записей в хэш-таблице превышает произведение коэффициента загрузки и текущей емкости, емкость примерно удваивается путем вызова метода rehash.

Я думаю, это понятно. Карта с коэффициентом загрузки 0,75 и начальной емкостью 100 будет вставлять первые 75 новых записей карты без выделения памяти. Если вы добавите еще один элемент. Новый блок памяти с емкостью 200 выделяется, и существующие элементы копируются в эту новую память. Новое количество предметов, которые нужно получить, чтобы был выделен еще один блок памяти, теперь равно 150.

Более подробную информацию можно увидеть в исходном коде класса HashMap.

Answer 3

Ну, не берите в голову каламбур, но это зависит от реализации. Пока он соответствует интерфейсу и имеет то же ожидаемое время выполнения O, он может делать все, что захочет.

При этом здесь указана ссылка на GCC-версию Java HashTable http://www.google.com/codesearch/p?hl=en#t4cUIrRdV2U/gnu/mingw/gcc-java-3.4.2-20040916-1-src.tar.gz|HvPdZYyCY6Q/gcc-3.4.2-20040916-1/libjava/java/util/Hashtable.java&q=HashTable.java

Я не думаю, что буду обрисовывать какие-либо комментарии, хотя:)

Answer 4

Ваша JVM имеет исходный код для библиотек, доступных в процессе установки JDK.Вы просто должны выбрать это.Java имеет две разные реализации: HashMap и HashTable.В HashTable есть дополнительные возможности для синхронизации, поэтому, если вам нужна базовая реализация, посмотрите на исходный код HashMap.Кроме того, ты сам по себе.

Answer 5

Исходный код доступен бесплатно, и вы можете скачать его. Или посмотрите здесь:

http://www.docjar.com/html/api/java/util/Hashtable.java.html

Answer 6

Исходный код доступен для скачивания .Возможно, он уже есть - если вы используете Eclipse, нажмите Ctrl-Shift-T, введите «Hashtable» и посмотрите, видите ли вы источник.Самостоятельно загружать код определенно предпочтительнее, чем просто публиковать его здесь.

Если у вас есть какие-либо специфические вопросы о реализации, задавайте их (либо редактируя этот вопрос, либо задавая другой).Общий вопрос о том, «как работает Hashtable» вряд ли поможет вам продвинуться далеко ... хотя чтение общих принципов не повредит.

Answer 7

Код для большей части JDK поставляется с JDK. Это находится в файле src.jar. Если вы используете IDE, он автоматически свяжется с этим jar, поэтому, когда вы + во внутреннем классе, он покажет вам источник.

Стоит отметить, что Hashtable был заменен коллекциями Java 1.2 в 1998 году. Я не рекомендую использовать его, если не требуется для устаревших библиотек.

1> Почему коэффициент загрузки 0,75 для хеш-таблицы, а не какое-то другое значение, которое меняется. Довольно странно.

Как ни странно, по умолчанию должно быть что-то, и это значение было выбрано для наилучшего всестороннего выступления.

Мне не нужен существующий код. Кто-то, кто написал код лучше, чем тот, который на самом деле написан

Что вы подразумеваете под лучше? Вы смотрели на коллекции, добавленные с библиотекой параллелизма в Java 5.0 (2005). В некоторых случаях лучше в коллекциях Trove4j, поскольку они поддерживают примитивы. Вы также можете посмотреть на Guava, который имеет много расширений.