Waar verantwoordelijkheden van hashen neerleggen

[Andre-85]

Ik zit met het volgende "probleem". Eigenlijk is het meer een design vraagstuk dan een probleem.

In mijn domein heb ik te maken met URI's die naar resources wijzen. Het zoeken in een relatief grote lijst naar een Uri was te traag. De meest voor de hand liggende methode om dit te optimaliseren was gebruik maken van een hash_map.

Eerst een versimpelde versie van de Uri

C++:

class Uri
{
public:
  //constructors / destructor

  //Getters/Setters

  bool operator==(const Uri &rhs)
  {
    return ((m_host == rhs.m_host) &&
              (m_port == rhs.m_port) &&
              (m_specifier == rhs.m_specifier));
  }

private:
  boost::asio::ip::address m_host;
  unsigned int m_port;
  std::string m_specifier;
};

Nu zit ik met het volgende design issue. Mijn Uri 'weet' wat het uniek maakt en weet dus wat er gehashed moet worden. Maar de Uri weet niks van hashen, welk algoritme te gebruiken voor een hash en het berekenen van de hash hoort mijns inziens niet in een Uri object thuis.

Oplossingen:
1) Doe niet moeilijk en geef Uri een Hash method doe daar het werk en klaar.
2) Creëer een "Hasher" class. Een Uri heeft een Hasher, Uri::Hash called wat methods op de Hasher om de hash te berekenen en geeft het resultaat terug.
3) Maak een HashableUri (die een Hasher heeft). De constructor heeft een Uri als parameter en de HashableUri heeft de Hash method.

Nadelen:
1) Lelijk, het hashen is niet geencapsuleerd, en een Hash method op een uri vind ik eigenlijk ook niet zo mooi...
2) Nog steeds een Hash method op een Uri...
3) De noodzaak om een Hashable.... te maken voor iedere class die ik wil kunnen hashen.... Hashable moet mogelijk friend van de te hashen class zijn.

Welke oplossingen zie ik nog over het hoofd? Het moet vast netter kunnen...

offtopic:
Btw als iemand een betere titel weet....

[MBV]

Wat is er raar aan een hash()-functie maken? Diverse java-api's vereisen dat zo'n soort functie aanwezig is, net als bijvoorbeeld equals(x) (in C++ zou dat operator==(x) zijn).

Sterker nog: jouw klasse moet het hashen zelf doen, omdat alleen jouw klasse weet wat zijn private members zijn! Hoe zou je het anders willen doen, een Hasher-interface maken met een HashUri subclass die moet worden gewijzigd zodra je een datamember toevoegt?
Daarnaast is die hash-functie ook nog eens een one-liner omdat je iets van boost kan gebruiken.

[Andre-85]

Nou mijn punt is dat mijn Uri class inderdaad als enige weet wat er gehasht moet worden, en ik het 'vreemd' vind dat de Uri class weet hoe er gehasht wordt. Ik heb er nu voor gekozen om dit met een 32bits crc berekening (boost::crc) te implementeren, maar het idee dat deze kennis in de Uri class zit voelt niet goed.

[icyx]

Die hash functionaliteit zou je eventueel via een instance, of een via een setter oid mee kunnen geven. Op die manier houd je toch je hash logica gescheiden van de rest.
Verder ben ik het met MBV eens dat het aangeven wat er gehasht moet worden juist specifiek een taak van je Uri class.

[frickY]

Dat zegt de TS toch ook? Hij valt alleen over hoe/waar er gehashed wordt.
Moet zijn Uri weten dat de applicatie crc32 gebruikt? Hoort dat niet hoger?

Wat mij betreft is het terecht dat dit knaagt.

[H!GHGuY]

Trouwens weet jou klasse ook beter welke hash te gebruiken.

Binary data en readable text hash je bvb liever niet met dezelfde hash functie want het resultaat zou wel eens kunnen tegenvallen. Ik ga dus akkoord met wat hierboven vermeld wordt.

Wil je alsnog alles mooi opsplitsen dan kun je volgende template-code gebruiken:

C++:

template<class T>
class HashGenerator
{
public:
  uint32_t GetHash(const T& t) { return t.GetHash(); }
}

template<>
class HashGenerator<std::string>
{
  public:
    uint32_t GetHash(const T& t) { /* std::string hash */ }
}
template<>
class HashGenerator<uint32_t>
{
  public:
    uint32_t GetHash(const T& t) { /* return t*/ }
}

class HashCombiner
{
  public:
    uint32_t Combine(uint32_t Hash) { m_Hash = /* doe iets met m_Hash en Hash, bvb m_Hash ^ Hash */; }
    uint32_t GetHash() { return m_Hash; }
  private:
  uint32_t m_Hash;
}

Eventueel kun je ook gewoon global template methods maken en als je meer configuratie opties wil kun je traits classes maken voor het type, bvb om binary vs text verschillend te behandelen.

Dat je class de hash-methode kiest, wil nog niet zeggen dat ie die methode moet implementeren.
Maw, implementeer je hash-classes apart, met een propere interface en laat je andere klassen dan adhv die interface de hash gebruiken en impliciet de correcte hash-implementatie gebruiken.

[ Voor 21% gewijzigd door H!GHGuY op 27-09-2010 21:10 ]

[icyx]

frickY schreef op maandag 27 september 2010 @ 20:58:
Dat zegt de TS toch ook? Hij valt alleen over hoe/waar er gehashed wordt.
Moet zijn Uri weten dat de applicatie crc32 gebruikt? Hoort dat niet hoger?

Wat mij betreft is het terecht dat dit knaagt.

Het is zeker terecht, maar ik denk dat je mij verkeerd begrepen heb. Ik bedoel namelijk hetzelfde als H!GHGuY. Wanneer je ergens je hash logic hebt onder gebracht (dus buiten die Uri class) kan je die extern aanspreken.
Maak bijvoorbeeld een hash functie met parameters (byte *data, int len, byte *hash, int &hashlen) oid, zodat het enige wat de Uri class doet is aangeven welke data er gehashd moet worden, en waar de result neergezet moet worden.
De oplossing mbv templates vind ik echter wel wat netter, maar het bovenstaande dient alleen maar ter verduidelijking wat ik bedoelde.

[Killemov]

Andre-85 schreef op maandag 27 september 2010 @ 20:00:
Nou mijn punt is dat mijn Uri class inderdaad als enige weet wat er gehasht moet worden, en ik het 'vreemd' vind dat de Uri class weet hoe er gehasht wordt. Ik heb er nu voor gekozen om dit met een 32bits crc berekening (boost::crc) te implementeren, maar het idee dat deze kennis in de Uri class zit voelt niet goed.

Aha, JIJ kiest er voor om een 32bits crc te gebruiken... stel dat je hash zou werken met ehm sprintf, moet dat er dan ook buiten? Lijkt me niet he?

In Java is het vrij gebruikelijk om zoiets als ( ( 31 * m_host + 31 ) * m_port + 31 ) * m_specifier als uitgangspunt te nemen.

Als je een UrlTree zou maken die weet welke velden er zijn, dan kun je alleen al met het opslaan/zoeken op basis van het veld waar het meeste variatie in zit relatief veel snelheidswinst boeken.

[Janoz]

Contract van een hash is dat hij, bij dezelfde relevante waarde van het object, dezelfde hash oplevert, en dat daarnaast de hash zoveel mogelijk verschilt. IMHO is het niet alleen de Uri class die weet welke velden voor de hash gebruikt moeten worden, maar ook weet hoe die hash zoveel mogelijk kan verschillen. IMHO kan de Uri class dus eigenlijk zelf het beste bepalen op welke manier de hash berekend zou moeten worden, en daarbij lijkt mij een complete crc library toevoegen een beetje overdreven. Als je uit gaat pluizen wat die lib daadwerkelijk met je input doet dan gaat dat redelijk lijken op de implementatie die Killemov al laat zien.

[Verwijderd]

Ik vind de 'Java' aanpak hier ook het best. Je implementeert daarbij de hash functie in de class zelf. De reden om hem daar te plaatsen (en dus de class er zelf voor verantwoordelijk maken) is simpelweg omdat alleen de class zelf weet welke combinatie van variabelen hem uniek maakt. Vooral bij iets als een URI lijkt het me ook niet moeilijk een combinatie van variabelen te vinden die het URI object uniek identificeert

[H!GHGuY]

Verwijderd schreef op zaterdag 02 oktober 2010 @ 14:51:
Ik vind de 'Java' aanpak hier ook het best. Je implementeert daarbij de hash functie in de class zelf. De reden om hem daar te plaatsen (en dus de class er zelf voor verantwoordelijk maken) is simpelweg omdat alleen de class zelf weet welke combinatie van variabelen hem uniek maakt. Vooral bij iets als een URI lijkt het me ook niet moeilijk een combinatie van variabelen te vinden die het URI object uniek identificeert

Dat is nu net wat ik met mijn post probeer te weerleggen.

Ik ben akkoord dat klassen een GetHash() mogen hebben, maar de implementatie van de hash zou ik dan weer overlaten aan andere meer gespecialiseerde klassen zoals in mijn voorbeeld.

[Haan]

De .NET manier (die vzv ik weet redelijk gelijk is aan de Java manier) vind ik anders wel prima. De Object class heeft een GetHashCode functie die een integer als hash teruggeeft. Dit betekent dus dat iedere class (aangezien elke class uiteindelijk van Object erft) altijd deze functie al heeft. Het is echter aan jou om de hash functie te overriden indien nodig. De documentatie geeft hierbij aan dat je daarvoor bijvoorbeeld gewoon een XOR operatie op (een aantal) instance velden kan gebruiken:

C#:

public class Foo
{
    SomeType a = new SomeType();
    AnotherType b = new AnotherType();
    LastType c = new LastType();

    public override int GetHashCode () 
    {
         return a.GetHashCode() ^ b.GetHashCode() ^ c.GetHashCode();
    }
}

Voor die ene regel heb je helemaal geen aparte Hash class nodig. Nu kan het zijn dat dit in C++ een heel ander verhaal is, maar in Java / .NET werkt dit prima zo.

[Janoz]

H!GHGuY schreef op zaterdag 02 oktober 2010 @ 17:46:
....maar de implementatie van de hash zou ik dan weer overlaten aan andere meer gespecialiseerde klassen zoals in mijn voorbeeld.

Waarom? Wat voor voordeel biedt een gespecialiseerde klasse? Een hash berekening is echt geen rocketsience.

[H!GHGuY]

Janoz schreef op zaterdag 02 oktober 2010 @ 22:45:
[...]

Waarom? Wat voor voordeel biedt een gespecialiseerde klasse? Een hash berekening is echt geen rocketsience.

Hashes zijn meer dan wat waarden XOR'en. Zoals ik al zei is de gekozen hash functie nauw verbonden aan de input.
Je gebruikt normaal niet dezelfde hash-functie om een executable te hashen als je zou gebruiken voor Unicode tekst of Nederlandse tekst. Hoewel ze allemaal sequences van karakters behandelen bestaat het input-domein bij een executable uit bytes met een redelijk uniforme verdeling over het ganse bereik, terwijl je bij Unicode strings of Nederlands tekst typisch het input-domein een subset is van het volledige bereik van de gebruikte codering.

Wie huisnummers wil hashen zal een gespecialiseerde hash nodig hebben aangezien huisnummer 1 veel vaker zal voorkomen dan huisnummer 300.

[ Voor 8% gewijzigd door H!GHGuY op 03-10-2010 12:49 ]

[Janoz]

Ik geef je helemaal gelijk dat de extra kennis over de data die je hebt bijdraagt aan een beter verdeeld Hash resultaat. Maar om het vervolgens uit te besteden lijkt mij niet handig. Dan heb je een unicode string, die wil je extern laten hashen, en dan ga je op zoek naar een generieke hash implementatie, die weer specifiek op een unicode string toegespitst is.

Wat je goed moet beseffen is dat het contract van een dergelijke hash enkel stelt dat dezelfde bron waarde dezelfde hash op moet leveren, en dat bij verschillende waarden de kans op een andere hash erg groot is. Het is niet van belang dat het makkelijk is om een variabele zo aan te passen of uit te zoeken dat hij eenzelfde hash oplevert. Het gaat hier niet om security.

In dat geval is het berekenen van een hash wel zo simpel als het xor-en van wat data. Voor binaire data neem je de hele byte, terwijl je bij een tekst string eventueel kunt overwegen om enkel de 6 meest veranderende bits te gebruiken (als dat uberhaupt al uitmaakt). Het algorithme is te simpel om de complete implementatie in een andere class onder te brengen. Maar eigenlijk is het hele string of binaire data hashen verhaal een beetje een nonissue, aangezien daarvoor over het algemeen al een standaard geimplementeerde hash functie beschikbaar is.

Huisnummer vind ik trouwens een beetje een mager voorbeeld. De hash ruimte is (zelfs bij een byte) al zoveel groter dan de meest voorkomende huisnummer waarden dat het voor de hand ligt om bij de hash ook daadwerkelijk het huisnummer zelf op te leveren (modulus het bereik van je hash waarde)

[Hydra]

Beetje een kwestie van het wiel opnieuw uitvinden dit. Het zit in Java en .Net niet voor niets in de class zelf. Hoe een hash berekend wordt, daar heeft niemand wat mee te maken behalve de class zelf. Het enige wat voor de buitenwereld interessant is is de waarde die aan een aantal regels moet voldoen (twee objecten die equals() == true terugggeven moeten dezelfde hash hebben, etc.). Hoe je die berekent interesseert niemand wat. Natuurlijk is het logich dat je hash-code hergebruikt, dat doet hier niks aan af.

Oftewel:
- 1 class die een eigen hash implementeert: lekker in de class.
- N classes die niet overerven maar wel dezelfde hash gebruiken; getHash() overriden en onderhuids een helperclass aanroepen.

[H!GHGuY]

Janoz schreef op zondag 03 oktober 2010 @ 14:03:
...

We komen uiteindelijk wel op hetzelfde punt uit hoor: je maakt het zo complex als je het zelf wil (of zo complex als het moet om te voldoen aan de requirements).

Maar als je puur designtechnisch spreekt (en dus niet pragmatisch) dan stop je hashing bij voorkeur in een stuk aparte functionaliteit. Mijns inziens was dit de insteek die de TS wou.