# Hashtabelle mit Liste zur Kollisionsehandlung



## StangelLata (25. Mai 2018)

Hallo!
Ich sitze schon seit längerem an einer Aufgabe, die ich diese Woche noch erledigen muss. Es geht um folgendes: 
Aufgabe ist es eine Klasse SongTable (eine Hashtabelle) zu erstellen, welche folgende Methoden implementiert: 
- void add(Song song) 
- Song lookupTitle(String titel) 
- String toString() 
- void print() 
mit einem Verhalten wie in der Klasse SongTree
toString und print können Songs in beliebiger Reihenfolge anordnen 
- Hash-Tabelle:  eine fixe Größe (im Konstruktor), Kollisionsbehandlung eine einfach verkettete Liste. 
Eingefügt werden darf überall.

Probleme habe ich insbesondere bei der Kollisionsbehandlung mittels Liste und bei der Implementierung der Methoden!
Ich hoffe ihr könnt helfen!
MfG
Lars


```
public class SongTable{
    private String [] ks;
    private Song[] vs;
    private int count = 0;
    SongTable(int n){
        ks = new String[n];
        vs = new Song[n];
    }



    void add(Song s){

    }
    private int find(String k){
        if (k == null) return ks.length - 1;
        int i = hashCode() & (ks.length - 2);
        while (ks[i] != null && !ks[i].equals(k))
            i = (i+1) & (ks.length - 2);
        return i;
    }

    public boolean containsKey(String k){
        return ks[find(k)]!=null;
    }

    public Song get(String k) {
        return vs[find(k)];
    }

    public boolean equals(Object o){
        if (this == o){ return true;}
        if (o == null || o.getClass() != SongTable.class){
            return false;
        }
        SongTable s = (SongTable)o;
        if (count != s.count) return false;
        for (int i = 0; i < ks.length-1; i++){
            if (ks[i] != null && (vs[i] == null ? !s.containsKey(ks[i])||s.get(ks[i])!=null : !vs[i].equals(s.get(ks[i]))))
                return false;
        }
        return true;
    }

    public int hashCode(){
        int h = count;
        for (int i = 0; i <ks.length-1 ; i++) {
            if (ks[i] != null){
                h+=ks[i].hashCode();
                if (vs[i] != null){
                    h += vs[i].hashCode();
                }
            }
        }
        return h;
    }

    String put (String k, Song v){
        if (k == null) {
            return null;
        }
        int i = find(k);
        vs[i] = v;
        return null;
    }
    Song lookupTitle(String title){
        return null;
    }

    @Override
    public String toString() {
        return super.toString();
    }

    void print(){}

}
```


```
public class Song {

    private String titel;
    private String band;
    private int laenge;

    Song(String titel, String band, int laenge){
        this.titel = titel;
        this.band = band;
        this.laenge = laenge;
    }



    public int getLaenge() {
        return laenge;
    }


    public String getBand() {
        return band;
    }


    public String getTitel() {
        return titel;
    }

    public void print(){
            System.out.println(getBand() + ": " + getTitel() + " (" + getLaenge() + "s)");
    }

    public String toString() {
        return getBand() + ": " + getTitel() + " (" + getLaenge() + "s)"+'\n';
    }
}
```


```
import java.util.Iterator;

public class SongTree implements SongIterable {
    private TreeNode root;
    SongTree(){}

    public  void add(Song s){
        if (root == null){
            root = new TreeNode(s);
        }else {
            root.add(s);
        }
    }


    public void print(){
        root.printInOrder(root);
    }


    public Song lookupTitle(String title){
        if (root.searchRecursive(root, title)!=null){
            root.searchRecursive(root, title).print();
            return  root.searchRecursive(root, title);
        }else {
            System.out.println(""+null);
            return null;
        }
       // return  root.searchIterative(root, title);
    }

   

    long sum = 0;

    public void setSum(long sum) {
        this.sum = sum;
    }

    public long getSum() {
        return sum;
    }

    public long getLaenge(){
        return sumLength(root);
    }

    public long sumLength(TreeNode node){
        if (node == null){
            return 0;
        }else {
            return node.song.getLaenge() + sumLength(node.getLeft()) + sumLength(node.getRight());
        }
    }


    @Override
    public Iterator iterator() {
        return null;
    }
}
```


```
public class TreeNode {
    public  Song song;
    public  TreeNode left, right;

    public TreeNode(){}

    public TreeNode(Song song){
        this.song = song;
    }


    public void add(Song s){
        if (s.getTitel().compareTo(song.getTitel())<=0){
            if (left != null){
                left.add(s);
            } else {
                left = new TreeNode(s);
            }
        }else if (s.getTitel().compareTo(song.getTitel())>0){
            if (right != null){
                right.add(s);
            }else {
                right = new TreeNode(s);
            }
        }
    }

    public void printInOrder(TreeNode root){
        if (root.getLeft() != null){
            printInOrder(root.getLeft());
        }
        root.song.print();
        if (root.getRight()!= null){
            printInOrder(root.getRight());
        }
    }

    public TreeNode getLeft() {
        return left;
    }

    public TreeNode getRight() {
        return right;
    }

    public Song searchRecursive(TreeNode node, String title){
        if (node == null){
            return null;
        }
        if (node.song.getTitel().compareTo(title) == 0){
            return node.song;
        }else if(node.song.getTitel().compareTo(title)<0){
            return searchRecursive(node.getRight(), title);
        }else {
            return searchRecursive(node.getLeft(), title);
        }
    }

    public Song searchIterative(TreeNode node, String title){

        while (node != null && node.song.getTitel().compareTo(title) != 0){
            if (node.song.getTitel().compareTo(title) > 0){
                node = node.left;
            }else {
                node = node.right;
            }
        }
        if (node == null){
            return null;
        }else {
            return node.song;
        }
    }
    }
```


----------



## Javinner (25. Mai 2018)

@StangelLata 
Eventuell bin ich einfach blind, aber ich sehe nirgends die besagte Hashtable in deinem Code..
Schau dir das Beispiel von Hashtable an.


----------



## httpdigest (25. Mai 2018)

@Javinner: Ich denke mal, dass SongTable die Hashtabelle sein soll, wie ja auch in der Beschreibung geschrieben.
@StangelLata:


> int i = hashCode() & (ks.length - 2);


Überlege hier noch mal ganz genau, wovon du eigentlich den hashCode() berechnen möchtest, wenn man in deiner Tabelle einen Eintrag finden möchte...
Hint: Ich fand es schon mehr als merkwürdig, warum du dir die Mühe gemacht hast, der SongTable eine hashCode() Methode zu spendieren. Ist eigentlich nicht notwendig/gefordert.


----------

