Weil element nie null ist, warum ist das so? Dazu musst du uns noch sagen was liste ist oder was hash() macht.Warum liefert die immer true?
Hab noch nicht so recht nen Plan, aber: was ist denn hash() für eine Methode? Was macht die mit value?
[JAVA=2]int hash = hash(value);[/code]
private int hash(int x) {
int m = n - 1; // Something's wrong. Can you see what? x_X
return x % m;
}
Das wird sich schon nicht kompilieren lassen, weil du n nirgendwo deklarierstJava:private int hash(int x) { int m = n - 1; // Something's wrong. Can you see what? x_X return x % m; }
Ich weiß ja nicht genau, was du vorhast, aber wäre es nicht u.U. sinnvoller, gleich die eingebaute hashCode()-Methode zu überschreiben?Naja, vom Prinzip her soll hash(int) irgendwann die Hashfunktion sein.
ich würde mal den ganzen code posten... sonst dauert das noch die ganze nacht...
package blatt7_aufgabe1;
import java.util.LinkedList;
public class MyHashSet implements HashInterface {
int n;
LinkedList<Integer> list = new LinkedList<Integer>();
public MyHashSet(int size) {
n = size;
for(int i = 0; i < n; i++) {
list.add(null); // Generating n buckets... is that right?
}
}
private int hash(int x) {
int m = n - 1; // Something's wrong. Can you see what? x_X
return x % m;
}
public void insert(int value) {
if (!(hasValue(value))) {
list.remove(hash(value));
list.add(hash(value), value);
}
}
public void delete(int value) {
if (hasValue(value)) {
list.remove(hash(value));
}
}
public boolean hasValue(int value) {
int hash = hash(value);
Integer element = list.get(hash);
//return (element != null);
if (element == null)
return false;
else
return true;
}
public double[] statistics() {
// needs implementation desperately...
return null;
}
}
Funzt bei mir eig. ohne Probleme.
Zeig mal deinen Testcode.
package blatt7_aufgabe1;
public class TestHashSet {
public static void main(String[] args) {
int n = 10000;
MyHashSet myHashSet = new MyHashSet(n);
for(int i = 0; i < n; i++) {
myHashSet.insert(i);
}
/*
System.out.print("minimale Kollisionsliste:"+hashSet.statistics()[0]);
System.out.print("maximale Kollisionsliste:"+hashSet.statistics()[1]);
System.out.print("Mittelwert Kollisionslänge:"+hashSet.statistics()[2]);
System.out.print("Standardabweichung Kollisionslänge:"+hashSet.statistics()[3]);
*/
System.out.println(myHashSet.hasValue(1234));
System.out.println(myHashSet.hasValue(0));
System.out.println(myHashSet.hasValue(9999));
System.out.println(myHashSet.hasValue(10000));
System.out.println(myHashSet.hasValue(10001));
System.out.println(myHashSet.hasValue(20001));
}
}
ja// Generating n buckets... is that right?
mhn ok...// Something's wrong. Can you see what? x_X
public void print(){
for(int i = 0; i < list.size(); i++)
System.out.println(i+" "+list.get(i));
}
public static void main(String[] args) {
MyHashSet set = new MyHashSet(5);
System.out.println(set.hasValue(3));
set.insert(2);
set.insert(3);
set.insert(4);
set.insert(5);
set.print();
}
0 5
1 null
2 2
3 3
4 4
hier musst du aufpassen..
list.remove(hash(value));
achtung... du vernichtest dein bucket. also wenn du remove machst und du hast 2, 3, 4 drinnen, machst ein remove auf 3 dann ist 4 anstelle von 3... du willst eher 3 auf null setzen..
Also du füllst dein komplettes Hashset, hast ne Hashfunktion die dir lediglich mit modulo die hashs berechnet. Und dann kommts dir komisch vor dass alle prüfungen auf hasValue true ergeben?
EDIT:
Du solltest anstatt der Liste ne Map<Integer, Integer> nehmen und die Hashfunktion gegen eine geignetere (z.b. von Eclipse generierte) austauschen, dann solltest du weniger Kollisionen haben und deine Tests sollten hinhaun
package blatt7_aufgabe1;
import java.util.LinkedList;
public class MyHashSet implements HashInterface {
int n;
Object[] array;
public MyHashSet(int size) {
n = size;
for(int i = 0; i < n; i++) {
array[i] = null;
}
}
private int hash(int x) {
int m = n; // Something's wrong. Can you see what? x_X
return x % m;
}
public void insert(int value) {
if (!(hasValue(value))) {
array[hash(value)] = value;
}
else if (hasValue(value)) {
LinkedList<Integer> foo = new LinkedList();
foo.add(value);
// TODO write foo into the array
}
}
public void delete(int value) {
/*if (hasValue(value)) {
list.remove(hash(value));
}*/
}
public boolean hasValue(int value) {
Object element = array[hash(value)];
if (element == null)
return false;
/* if (element an Integer)
* if (element == value)
* return true;
* else if (element a LinkedList<Integer>)
* if (element.contains(value)
* return true;
* else
* return false;
*/
}
public double[] statistics() {
// needs implementation desperately...
return null;
}
}
Erstmal zum warum:Ich hab mir jetzt mal gedacht, dass ich ein array mache, wo LinkedList<Integer>'s drin sind und Integer. Bloß weiß ich nicht, wie ich das abfragen soll. Und warum soll ich 'ne Map nehmen? Das kenn' ich gar nicht. Wie funktioniert das?
Erstmal zum warum:
Du hast in deinem Array n mögliche Keys. Wenn du deine Hashfunktion auf die keys (0...n-1) abbildest dann bekommst du sehr viele Kollisionen , und das ist in ner hashmap immer mist.
Nimmst du ne Map<Integer, Integer> dann hast du als möglichen Wertebereich den Wertebereich Integer.MIN_VALUE bis Integer.MAX_VALUE. Mit ner geschickten Hashfunktion kannst du damit dann deine anzahl an Kollisionen verringern und bekommst somit auch genauere Werte bei hasValue.
Zur Anwendung:
einfach mal googlen
package blatt7_aufgabe1;
import java.util.LinkedList;
public class MyHashSet implements HashInterface {
int n;
LinkedList[] array;
public MyHashSet(int size) {
n = size;
array = new LinkedList[n];
for(int i = 0; i < n; i++) {
array[i] = null;
}
}
private int hash(int x) {
int m = n; // Something's wrong. Can you see what? x_X
return x % m;
}
public void insert(int value) {
if (!(hasValue(value))) {
if ((array[hash(value)]) != null)
array[hash(value)].add(value);
else {
array[hash(value)] = new LinkedList<Integer>();
array[hash(value)].add(value);
}
}
}
public void delete(int value) {
Integer valueObj = value;
if (hasValue(value)) {
array[(hash(value))].remove(valueObj);
}
}
public boolean hasValue(int value) {
LinkedList<Integer> list = array[hash(value)];
if (list != null)
return list.contains(value);
return false;
}
public double[] statistics() {
double min_size = Integer.MAX_VALUE, max_size = 0, mean_size = 0, deviation = 0;
for(int i = 0; i < n; i++) {
if (array[i] != null) {
int size = array[i].size();
if (size < min_size)
min_size = size;
if (size > max_size)
max_size = size;
mean_size += size;
}
}
mean_size /= n;
for (int i = 0; i < n; i++) {
if (array[i] != null) {
int size = array[i].size();
deviation += Math.pow(size - mean_size, 2);
}
}
deviation /= n;
deviation = Math.sqrt(deviation);
double[] result = new double[4];
result[0] = min_size;
result[1] = max_size;
result[2] = mean_size;
result[3] = deviation;
return result;
}
}
Nebenbei gesagt kräuseln sich mir bei
Java:if (element == null) return false; else return true;
die Fußnägel. Das schreibt man so:
Java:return element != null;
Ja, ich weiß, das ist ziemlich hässlich, aber darüber steht ja auskommentiert dasselbe, was du wolltest. Ich war mir nur kurz mal nicht sicher, weil irgendwie gar nichts ging, und hab' dann erstmal foolproof getestet.