Index assoziation

SeppJ

Per Definition ist jeder Algorithmus, der aus einer Zeichenkette einen Integer errechnet ein Hash, denn ein Hash ist ein Algorithmus der eine große Eingabemenge auf eine kleine Zielmenge abbildet, was bei Zeichenketten und Integern gegeben ist.

P.S.: Wie kann ein Integer dezimal sein? Dieses Attribut macht in dem Zusammenhang keinen Sinn.

RussianTux

SeppJ schrieb:

Per Definition ist jeder Algorithmus, der aus einer Zeichenkette einen Integer errechnet ein Hash, denn ein Hash ist ein Algorithmus der eine große Eingabemenge auf eine kleine Zielmenge abbildet, was bei Zeichenketten und Integern gegeben ist.

Das Problem ist nur, dass ich lauter Information und Algorithmen im Web finde, aber überhaupt keine Ahnung davon habe, welcher denn nun der passende für mich wäre, das Ziel ist es zu Übungszwecken ohne die STL und std eine eigene Hashtabelle zu programmieren, der Algorithmus welcher Kollisionen vermeidet, damit man bestehende Daten nicht überschreibt oder sonstige Fehler macht wegen doppelter Hash Anbindung

SeppJ schrieb:

P.S.: Wie kann ein Integer dezimal sein? Dieses Attribut macht in dem Zusammenhang keinen Sinn.

Sry, es war eine Ganzzahl gemeint

SeppJ

Ganzzahl ist deutsch für Integer.

hustbaer

@RussianTux
Du hast hier drei bzw. vier Teilprobleme.

1: Die Hashfunktion. Google sollte ausreichend Informationen liefern was es da so alles für Strings gibt. Ist natürlich auch immer ein Tradeoff zwischen Geschwindigkeit und Qualität. Zur Not guck dir an was Boost.Hash mit Strings macht. Oder nimm Adler32.

2: Herausfinden ob es eine Kollision gegeben hat. Das löst man üblicherweise indem man in jedem Bucket (=Element des Arrays) nicht nur den Wert speichert, sondern auch eine Kopie des gesamten Keys. Ohne dass du den unveränderten Key zum Vergleich vorliegen hast *kannst* du nicht garantieren dass du nichts überschreibst.

3: Die Frage was du machst wenn eine Kollision auftritt. Da gibt es mehrere Möglichkeiten.

a: Du machst nix, d.h. du trägst den neuen Wert einfach nicht ein.

b: Du überschreibst den alten Key&Wert mit dem neuen Key&Wert.

c: Du machst aus jedem Bucket eine Liste, in der du alle kollidierenden Key/Wert Paare reintust.

d: Du verwendest "open addressing". D.h. du guckst nicht nur in einem Bucket nach, sondern durchsuchst der Reihe nach weitere, bis du ein freies findest. Dabei gibt es wieder mehrere Möglichkeiten wie man bei dieser Suche vorgeht. Die einfachste Variante ist immer um einen fixen Offset weiterzugehen ( i = (i + offset) module N - typischerweise mit offset == 1 ). Man kann auch den Offset nach jedem Versuch um eins vergrössern. Oder man kann den Offset mit einer zweiten sog. sekundären Hashfunktion berechnen ("double hashing").
Open addressing ist kuhl, allerdings ist das Entfernen von Keys nicht ganz trivial.

4: Sofern keine fixe Tablegrösse verwendet wird: Entscheiden wann du den Hashtable vergrösserst.
Die wohl üblichste Variante ist einen max. "Füllstand" festzulegen ("load factor"). D.h. wenn du 1000 Buckets hast erlaubst du z.B. 700 Einträge. Vor dem Einfügen des 701. Werts vergrösserst du den Hashtable.

krümelkacker

hustbaer schrieb:

Open addressing ist kuhl, allerdings ist das Entfernen von Keys nicht ganz trivial.

Ah, da habe ich noch gar nicht drüber nachgedacht bisher. Wie löst man das am geschicktesten? Für ein STL-ähnliches Design in C++, wo man die Werte direkt abspeichern wollen würde, bräuchten wir mindestens noch ein Flag, das sagt, ob ein Eintrag gültig ist. Das könnte man doch zu einem Zähler aufbohren, über den man sich zusätzlich merken könnte, wie viele andere Einträge im Feld gelandet wären, falls es nicht schon besetzt gewesen wäre. Das sollte das Problem eigentlich schon lösen können. Ich probiere das mal aus... ^^

volkard

krümelkacker schrieb:

hustbaer schrieb:

Open addressing ist kuhl, allerdings ist das Entfernen von Keys nicht ganz trivial.

Ah, da habe ich noch gar nicht drüber nachgedacht bisher. Wie löst man das am geschicktesten? Für ein STL-ähnliches Design in C++, wo man die Werte direkt abspeichern wollen würde, bräuchten wir mindestens noch ein Flag, das sagt, ob ein Eintrag gültig ist.

Oder einen unmöglichen key, was inbesondere bei Zeigern geht.

krümelkacker

volkard schrieb:

krümelkacker schrieb:

hustbaer schrieb:

Open addressing ist kuhl, allerdings ist das Entfernen von Keys nicht ganz trivial.

Ah, da habe ich noch gar nicht drüber nachgedacht bisher. Wie löst man das am geschicktesten? Für ein STL-ähnliches Design in C++, wo man die Werte direkt abspeichern wollen würde, bräuchten wir mindestens noch ein Flag, das sagt, ob ein Eintrag gültig ist.

Oder einen unmöglichen key, was inbesondere bei Zeigern geht.

Zumindest dann, wenn ein Nullzeiger kein gültiger Schlüssel sein muss. Ich habe jetzt eine Implementierung basierend auf "Lazy Deletion" gebaut. Da brauche ich 2 Bits extra pro Slot für einen von drei möglichen Zuständen:
(0) "end" (frei, hinter einem Clusters)
(1) "deleted" (frei, aber mitten in einem Cluster)
(2) "valid" (der Slot ist belegt durch ein valides value_type Objekt)

Beispiel: Ein 2er-Cluster (zwei aufeinanderfolgende Einträge)

+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 2 | 2 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+

Ich lösche den ersten:

+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 2 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+

und muss den Zustand auf "deleted" setzen, weil der zweite Eintrag ja auf den ersten hätte landen können und die Suche für den zweiten nicht abbrechen darf. Lösche ich noch den zweiten Eintrag, ist der "deleted"-Zustand überflüssig, da wir schon am Ende eines Clusters (der rechte Nachbar ist 0) sind:

+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+

Wir dürfen auch die 0 soweit nach links propagieren, bis wir wieder etwas anderes als "deleted" finden:

+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+

und sind in diesem Fall sogar alle deleted-Zustände los.

Mit dem von mir oben skizzierten Ansatz wäre das anders gelaufen. Da gibt es ein Flag frei/belegt und ein Zähler pro Slot, der sagt, wie oft ich da etwas speichern wollte. Falls wir bei den zwei Einträgen gar keine Hash-Kollision hatten, sähe das dann so aus:

+---+---+---+---+---+---+---+---+
| - | - | - | X | X | - | - | - |  Besetzt?
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |  Zaehler
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| - | - | - | - | X | - | - | - |  Besetzt?
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |  Zaehler
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| - | - | - | - | - | - | - | - |  Besetzt?
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |  Zaehler
+---+---+---+---+---+---+---+---+

Und im Kollisionsfall dann so

+---+---+---+---+---+---+---+---+
| - | - | - | X | X | - | - | - |  Besetzt?
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |  Zaehler
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| - | - | - | - | X | - | - | - |  Besetzt?
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |  Zaehler
+---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+
| - | - | - | - | - | - | - | - |  Besetzt?
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |  Zaehler
+---+---+---+---+---+---+---+---+

Die Suche nach einem Schlüssel hört auf, sobald ich einen 0-Zähler gefunden habe; dementsprechend ist der zweite Eintrag, nachdem der erste gelöscht wurde, noch auffindbar wegen der 1. Die Frage wär jetzt, bringt das was so? Ich weiß es nicht.

Ich habe jetzt beide Ansätze implementiert. Im Fall "Lazy ohne Zähler" lösche ich die Einträge bei erase(range_begin,range_end) rückwärts in der Hoffnung, dass sich so Cluster-Enden schneller propagieren.

Lustig lustig ... Hat mal wieder Spaß gemacht, das Proggen ... Ich konnte bei der Implementierung einiges aus C++11 verwenden: std::aligned_storage, alignof, static_assert, move semantics, perfect forwarding, ...

Hier mal ein paar Fragmente bzgl aligned_storage und der slot-Implementierung. Die C++11 Mittel machen das hier relativ sauber, was in C++98 bestimmt "hackiger" gewesen wäre ...

template<class AlignedStorageType>
struct slot
{
	enum slot_state {
	  end, deleted, valid
	};

	slot_state state;
	AlignedStorageType rawdata;

	slot() : state(end) {}

	bool is_valid()   const {return state==valid;}
	bool is_free()    const {return state!=valid;}
	bool is_end()     const {return state==end;}
	bool is_deleted() const {return state==deleted;}
	void set_end()     {state = end;}
	void set_deleted() {state = deleted;}
	void set_valid()   {state = valid;}
};

:::

template<class KeyType, class MappedType, class HashType>
class hash_map
{
  :::
  typedef std::pair<const KeyType, MappedType> value_type;
  :::
  MappedType& operator[](KeyType const& key)
  {
    ensure_room();
    auto idx = find_index_of_key(k);
    auto& slot = data_[idx];
    value_type* ptr = valueptr(slot);
    if (!slot.is_valid()) {
      new(ptr) value_type(k,MappedType());
      slot.set_valid();
      ++size_;
    }
    return ptr->second;
  }

  :::
private:
  typedef typename std::aligned_storage<sizeof(value_type),alignof(value_type)>::type ast;
  typedef slot<ast> slot_type;
  :::
  static_assert(sizeof(value_type)<=sizeof(slot_type::rawdata),"programming error");
  :::
  static value_type      * valueptr(slot_type      & s) {return reinterpret_cast<      value_type*>(&s.rawdata);}
  static value_type const* valueptr(slot_type const& s) {return reinterpret_cast<const value_type*>(&s.rawdata);}
  :::
  /// make sure that at least one slot is free
  void ensure_room();
  :::
  slot_type* data_;
  size_type num_slots_;
  size_type size_;
  HashType hfun_;
  :::
};

Besteht Interesse an dem Rest? Da ist fast alles bei, was std::unordered_map auch kann. Ausnahmen: Ich verzichtete auf einen Allocator, auf einen Equality-Funktor. Vielleicht fehlt auch noch mehr. K.A.

Schönes Wochenende noch!

volkard

Cluster? Mach die weg!

krümelkacker

"Cluster" nennt man "Elementhaufen ohne Lücken". Das lässt sich bei einer Tabelle, die zu 80% gefüllt ist, nicht vermeiden. Man kann die als Anwender natürlich größer machen (sofern es die Schnittstelle hergibt). Man kann eigentlich recht viel als Anwender reißen. Speichert man die Objekte direkt oder indirekt (per unique_ptr z.B.) in der Tabelle?. Hat alles Vor- und Nachteile. Ich find's aber nett, dass der open adressing-Ansatz dem Nutzer die Möglichkeit bietet, Kram direkt im Feld abzulegen, so wie es std::vector<> ja eigentlich auch macht. Beide kann ich immer noch mit T=unique_ptr<sowieso> instanzieren, wenn ich will.

volkard

krümelkacker schrieb:

"Cluster" nennt man "Elementhaufen ohne Lücken". Das lässt sich bei einer Tabelle, die zu 80% gefüllt ist, nicht vermeiden.

Sie lassen sich gar nicht vermeiden, fürchte ich. Daß man mal zwei- oder dreimal gucken muß, kommt halt vor. Unabhängig vom Füllstand.

Falls Du lineares Sondieren machst (ist doch so?), bekommst Du mit der Zeit laaange Cluster. Denn die Wahrscheinlichkeit, bei Einfügung auf einen langen Cluster zu treffen, ist um so größer, je länger der Cluster ist. Und dann wird er prompt ums eins verlängert. Also haben ausgerechnet die längsten Cluster die stärkste Tendelendenz, noch länger zu werden.

Und mir scheint, mit der "lazy deletion" verstärkst Du diese Tendelendenz sogar noch.

volkard

Irgendwie werde ich mit der lazy deletion nicht warm.
Ich finde, man sollte auf's Löschen verzichten.

(0) "end" (frei, hinter einem Clusters)
(1) "deleted" (frei, aber mitten in einem Cluster)
(2) "valid" (der Slot ist belegt durch ein valides value_type Objekt)

Da eh die Tendenz zu langen Clustern besteht, simuliere ich mal gleich einen.
insert 2 3 4 5 6 (egal in welcher Reihenfolge)

1   2   3   4   5   6   7   8
+---+---+---+---+---+---+---+---+
| 0 | 2 | 2 | 2 | 2 | 2 | 0 | 0 |
+---+---+---+---+---+---+---+---+

Und mache ihn weg.

delete 2 3 4 5 (egal in welcher Reihenfolge)

1   2   3   4   5   6   7   8
+---+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 1 | 1 | 2 | 0 | 0 |
+---+---+---+---+---+---+---+---+

Jetzt scheint mir, daß ein längerer Cluster eine recht geringe Wahrscheinlichkeit hat, die 0 bis nach vorne zu ziehen. Und innerhalb eines Clustern können keine neuen Nullen entstehen.

insert 7 8 0
delete 7 8 0

1   2   3   4   5   6   7   8
+---+---+---+---+---+---+---+---+
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+---+

krümelkacker

volkard schrieb:

Irgendwie werde ich mit der lazy deletion nicht warm.
Ich finde, man sollte auf's Löschen verzichten.

Das ist natürlich eine Möglichkeit. Oder Abundzu mal komplett neu Rehashen.

Die Tabelle so voll werden zu lassen, will ja keiner. Die sollte man vorher schon vergrößern. Aber so richtig toll gefällt mir das mit der lazy deletion auch nicht. Der Ansatz, den ich da skizziert hatte, ist glaub'ich weniger schlimmt. Da spielt die Zahl der Kollisionsn aber auch eine Rolle. Wenn es in Deinem Fall z.b. gar keine Kollisionen gegeben hat, gibt's auch keine Probleme und die Zähler bleiben die ganze Zeit auf 0. Beim Löschen musste ich da aber die Hashfunktion nochmal anschmeißen, damit ich wusste, welche Zähler ich zu modifizieren habe.

volkard

krümelkacker schrieb:

Die Tabelle so voll werden zu lassen, will ja keiner.

70% will keiner?

krümelkacker schrieb:

Da spielt die Zahl der Kollisionsn aber auch eine Rolle.

Und die Kollissionshäiufungen durch immer größer werdende Bereiche von Fehlbelegungen, die den richtigen Gästen ihr Zimmer weggeschnappt haben. Deswegen habe ich da auch bei 50% eine Heidenangst.

krümelkacker schrieb:

Wenn es in Deinem Fall z.b. gar keine Kollisionen gegeben hat, gibt's auch keine Probleme und die Zähler bleiben die ganze Zeit auf 0.

Ah, 4 Zustände oder beim Löschen auch nochmal hashen.

Und trotzdem.