arrays verdoppeln dynamische haschtable

[maxhd2]

ich muss eine hashtable bauen die sich bei 50%belegung verdoppelt
leider tut sie das nicht, mist! bitte helft mir den fehler zu finden.

import java.lang.Math;

public class hash {

	private int[] table;
	private int size, size2, count;
	private static int marker = Integer.MIN_VALUE;
	private int[] doppel;

	public hash( int size) {

		if (size <4)// minimale haschtablegroesse 5
		size=4;


		 for(boolean isPrim=false; isPrim !=true; ++size) //size muss eine primzahl sein
		 {
		  int maxteiler= (int) Math.sqrt(size+1);

			  for(int teiler=2; (teiler<= maxteiler) || !isPrim ; teiler++)
			  {
				  if(size%teiler==0){ isPrim= false;  //wenn rest 0 ist dann ist es keine primzahl
				  break;}  // daher wird innere schleife abgebrochen

			  }
			  isPrim=true;

		 }



	this.size = size;
	this.table = new int[size];
	for(int i=0; i<size; i++)
		table[i]=marker;

	}

	public void add (int value) {
	add(value, size, table);}


	public void add (int value,int groesse, int[] c) {
		int pos2=0;
		int pos=0;
		boolean done = false;

		pos = value%groesse;

		if (count>=groesse/2){count=0; verdopple();}

			if(c[pos]==marker) { //wenn platz frei
				c[pos]=value;
				++count;
				return;}

			else{
				for(int i=pos;pos2==pos ;++i){
					pos2= i%groesse;
					if(c[i]==marker) {
						c[i]=value;
						done=true;
						++count;
						return;}
				}//ende for

				if (!done){
					verdopple();
					add(value);}
		}//ende else

	}


	private void verdopple(){

	size2=2*this.size;

	for(boolean isPrim=false; isPrim !=true; ++size2) //size muss eine primzahl sein
		 {
		 int maxteiler= (int) Math.sqrt(size2+1);

			  for(int teiler=2; (teiler<= maxteiler) || !isPrim ; teiler++)
			  {
				  if(size2%teiler==0){ isPrim= false;  //wenn rest 0 ist dann ist es keine primzahl
				  break;}  // daher wird innere schleife abgebrochen

			  }
			  isPrim=true;

		 }

		this.doppel= new int[size2];
		for(int i=0; i<size2; i++)
		doppel[i]=marker;



		for(int i=0;i<size;i++){
		int wert = table[i];
		if(wert !=marker) add(wert,size2,doppel);



		}
	this.table=this.doppel;
	}


	public void show() {
	for (int i=0; i<size;i++){
	System.out.print("\t"+table[i]);}
	//for (int i=0; i<size2;i++){
	//System.out.print("tabelle2\t"+doppel[i]);}
	}

}

public class Bsp10 {

	public static void main (String [] args) {

	hash tabelle = new hash(10);

	for (int i=0; i<9; i++){
	tabelle.add(i);}
	tabelle.show();
}
}

 

[schnuffie]

private int size = 0;
private int[] ai = new int[1];
private void doppel() {
if (size >= (ai.length >> 1)) {
int[] aiTemp = ai;
ai = new int[size << 1];
for (int i = 0; i < aiTemp.length; i++) {
ai[i] = aiTemp[i];
}
}
}

Bei jeder Hinzufüge-Methode führst Du diese Methode vorher aus und inkrementierst nach dem Hinzufügen einfach die Variable size.

 

[Thomas Darimont]

Hallo!

size << 1

Bitte verwende in deinen Beispielen einfachen code ... ;-) die meisten Leute können eben mit 2*size mehr anfangen als size << 1... falls das ganze unter dem Aspekt "Optimierung" laufen sollte, kann ich nur zitieren:

Premature Optimization is the root of ALL evil!

(Donald Knuth)

Gruß Tom

 

[schnuffie]

Damit hast Du schon Recht Tom, man könnte auch size*2 schreiben.

Wenn ich mir allerdings so manche Beispiele von Dir durchschaue, sind die weit weniger für Java-Einsteiger geeignet. :-(

 

[Thomas Darimont]

Hallo!

Wenn ich mir allerdings so manche Beispiele von Dir durchschaue, sind die weit weniger für Java-Einsteiger geeignet.

So? Bisher hat sich da noch nie jemand beschwert... *duckandrun* ;-)

Gruß Tom