Løsningsforslag - oppgaver i Avsnitt 6.1.5


Oppgave 2

  String[] navn = {"Olga","Basir","Ali","Per","Elin","Siri","Ole","Mette","Bodil"};

  int p = 17, q = 13;
  String[] hash = new String[p];

  for (String n : navn)
  {
    int h = n.hashCode() & 0x7fffffff;          // hashverdi
    int i = h % p;                              // hashindeks
    if (hash[i] == null) hash[i] = n;           // legger inn
    else
    {
      int hopplengde = q - (h % q);             // bruker q

      while (true)
      {
        if ((i += hopplengde) >= p) i -= p;     // gjør et hopp
        if (hash[i] == null)
        {
          hash[i] = n;                          // legger inn
          break;                                // ferdig med denne verdien
        }
      }
    }
  }

  for (int i = 0; i < hash.length; i++)
  {
    if (hash[i] != null) System.out.print("(" + hash[i] + "," + i + ") ");
  }

  // Utskrift: (Olga,4) (Elin,5) (Mette,6) (Basir,8)
     (Ali,9) (Per,11) (Ole,12) (Siri,14) (Bodil,16)