Философия Java


Понимание hashCode( ) - часть 3


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

Зная основы хеширования, можно реализовать простой хешированный класс Map:

//: c09:SimpleHashMap.java

// Демонстрация хешированного Map.

import java.util.*; import com.bruceeckel.util.*;

public class SimpleHashMap extends AbstractMap { // Выбираем главное число размера хеш-таблицы

// для получения равномерного распределения:

private final static int SZ = 997; private LinkedList[] bucket= new LinkedList[SZ]; public Object put(Object key, Object value) { Object result = null; int index = key.hashCode() % SZ; if(index < 0) index = -index; if(bucket[index] == null) bucket[index] = new LinkedList(); LinkedList pairs = bucket[index]; MPair pair = new MPair(key, value); ListIterator it = pairs.listIterator(); boolean found = false; while(it.hasNext()) { Object iPair = it.next(); if(iPair.equals(pair)) { result = ((MPair)iPair).getValue(); it.set(pair); // Замена старого новым

found = true; break; } } if(!found) bucket[index].add(pair); return result; } public Object get(Object key) { int index = key.hashCode() % SZ; if(index < 0) index = -index; if(bucket[index] == null) return null; LinkedList pairs = bucket[index]; MPair match = new MPair(key, null); ListIterator it = pairs.listIterator(); while(it.hasNext()) { Object iPair = it.next(); if(iPair.equals(match)) return ((MPair)iPair).getValue(); } return null; } public Set entrySet() { Set entries = new HashSet(); for(int i = 0; i < bucket.length; i++) { if(bucket[i] == null) continue; Iterator it = bucket[i].iterator(); while(it.hasNext()) entries.add(it.next()); } return entries; } public static void main(String[] args) { SimpleHashMap m = new SimpleHashMap(); Collections2.fill(m, Collections2.geography, 25); System.out.println(m); } } ///:~




Начало  Назад  Вперед



Книжный магазин