Oppgave 1

Vi må finne bokstaver a, b, c og d slik at 31a + b = 31c + d eller 31(a - c) = d - b. Vi kan som a og b velge to bokstaver ved siden av hverandre, f.eks. a = 'B' og c = 'A'. Dermed bli a - c = 'B' - 'A' = 1 og 31(a - c) = 31. Vi får løst oppgaven hvis vi finner to bokstaver d og b som har en avstand på 31. Vi har at avstanden mellom 'A' og 'a' er 32. Da kan vi velge d = 'a' og b = 'B'. Da blir d - b = 'a' - 'B' = 31. Eller vi kan velge d = 'b' og b = 'C', osv. Med andre ord er det mange muligheter.

  System.out.println("BB".hashCode() + " " + "Aa".hashCode());
  // Utskrift: 2112 2112

Oppgave 2

  int n = 197;
  int[] hash = new int[n];

  for (int i = 0; i < 400; i++)
  {
    String s = "A";
    if (i < 100) s += 0;
    if (i < 10) s += 0;
    s += i;
    hash[s.hashCode() % n]++;
  }

  int m = Tabell.maks(hash);  // posisjonen til største verdi

  int maks = hash[m];         // den største verdien

  int[] frekvens = new int[maks + 1];
  for (int i = 0; i < hash.length; i++) frekvens[hash[i]]++;  // teller opp

  System.out.println(Arrays.toString(frekvens));  // [0, 48, 95, 54]

Utskriften over viser at alle indeksene ble brukt. Det var 48 indekser som ble brukt én gang, 95 ble brukt to ganger og 54 ble brukt 3 ganger. Dermed 48·1 + 95·2 + 54·3 = 400. Det ideelle hadde vært at hver indeks ble brukt nøyaktig to ganger. Men det vi fikk her er likevel ganske bra.

Med n = 193, 199 og 211 ble det ikke så bra. Da kommer flg. utskrift:

  n = 193 : [33, 48, 44, 24, 28, 16]
  n = 199 : [30, 38, 38, 86, 7]
  n = 211 : [48, 44, 44, 40, 27, 8]

Oppgave 3

  n = 193 : [15, 58, 48, 46, 22, 4]
  n = 197 : [8, 54, 72, 54, 5, 4]
  n = 199 : [39, 40, 47, 39, 22, 11, 1]
  n = 211 : [39, 45, 55, 43, 29]

Oppgave 4

  n = 193 : [31, 36, 50, 40, 36]
  n = 197 : [5, 42, 96, 50, 4]
  n = 199 : [0, 40, 119, 38, 2]
  n = 211 : [0, 66, 102, 42, 1]

Oppgave 5

  if (k < 0) k = ~k;

Oppgave 6

  System.out.println(-1 % 3);  // Utskrift: -1
  System.out.println(Integer.remainderUnsigned(-1, 3));  // Utskrift: 0

Den siste utskriften sier at siden resten er 0, må 3 gå opp i -1. Men det er ikke -1 lenger. Det er det tallet der alle (32) bitene er 1-biter. Det er tallet 2³² - 1 = 4294967295. Kunne vi på forhånd ha funnet ut at 3 går opp i dette tallet? Ja! Tredje kvadratsetning sier at 2³² - 1 = (2¹⁶ - 1)(2¹⁶ + 1), osv til (2² - 1)(2² + 1)(2⁴ + 1)(2⁸ + 1)(2¹⁶ + 1). Men (2² - 1) = 3. Dermed går 3 opp.

Oppgave 7

  int h = hash("ABC", 10, 3.14);
  System.out.println(h);  // Utskrift: 362153214