c++ doubleHashing add
-
Nachdem ich schon einiges an Arbeit in mein DoubleHashing Verfahren investiert habe, bringt mich die add-Methode jetzt zum verzweifeln.
Ich hoffe, dass ich den logischen Verlauf des Einfügens beim Double Hashing richtig verstanden habe.
Erklärung:
key = speichert immer den HashValue
element = den Werte
status = (0= nicht belegt), (1= belegt)Mein Problem besteht darin, dass ein Wert eingefügt wird und dieser gleich dreimal und danach ist Schluss.
bzw. dürfte ich irgendwo, ich bin mir nicht sicher an welcher Stelle mit einem operator == einen nicht initalisierten Wert vergleichen.Für die Komplexität entschuldige ich mich jetzt schon.
Ich hoffe darauf, dass mir irgendjemand helfen kann, weil schön langsam glaube ich mir ist nicht mehr zu helfen.
template<typename E> void DoubleHashing<E>::add(const E e[], size_t len) { size_t newMax = maxV; size_t newArray = newMax; unsigned int temp = 0; size_t uebergabe; for(size_t i=0; i<len; i++) { if(!member(e[i])) { if((entries + len) > (maxV*0.7)) { HashElements *expand; while((entries+len) > (newMax*0.7)) { newMax = size_t((maxV*1.2)+2); } expand = new HashElements[newMax]; for(size_t k=0; k<maxV; ++k) { temp = value[k].key % newMax; if(value[k].status != 0) { if(expand[temp].status == 0) { expand[temp].fill(value[k].element, value[k].key); expand[temp].status = 1; break; } if(expand[temp].status != 0) { size_t doubleha = value[k].key % newMax; size_t lastPosition = value[k].key%10; size_t anfang = ((doubleha+(lastPosition*3))%newMax); doubleha = ((doubleha+(lastPosition*3))%newMax); if(expand[doubleha].status == 0) { expand[doubleha].fill(value[k].element, value[k].key); expand[doubleha].status = 1; break; } if(expand[doubleha].status != 0) { doubleha = ((doubleha+(lastPosition*3))%newMax); for(; doubleha < newMax; doubleha = ((doubleha+(lastPosition*3))%newMax)) { if(expand[doubleha].status == 0) { expand[doubleha].fill(value[k].element, value[k].key); expand[doubleha].status = 1; break; } if(anfang == doubleha) { HashElements *bigger; uebergabe = 1; newArray = size_t ((newMax*1.2)+2); bigger = new HashElements[newArray]; size_t zweiteFunk= value[k].key % newMax; /* * expand an bigger uebergeben * */ for(size_t p=0; p<newMax; p++) { size_t firstKey; if(expand[p].status != 0) { firstKey = expand[p].key % newArray; if(bigger[firstKey].status == 0) { bigger[firstKey].fill(expand[p].element, expand[p].key); bigger[firstKey].status = 1; break; } if(bigger[firstKey].status == 1) { size_t secondKey = firstKey; size_t nnumber = expand[p].key % 10; secondKey = ((secondKey+(nnumber*3)) % newArray); size_t ursprung = secondKey; if(bigger[secondKey].status == 0) { bigger[secondKey].fill(expand[p].element, expand[p].key); bigger[secondKey].status = 1; break; } if(bigger[secondKey].status == 1) { secondKey = ((secondKey+(nnumber*3)) % newArray); while(secondKey != ursprung) { if(bigger[secondKey].status == 0) { bigger[secondKey].fill(expand[p].element, expand[p].key); bigger[secondKey].status = 1; break; } secondKey = ((secondKey+(nnumber*3)) % newArray); } } } } } /* * * Ende expand an bigger */ if(bigger[zweiteFunk].status == 0) { bigger[zweiteFunk].fill(value[k].element, value[k].key); } if(bigger[zweiteFunk].status != 0) { size_t letztePos = value[k].key%10; //size_t start = ((zweiteFunk+(letztePos*3))%newMax); zweiteFunk = ((zweiteFunk+(letztePos*3))%newArray); if(bigger[zweiteFunk].status == 0) { bigger[zweiteFunk].fill(value[k].element, value[k].key); } if(bigger[zweiteFunk].status == 1) { for(; zweiteFunk<newMax; zweiteFunk=((zweiteFunk+(letztePos*3))%newMax)) { if(bigger[zweiteFunk].status == 0) { bigger[zweiteFunk].fill(value[k].element, value[k].key); break; } } } } newMax = newArray; expand = bigger; delete[] bigger; } } } } } maxV = newMax; value = expand; delete[] expand; } } else { temp = hashValue(e[i])%maxV; if(value[temp].status == 0) { value[temp].fill(e[i], hashValue(e[i])); entries++; } if(value[temp].status!=0) { size_t hashfunc = hashValue(e[i])%maxV; size_t lastNumber = hashValue(e[i]) % 10; size_t begin = (hashfunc + (lastNumber*3)) % maxV; hashfunc = ((hashfunc +(lastNumber*3))%maxV); if (value[hashfunc].status == 0) { value[hashfunc].fill(e[i], hashValue(e[i])); value[hashfunc].status = 1; entries++; break; } if(value[hashfunc].status!=0) { hashfunc = ((hashfunc +(lastNumber*3))%maxV); for(; hashfunc < maxV; hashfunc = ((hashfunc +(lastNumber*3))%maxV)) { if(begin==hashfunc) { HashElements * greater; newMax = size_t ((maxV*1.2)+2); greater = new HashElements[newMax]; for(size_t j=0; j<maxV; ++j) { unsigned int tempkey = value[j].key%newMax; if(value[j].status != 0) { if(greater[tempkey].status == 0) { greater[tempkey].fill(value[j].element,value[j].key); greater[tempkey].status = 1; } if(greater[tempkey].status != 0) { hashfunc = value[j].key%newMax; lastNumber = hashValue(value[j].key) % 10; begin = (hashfunc + (lastNumber*3)) % newMax; hashfunc = ((hashfunc +(lastNumber*3))%newMax); for(; hashfunc < newMax; hashfunc = ((hashfunc +(lastNumber*3))%newMax)) { if(greater[hashfunc].status == 0) { greater[hashfunc].fill(value[j].element,value[j].key); break; } } } } } } if(value[hashfunc].status==0) { value[hashfunc].fill(e[i], hashValue(e[i])); entries++; break; } } maxV = newMax; } } } } } }
-
Komm refactor das mal in Funktionen <= 20 Zeilen, und dann poste es nochmal. Sauber eingerückt.
-
Vielleicht sollte man an dieser Stelle auch auf
std::unordered_maphinweisen
-
Der Menge der "open-addressing" Fragen nach zu schliessen die in letzter Zeit hier aufgetaucht sind ... ist der Fragesteller vermutlich weder in einer Situation wo er das produktiv einsetzen will, noch in einer wo er sich aussuchen kann ob er was fertiges nehmen will oder selbst schreiben
Oder die Fragestellerin, wenn man dem Geschlecht des Nicknames trauen darf.
