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

Your email address will not be published.


*