Compile Time String Hash

HarteWare

Hallo,

basierend auf diesem Link habe ich diese constexpr version geschrieben:

constexpr unsigned str_hash(const char* s)
{
    unsigned hash {2166136261u};
    do {
        hash ^= static_cast<unsigned>(*s);
        hash *= 16777619u;
    } while (*s++);
    return hash;
}

Kennt jemand eine bessere Methode, oder ist das gut?

LG

Swordfish

@harteware sagte in Compile Time String Hash:

ist das gut?

Ja, seit C++14 kann man das so machen. Eine Variante die auch mit C++11 klappt wäre zB. die hier (FNV-1a).

Vielleicht schreibst Du auch besser std::uint32_t damit klar wird, daß es sich um eine 32-Bit-Version von FNV-1 handelt.

// edit: Deine Version hasht auch die terminierende \0 eines ~~leeren~~ Strings. Das sollte IMO nicht so sein. Eine Referenzimplementierung finet sich unter draft-eastlake-fnv-15.txt

HarteWare

@Swordfish vielen Dank für die Hinweise, ich habe meinen Code korrigiert.

constexpr uint32_t fnv32(const char* s)
{
    uint32_t hash{2166136261u};
    while (*s) {
        hash = 16777619u * (hash ^ static_cast<uint32_t>(*s++));
    }
    return hash;
}

LG

Swordfish

@harteware Der Cast ist überflüssig. Und die magic numbers könnten Namen vertragen:

#include <stdexcept>
#include <cstdint>

namespace hashing
{
	// 32 bit FNV prime = 2^24 + 2^8 + 0x93
	constexpr std::uint32_t fnv32_prime{ 0x01000193 };

	// FNV-0 hash of "chongo <Landon Curt Noll> /\\../\\" represented in ASCII
	constexpr std::uint32_t fnv32_basis{ 0x811c9dc5 };

	constexpr
	auto fnv1a_32_str(char const * str) -> std::uint32_t
	{
		if (!str)
			throw std::invalid_argument{ "Argument str is a null pointer!" };

		std::uint32_t hash{ fnv32_basis };

		while (*str)
			hash = (hash ^ *str++) * fnv32_prime;

		return hash;
	}
}

hustbaer

"Basis" klingt schon sehr Deutsch. Base? Oder gleich seed?

Swordfish

Fowler, Noll & Vo selbst nennen es "offset basis".

hustbaer

Krass.

Swordfish

@hustbaer sagte in Compile Time String Hash:

Krass.

?

Da zumindest zwei davon sicher native speaker sind ...

firefly

Ganz besonders das basis scheinbar auch ein englisches wort ist.
zumindestens laut dict.cc
https://www.dict.cc/?s=basis

hustbaer

Natürlich ist es ein englisches Wort, aber mir kommt es in dem Zusammenhang sehr deplatziert vor. "Basis" wird im Englischen sowieso recht wenig verwendet.

@swordfish sagte in Compile Time String Hash:

Da zumindest zwei davon sicher native speaker sind ...

Und deswegen darf ich nicht überrascht und/oder der Meinung sein dass das Wort dort unpassend wirkt?

HarteWare

Ich finde 'seed' auch besser..
Ich kenne das Wort basis im Alltag nur vom Ausdruck "on a regular basis", was so viel heißt wie "regularly", aber eher für Dinge die in größeren Zeitabschnitten regelmäßig geschehen oder gemacht werden (z.B. Ölwechsel). Sonst verwendet man es eher selten.

Und deswegen darf ich nicht überrascht und/oder der Meinung sein dass das Wort dort unpassend wirkt?

Doch! :o)

Swordfish

Mhm. Und was genau bringt es, das Ding mit Gewalt anders zu nennen als der Rest der Welt?

hustbaer

@Swordfish Das musst du die drei Jungs fragen, nicht mich

Aber ernsthaft: Nachdem du mir geschrieben hast dass die Erfinder selbst den Begriff verwenden (was ich vorher nicht wusste), hab ich ja nicht mehr vorgeschlagen es zu ändern.

Krass ist es trotzdem, weil es halt sonst keiner "basis" nennt. Womit wir wieder genau bei "was bringt es das Ding mit Gewalt anders zu nennen" wären.

Columbo

@hustbaer sagte in Compile Time String Hash:

Natürlich ist es ein englisches Wort, aber mir kommt es in dem Zusammenhang sehr deplatziert vor. "Basis" wird im Englischen sowieso recht wenig verwendet.

Das kann man so nicht sagen. Und darüberhinaus kann ich mich an viele Vorkommnisse dieses Begriffs während meines Studiums erinnern.

Edit: Um auch etwas zum Thema beizutragen: Wir hatten compile-time string hashes schon mehrmals. Siehe bspw. https://www.c-plusplus.net/forum/post/2539241

Swordfish

@hustbaer sagte in Compile Time String Hash:

Krass ist es trotzdem, weil es halt sonst keiner "basis" nennt.

Sehe ich eben nicht so.

hustbaer

Du darfst das sehen wie du willst
Ich wollte nur darauf hinaus dass
a) ich nicht wusste dass das der "Originalbegriff" ist, und wenn ich es gewusst hätte ich die Verwendung niemals kritisiert hätte, da ich es schon gut finde Dinge nicht unnötig anders zu nennen als "im Original" und
b) ich ein "Argument from Authority" üblicherweise nicht gelten lasse

D.h. ja, der Begriff passt im Zusammenhang mit FNV (und damit auch in deinem Code-Beispiel!), weil man das dort halt einfach so nennt. Er ist für mich trotzdem komisch im weiteren Kontext von Hashfunktionen, weil es da nicht unbedingt ein üblicher Term ist.