Программирование на JAVA

Для того, чтобы выяснить принципы работы дан­ного алгоритма, рассмотрим несколько примеров.

Предположим, имеется массив строк, содержащий названия городов. Для того, чтобы найти элемент массива, содержащий название города, в общем случае требуется просмотреть весь массив, а если необходимо най­ти все элементы массива, то для поиска каждого, в среднем, потребуется просматривать половину массива. Такой подход может оказаться приемле­мым только для небольших массивов.

Как уже отмечалось ранее, для того, чтобы увеличить скорость поис­ка, используется алгоритм хэширования. Каждый объект в Java унаследо­ван от Object. Как уже отмечалось ранее. Object определено целое число, которое уникально идентифицирует экземпляр класса Object и, соответст­венно, все экземпляры классов, унаследованных от Object. Это число воз­вращает метод hashCode(). Именно оно используется при сохранении ключа в Hashtable следующим образом: разделив длину массива, предназ­наченного для хранения ключей, на код, получаем некое целое число, ко­торое служит индексом для хранения ключа в массиве array.length % hashCode().

Далее, если необходимо добавить новую пару ключ/значение, вычис­ляется новый индекс, и если этот индекс совпадает с уже имеющимся, то создается список ключей, на который указывает элемент массива ключей-Таким образом, при обратном извлечении ключа необходимо вычислить индекс массива по тому же алгоритму и получить его. Если ключ в массиве единственный, то используется значение элемента массива, если хранится несколько ключей, то необходимо обойти список и выбрать нужный.

Есть несколько соображений, относящихся к производительности классов, использующих для хранения данных алгоритм хэширования. В частности, размер массива. Если массив окажется слишком мал, то свя­занные списки будут слишком длинными и скорость поиска станет су­щественно снижаться, так как просмотр элементов списка будет такой #е, как в обычном массиве. Чтобы этого избежать, задается некий коэф­фициент заполнения. При заполнении элементов массива, в котором хранятся ключи (или списки ключей) на эту величину, происходит уве­личение массива и производится повторное реиндексирование. Таким образом, если массив окажется слишком мал, то он будет быстро запол­няться и будет производиться операция повторного индексирования, ко­торая отнимает достаточно много ресурсов