{"id":2632,"date":"2014-01-08T15:47:42","date_gmt":"2014-01-08T13:47:42","guid":{"rendered":"http:\/\/www.tutego.de\/blog\/javainsel\/?p=2632"},"modified":"2014-01-08T15:47:42","modified_gmt":"2014-01-08T13:47:42","slug":"kollisionen-und-hash-funktionen","status":"publish","type":"post","link":"https:\/\/www.tutego.de\/blog\/javainsel\/2014\/01\/kollisionen-und-hash-funktionen\/","title":{"rendered":"Kollisionen und Hash-Funktionen"},"content":{"rendered":"<p>Die Wahl der richtigen Hash-Funktion ist wichtig f\u00fcr die Performance. Denn eine \u00bbdumme\u00ab Hash-Funktion, die beispielsweise alle Schl\u00fcssel nur auf einen konstanten Wert abbildet, erreicht keine Verteilung, sondern lediglich eine lange Liste von Schl\u00fcssel-Werte-Paaren; diese Anh\u00e4ufung an einer Stelle nennt sich Clustering. Doch auch bei der besten Verteilung \u00fcber N Buckets ist nach dem Einf\u00fcgen des Elements N + 1 irgendwo eine Liste mit mindestens zwei Elementen aufgebaut, daher vergr\u00f6\u00dfert die Bibliothek standardm\u00e4\u00dfig das Feld. Ist aber die Hash-Funktion aber so schlecht, dass alles auf das gleiche Bucket abgebildet wird, hilft dieses Re-Hashing auch nicht. <\/p>\n<p>Je l\u00e4nger die Datenstruktur der miteinander kollidierenden Eintr\u00e4ge wird, desto langsamer wird der Zugriff der auf Hashing basierenden Datenstruktur insgesamt. Java basiert beim Hashing einzig auf der hashCode()-Methode, und es liegt in unserer Hand sie gut zu implementieren. Die Klasse String hat eine relativ einfache (daf\u00fcr schnelle) Implementierung von hashCode(), die in der Vergangenheit zu Denial of Service Attacken f\u00fchrte gerade weil es zu Kollisionen kam.<a href=\"file:\/\/\/C:\/Users\/Christian Ullenboom\/Dropbox\/Eigene Dokumente\/Insel\/2\/#_ftn1_9033\" name=\"_ftnref1_9033\">[1]<\/a> <\/p>\n<hr align=\"left\" size=\"1\" width=\"33%\"\/>\n<p><a href=\"file:\/\/\/C:\/Users\/Christian Ullenboom\/Dropbox\/Eigene Dokumente\/Insel\/2\/#_ftnref1_9033\" name=\"_ftn1_9033\">[1]<\/a> In Java 7 wurde daf\u00fcr in String eine zus\u00e4tzliche Hash-Methode realisiert, doch in Java 8 diese Implementierung wieder entfernt und die Implementierung f\u00fcr das Hashing insgesamt ver\u00e4ndert, zumindest f\u00fcr die aktuellen Klassen, das \u00e4ltere java.util.Hashtable blieb unver\u00e4ndert.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Die Wahl der richtigen Hash-Funktion ist wichtig f\u00fcr die Performance. Denn eine \u00bbdumme\u00ab Hash-Funktion, die beispielsweise alle Schl\u00fcssel nur auf einen konstanten Wert abbildet, erreicht keine Verteilung, sondern lediglich eine lange Liste von Schl\u00fcssel-Werte-Paaren; diese Anh\u00e4ufung an einer Stelle nennt sich Clustering. Doch auch bei der besten Verteilung \u00fcber N Buckets ist nach dem Einf\u00fcgen [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false,"_links_to":"","_links_to_target":""},"categories":[11],"tags":[],"class_list":["post-2632","post","type-post","status-publish","format-standard","hentry","category-insel"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2632","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/comments?post=2632"}],"version-history":[{"count":1,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2632\/revisions"}],"predecessor-version":[{"id":2633,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2632\/revisions\/2633"}],"wp:attachment":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/media?parent=2632"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/categories?post=2632"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/tags?post=2632"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}