HashSet i tablica mieszająca
HashSet i tablica mieszająca
Jedną z podstawowych implementacji typu Set jest HashSet. Zbiory charakteryzują się tym, że nie posiadają duplikatów elementów. Oznacza to, że podczas dodawania nowego elementu musi być weryfikacja czy dany element istnieje w zbiorze czy nie. Dla implementacji HashSet jest to tablica mieszająca. Zobaczmy to na przykładzie!
Mamy kilka elementów które chcemy dodać do zbioru:
a,b,c,d,e,f,g,h,i
Dla każdego z tych elementów liczymy hashCode(). Dla uproszczenia przyjmijmy, że jest to kod ASCII:
a kod: 97
b kod: 98
c kod: 99
d kod: 100
e kod: 101
f kod: 102
g kod: 103
h kod: 104
i kod: 105
Jak liczymy indeks? Zakładamy sobie pewną liczbę np. 7 która reprezentuje liczbę kubełków w których będą umieszczane elementy a następnie liczymy resztę z dzielenia kodu przez liczbę kubełków:
97 % 7 = 6 kubełek
98 % 7 = 0 kubełek
99 % 7 = 1 kubełek
100 % 7 = 2 kubełek
101 % 7 = 3 kubełek
102 % 7 = 4 kubełek
103 % 7 = 5 kubełek
104 % 7 = 6 kubełek
105 % 7 = 0 kubełek
Zauważyć można, że niektóre elementy umieszczane są w tych samych kubełkach:
litera a i litera h => kubełek 6
litera b i litera i => kubełek 1
Wyszukanie elementu w tego typu strukturze jest bardzo efektywnym mechanizmem. Wystarczy bowiem policzyć indeks na podstawie kodu mieszania i ilości kubełków. Po policzeniu indeksu jeżeli w kubełku jest tyko jeden element to wystarczy zwrócić go bez konieczności wykonywania dodatkowych porównań. Poniżej zamieszczam przykładowy kod który realizuje opisane wyżej założenia:
public class HashTableAlghorithm { final int NB = 7; LinkedList [] hashTab = generateHashTab(NB); public HashTableAlghorithm() { String[] elements = getSampleElements(); for (int i = 0; i < elements.length; i++) { insertElementToHashTable(elements[i]); } printHashTableAllStructure(); } public void insertElementToHashTable(String s) { int hashCode = s.hashCode(); int index = hashCode % NB; if (!isElementExistInHashTable(index, s)) { hashTab[index].add(s); } System.out.println(s + " code: " + hashCode + " index: " + index); } private boolean isElementExistInHashTable(int index, String s) { for (Iterator i = hashTab[index].iterator(); i.hasNext(); ) if (s.equals(i.next())) { return true; } return false; } private String [] getSampleElements() { String[] elements = { "a", "b", "c", "d", "e", "f", "g", "h", "i", "a" }; return elements; } private void printHashTableAllStructure() { for (int i = 0; i < NB; i++) { String report = i + " - "; Iterator it = hashTab[i].iterator(); while (it.hasNext()) { report += " - " + it.next(); } System.out.println(report); } } private LinkedList [] generateHashTab(int buckets) { LinkedList [] hashTab = new LinkedList[buckets]; for (int i = 0; i < NB; i++) { hashTab[i] = new LinkedList(); } return hashTab; } public static void main(String args[]) { new HashTableAlghorithm(); } }
Wynik:
a code: 97 index: 6 b code: 98 index: 0 c code: 99 index: 1 d code: 100 index: 2 e code: 101 index: 3 f code: 102 index: 4 g code: 103 index: 5 h code: 104 index: 6 i code: 105 index: 0 a code: 97 index: 6 0 - - b - i 1 - - c 2 - - d 3 - - e 4 - - f 5 - - g 6 - - a - h Process finished with exit code 0
Leave a comment