Technopedia Center
PMB University Brochure
Faculty of Engineering and Computer Science
S1 Informatics S1 Information Systems S1 Information Technology S1 Computer Engineering S1 Electrical Engineering S1 Civil Engineering

faculty of Economics and Business
S1 Management S1 Accountancy

Faculty of Letters and Educational Sciences
S1 English literature S1 English language education S1 Mathematics education S1 Sports Education
teknopedia

teknopedia

teknopedia

teknopedia

teknopedia
  • Registerasi
  • Brosur UTI
  • Kip Scholarship Information
  • Performance
  1. Weltenzyklopädie
  2. Divisionsrestmethode – Wikipedia
Divisionsrestmethode – Wikipedia
aus Wikipedia, der freien Enzyklopädie

Die Divisionsrestmethode (siehe auch Modulo) liefert eine Hashfunktion.

Die Funktion lautet: h ( k ) = k mod m {\displaystyle h(k)=k{\bmod {m}}} {\displaystyle h(k)=k{\bmod {m}}}

m {\displaystyle m} {\displaystyle m} ist die Größe der Hashtabelle.

Eigenschaften

[Bearbeiten | Quelltext bearbeiten]
  1. Die Hash-Funktion kann sehr schnell berechnet werden
  2. Die Wahl der Tabellengröße m {\displaystyle m} {\displaystyle m} beeinflusst die Kollisionswahrscheinlichkeit der Funktionswerte von h {\displaystyle h} {\displaystyle h}.

Für die meisten Eingabedaten ist zum Beispiel die Wahl einer Zweierpotenz für m {\displaystyle m} {\displaystyle m}, also m = 2 i {\displaystyle m=2^{i}} {\displaystyle m=2^{i}}, ungeeignet, da dies der Extraktion der i {\displaystyle i} {\displaystyle i}-niedrigstwertigen Bits von k {\displaystyle k} {\displaystyle k} entspricht, so dass alle höherwertigen Bits bei der Hash-Berechnung ignoriert werden.

Für praxisrelevante Anwendungen liefert die Wahl einer Primzahl für m {\displaystyle m} {\displaystyle m}, welche keine Mersenne-Primzahl ist, eine geringe Anzahl von zu erwartenden Kollisionen bei vielen Eingabedatenverteilungen.[1]

Hashing von Zeichenketten

[Bearbeiten | Quelltext bearbeiten]

Zeichenketten können mit der Divisionsmethode gehasht werden, indem sie in ganze Zahlen zur Basis b {\displaystyle b} {\displaystyle b} umgewandelt werden, wobei b {\displaystyle b} {\displaystyle b} die Zeichensatzgröße bezeichnet.

Um Integer-Überläufe zu vermeiden, kann für die Berechnung des Hashwertes bei Schlüsseln das Horner-Schema angewendet werden. Das folgende Beispiel zeigt eine Berechnung eines Hashwertes für eine 7-Bit-ASCII-Zeichenkette s {\displaystyle s} {\displaystyle s}.

k mod m = ( … ( s 1 ⋅ 128 + s 2 ) mod m ) ⋅ 128 + s 3 ) mod m ) ⋅ 128 + … + s l − 1 ) mod m ) ⋅ 128 + s l ) mod m {\displaystyle k{\bmod {m}}=(\ldots (s_{1}\cdot 128+s_{2}){\bmod {m}})\cdot 128+s_{3}){\bmod {m}})\cdot 128+\ldots +s_{l-1}){\bmod {m}})\cdot 128+s_{l}){\bmod {m}}} {\displaystyle k{\bmod {m}}=(\ldots (s_{1}\cdot 128+s_{2}){\bmod {m}})\cdot 128+s_{3}){\bmod {m}})\cdot 128+\ldots +s_{l-1}){\bmod {m}})\cdot 128+s_{l}){\bmod {m}}}

Somit kann als Zwischenergebnis maximal ( m − 1 ) ⋅ 128 + 127 {\displaystyle \left(m-1\right)\cdot 128+127} {\displaystyle \left(m-1\right)\cdot 128+127} auftreten.

Dargestellt in Pseudocode:

Parameter: natürliche Zahlen i, h=0; Feld s
 for i = 0 to i < länge_von(s)
	h = (h * 128 + s[i]) mod m;
Ergebnis: h.

Die Multiplikation mit 128 = 2^7 entspricht der Links-Bit-Shift-Operation << 7.

Literatur

[Bearbeiten | Quelltext bearbeiten]
  • Donald E. Knuth: The Art of Computer Programming. Band 3: Sorting and Searching. 2nd edition. Addison-Wesley, Upper Saddle River NJ unter anderem 1998, ISBN 0-201-89685-0, S. 515.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press unter anderem, Cambridge MA unter anderem 2001, ISBN 0-262-03293-7, S. 231. 
Abgerufen von „https://de.teknopedia.teknokrat.ac.id/w/index.php?title=Divisionsrestmethode&oldid=194077299“
Kategorien:
  • Algorithmus
  • Hash

  • indonesia
  • Polski
  • العربية
  • Deutsch
  • English
  • Español
  • Français
  • Italiano
  • مصرى
  • Nederlands
  • 日本語
  • Português
  • Sinugboanong Binisaya
  • Svenska
  • Українська
  • Tiếng Việt
  • Winaray
  • 中文
  • Русский
Sunting pranala
Pusat Layanan

UNIVERSITAS TEKNOKRAT INDONESIA | ASEAN's Best Private University
Jl. ZA. Pagar Alam No.9 -11, Labuhan Ratu, Kec. Kedaton, Kota Bandar Lampung, Lampung 35132
Phone: (0721) 702022
Email: pmb@teknokrat.ac.id