Benutzer:Supaari/temp

Aus Hashtabelle#Quadratisches Sondieren

Allgemein offnes Hashing runder erklären!

Wie beim linearen Sondieren wird nach einem neuen freien Speicher gesucht, allerdings nicht sequenziell, sondern mit stetig quadratisch wachsender Schrittweite und in beide Richtungen. Verursacht h(k) eine Kollision, so werden z. B. h(k) + 1 , h(k) - 1 , h(k) + 4 , h(k) - 4 , h(k) + 9 und so weiter probiert. Allgemeine Formulierung:

$\left(h(k)+s_{n}\right){\bmod {\ }}m,\quad \mathrm {mit} \ s_{n}=\left(\lceil \textstyle {\frac {n}{2}}\rceil \right)^{2}\cdot (-1)^{n},\ n\in \mathbb {N} .$

( $\lceil \textstyle {\frac {n}{2}}\rceil$ bedeutet, $\textstyle {\frac {n}{2}}$ wird aufgerundet. $s_{n}$ ist Sondierungsfolge) Den ständigen Wechsel des Vorzeichens bei dieser Kollisionsstrategie nennt man auch "alternierendes quadratisches Sondieren" oder "quadratisches Sondieren mit Verfeinerung". Wählt man die Anzahl der Behälter geschickt (nämlich m = 4·j+3, m als Primzahl), dann wird sichergestellt, dass alle Behälter irgendwann getroffen werden.

Aus NAND-Gatter

${\begin{matrix}{\overline {x}}&\equiv &{\overline {x\cdot x}}\\x\cdot y&\equiv &{\overline {{\overline {x\cdot y}}\cdot {\overline {x\cdot y}}}}\\x+y&\equiv &{\overline {{\overline {x\cdot x}}\cdot {\overline {y\cdot y}}}}\\{\overline {x+y}}&\equiv &{\overline {{\overline {{\overline {x\cdot x}}\cdot {\overline {y\cdot y}}}}\cdot {\overline {{\overline {x\cdot x}}\cdot {\overline {y\cdot y}}}}}}\\x\not \equiv y&\equiv &{\overline {{\overline {x\cdot {\overline {y\cdot y}}}}\cdot {\overline {{\overline {x\cdot x}}\cdot y}}}}\end{matrix}}$

x XNOR y  ≡  (x NAND y) NAND ((x NAND x)  NAND  (y NAND y))  [≡ x <=> y]

x  =>  y  ≡   x NAND (y NAND y)
x <=   y  ≡  (x NAND x) NAND y
x <=>  y  ≡  (x NAND y) NAND ((x NAND x)  NAND  (y NAND y))  [≡ x XNOR y]

verum     ≡  (x NAND x) NAND x
falsum    ≡ ((x NAND x) NAND x)  NAND ((x NAND x)  NAND x)