Gruppe N+1
Fra Hiofwiki
[rediger]
Best viewed in Firefox
[rediger]
Oppgave 7.1.1
[rediger]
Heltallsdivisjon & linked chaining
Tabellstørrelse:11
Heltallsdivisjon med tabellstørrelsen gir;
34%11=1 45%11=1 3%11=3 87%11=10 65%11=10 32%11=10 1%11=1 12%11=1 17%11=6
_____
| |
0| |
|_____| _____ _____ _____
| | | | | | | |
1| 34 |->| 45 |->| 1 |->| 12 |
|_____| |_____| |_____| |_____|
| |
2| |
|_____|
| |
3| 3 |
|_____|
| |
4| |
|_____|
| |
5| |
|_____|
| |
6| 17 |
|_____|
| |
7| |
|_____|
| |
8| |
|_____|
| |
9| |
|_____| _____ _____
| | | | | |
10| 87 |->| 65 |->| 32 |
|_____| |_____| |_____|
[rediger]
Oppgave 7.1.2
[rediger]
Heltallsdivisjon & array chaining
Tabell størrelse: 20
34%11=1 45%11=1 3%11=3 87%11=10 65%11=10 32%11=10 1%11=1 12%11=1 17%11=6
_____ _____
| | |
0| | |
|_____|_____|
| | |
1| 34 | 11 |
|_____|_____|
| | |
2| | |
|_____|_____|
| | |
3| 3 | |
|_____|_____|
| | |
4| | |
|_____|_____|
| | |
5| | |
|_____|_____|
| | |
6| 17 | |
|_____|_____|
| | |
7| | |
|_____|_____|
| | |
8| | |
|_____|_____|
| | |
9| | |
|_____|_____|
| | |
10| 87 | 12 |
|_____|_____|_________________
| | |
11| 45 | 14 | Overflow area
|_____|_____|
| | |
12| 65 | 13 |
|_____|_____|
| | |
13| 32 | |
|_____|_____|
| | |
14| 1 | 15 |
|_____|_____|
| | |
15| 12 | |
|_____|_____|
| | |
16| | |
|_____|_____|
| | |
17| | |
|_____|_____|
| | |
18| | |
|_____|_____|
| | |
19| | | Overflow area
|_____|_____|_________________
[rediger]
Oppgave 7.1.3
[rediger]
Open addressing, linear probing
Tabell størrelse: 17
Heltallsdivisjon med tabellstørrelsen gir;
34%17=0 45%17=11 3%17=3 87%17=2 65%17=2 32%17=15 1%17=1 12%17=12 17%17=0
_____
| |
0| 34 | (p+1)%tab.length -> opptatt? -> (p+2)%tab.length -> osv
|_____|
| |
1| 1 | 17:(0+1)%17=1-> (0+2)%17=2 -> (0+3)%17=3 -> (0+4)%17=4 -> (0+5)%17=5
|_____|
| |
2| 87 | 65: (2+1)%17=3 -> (2+2)%17=4
|_____|
| |
3| 3 |
|_____|
| |
4| 65 |
|_____|
| |
5| 17 |
|_____|
| |
6| |
|_____|
| |
7| |
|_____|
| |
8| |
|_____|
| |
9| |
|_____|
| |
10| |
|_____|
| |
11| 45 |
|_____|
| |
12| 12 |
|_____|
| |
13| |
|_____|
| |
14| |
|_____|
| |
15| 32 |
|_____|
| |
16| |
|_____|
[rediger]
Oppgave 7.1.4
[rediger]
Open addressing, quadric probing
Tabell størrelse: 17
verdi:34, 45, 3, 87, 65, 32, 1, 12, 17
Heltallsdivisjon med tabellstørrelsen gir:
34%17=0 45%17=11 3%17=3 87%17=2 65%17=2 32%17=15 1%17=1 12%17=12 17%17=0
_____
| | new hashcode(x) = hashcode(x) + (-1)^i-1 * ((i+1)/2)^2 , 1<i<(tab.length-1)
0| 34 | ny hashkode(17) = 0 + (-1)^1-1 * ((1+1)/2)^2 = 1
|_____| ny hashkode(17) = 0 + (-1)^2-1 * ((2+1)/2)^2 = -1 -> -1%17=1
| | ny hashkode(17) = 0 + (-1)^3-1 * ((3+1)/2)^2 = 4
1| 65 | ny hashkode(1) = 1 + (-1)^1-1 * ((1+1)/2)^2 = 2
|_____| ny hashkode(1) = 1 + (-1)^2-1 * ((2+1)/2)^2 = 0
| | ny hashkode(1) = 1 + (-1)^3-1 * ((3+1)/2)^2 = 5
2| 87 | ny hashkode(65) = 2 + (-1)^1-1 * ((1+1)/2)^2 = 3
|_____| ny hashkode(65) = 2 + (-1)^2-1 * ((2+1)/2)^2 = 1
| |
3| 3 |
|_____|
| |
4| 17 |
|_____|
| |
5| 1 |
|_____|
| |
6| |
|_____|
| |
7| |
|_____|
| |
8| |
|_____|
| |
9| |
|_____|
| |
10| | ny hashkode(65) = 10 + (-1)^1-1 * ((1+1)/2)^2 =11
|_____| ny hashkode(32) = 10 + (-1)^1-1 * ((1+1)/2)^2 =11
| | ny hashkode(32) = 10 + (-1)^2-1 * ((2+1)/2)^2 =9
11| 45 |
|_____|
| |
12| 12 |
|_____|
| |
13| |
|_____|
| |
14| |
|_____|
| |
15| 32 |
|_____|
| |
16| |
|_____|
[rediger]
Oppgave 7.1.5
[rediger]
Double hashing (first digit extraction)
Tabell størrelse: 17
verdi:34, 45, 3, 87, 65, 32, 1, 12, 17
Heltallsdivisjon med tabellstørrelsen gir;
34%17=0 45%17=11 3%17=3 87%17=2 65%17=2 32%17=15 1%17=1 12%17=12 17%17=0
_____
| |
0| 34 | 17: 0 + 1 = 1%17=1 -> 0 + 2*1 = 2%17=2 -> 0 + 3*1 = 3%17=3 -> 0 + 4*1 = 4%17=4
|_____|
| |
1| 17 |
|_____|
| |
2| 87 | 65: 10 + 6=16%17=16
|_____|
| |
3| 3 |
|_____|
| |
4| 17 |
|_____|
| |
5| |
|_____|
| |
6| |
|_____|
| |
7| |
|_____|
| |
8| |
|_____|
| |
9| |
|_____|
| |
10| |
|_____|
| |
11| 45 |
|_____|
| |
12| 12 |
|_____|
| |
13| |
|_____|
| |
14| |
|_____|
| |
15| 32 |
|_____|
| |
16| 65 |
|_____|
| |
17| |
|_____|
[rediger]
Oppgave 7.2
import java.util.*;
public class LinkedHash
{
static LinkedList<String>[] hash;
public static void LagLinkedHash()
{
hash = (LinkedList<String>[])new LinkedList[26];
for(int i=0; i<26; i++)
hash[i] = new LinkedList<String>();
}
public static void leggTil(String s){
int pos = s.toUpperCase().charAt(0) - 65;
hash[pos].add(s);
}
public static void SkrivUt(){
for(int i=0; i<hash.length;i++){
System.out.println(hash[i]);
}
}
public static void main(String[] args) {
LagLinkedHash();
leggTil("Amanda");
leggTil("Per");
leggTil("ole");
leggTil("Bertha");
leggTil("anne");
leggTil("Andreas");
SkrivUt();
}
}
[rediger]
Oppgave 7.2
import java.util.Random;
import java.util.*;
public class KollisjonTeller {
private static int ant;
private static int tablengde;
static boolean[] KollisjonTab = new boolean[tablengde];
static int koll = 0;
public static int hash1(int n){
return n%tablengde;
}
public static int hash2(int n){
int res = (int) ((n % tablengde) * 1.5);
return res%2;
}
public static void setFalse(boolean[] tab){
for(int i = 0; i <= tab.length; i++){
tab[i]= false;
}
}
public static int LagRandom(int n){
Random generator = new Random();
int element = (generator.nextInt(n))+1;
return element;
}
public static int getLinear(int tall){
int i = hash1(tall);
koll = 0;
while(KollisjonTab[i])
{
koll++;
i++;
if(i == tablengde)
i=0;
}
KollisjonTab[i] = true;
return i;
}
public static int getKvadratisk(int tall){
int i = hash1(tall);
koll = 0;
while(KollisjonTab[i])
{
koll++;
double p = (int)Math.pow((double)koll,2.0);
i = (int)p+i;
if(i == tablengde)
i=0;
}
KollisjonTab[i] = true;
return i;
}
public static int getDoubleHash(int tall){
int i = hash1(tall);
koll = 0;
System.out.println(i);
if(KollisjonTab[i]){
i = hash2(tall);
koll++;
if(KollisjonTab[i]){
i = i + hash1(tall);
koll++;
while(KollisjonTab[i]){
i = i + (koll*(hash2(tall)));
koll++;
}
}
}
KollisjonTab[i] = true;
return i;
}
public static void main(String[] args) {
//ant = Integer.parseInt(args[0]);
ant = 4;
//tablengde = Integer.parseInt(args[1]);
tablengde = 6;
ArrayList<Integer> random = new ArrayList<Integer>();
for(int i=0; i<tablengde; i++)
random.add(LagRandom(ant));
int k =0;
setFalse(KollisjonTab);
for(int j=0; j<=random.size(); j++){
k = getLinear(random.get(j));
System.out.print(k + ", " );
}
System.out.println("Antall kollisjoner ved lineærsøk: " + koll);
setFalse(KollisjonTab);
for(int j=0; j<=random.size(); j++){
k = getKvadratisk(random.get(j));
System.out.print(k + ", " );
}
System.out.println("Antall kollisjoner ved kvadratisk søk: " + koll);
setFalse(KollisjonTab);
for(int j=0; j<=random.size(); j++){
k = getDoubleHash(random.get(j));
System.out.print(k + ", " );
}
System.out.println("Antall kollisjoner ved DoubleHash: " + koll);
}
}
