Ćwiczenia 14 - Haszowanie

Adresowanie bezpośrednie

D-A-SEARCH(T,k)
	return T[k]

D-A-INSERT(T,x)
	T[x.key] = x

D-A-DELETE(T,x)
	T[x.key] = NIL

Tablice z haszowaniem

U - zbiór kluczy
m - wielkość tablicy T
T[0,...,m - 1]
T[i] = NIL
h:U->{0,m - 1}

H-SEARCH(T,k)
	return T[h(k)]

H-INSERT(T,x)
	T[h(x.key)] = x

H-DELETE(T,x)
	T[h(x.key)] = NIL

Funkcje haszujące

Haszowanie modularne

h(p)
	return p MOD m

Haszowanie przez mnożenie

0 < A < 1
A = (sqrt(5) - 1) / 2
h(k)
	return ⌊m(kA MOD 1)⌋

Metoda łańcuchowa (3 pkt termin: 20:00:00 pierwsza środa po zajęciach)

Main

T[0..9]
CH-H-INSERT(T,206)
CH-H-INSERT(T,142)
CH-H-INSERT(T,303)
WRITE(T) //0 0 142 303 0 0 206 0 0 0
CH-H-INSERT(T,213)
WRITE(T) //0 0 142 213->303 0 0 206 0 0 0
WRITE(CH-H-SEARCH(T,303)) //303
CH-H-DELETE(T,303) 
WRITE(T) //0 0 142 213 0 0 206 0 0 0
WRITE(CH-H-SEARCH(T,213)) //213

CH-H-SEARCH(T,k)
	x = T[h(k)]
	while x ≠ NIL AND x.key ≠ k
		x = x.next
	return x

CH-H-INSERT(T,x)
	p = h(x.key)
	x.next = T[p]
	T[p] = x

CH-H-DELETE(T,x)
	p = h(x.key)
	if T[p] = x
		T[p] = x.next
	else
		y = T[p]
		while y.next ≠ x
			y = y.next
		y.next = x.next

Adresowanie otwarte (3 pkt termin: 20:00:00 pierwsza środa po zajęciach)

Main

T[0..9]
OP-H-INSERT(T,206)
OP-H-INSERT(T,142)
OP-H-INSERT(T,303)
WRITE(T) //0 0 142 303 0 0 206 0 0 0
OP-H-INSERT(T,213)
WRITE(T) //0 0 142 303 213 0 206 0 0 0
WRITE(OP-H-SEARCH(T,303)) //303
OP-H-DELETE(T,303)
WRITE(T) //0 0 142 DEL 213 0 206 0 0 0
WRITE(OP-H-SEARCH(T,213)) //213

OP-H-SEARCH(T,k)
	i = 0
	repeat
		j = h(k,i)
		if T[j] = k
			return j
		i = i + 1
	until T[j] = NIL OR i = m
	return NIL

OP-H-INSERT(T,k)
	i = 0
	repeat
		j = h(k,i)
		if T[j] = NIL OR T[j] = DELETED
			T[j] = k
			return j
		else
			i = i + 1
	until i = m
	error "tablica przepełniona"

OP-H-DELETE(T,k)
	i = 0
	repeat
		j = h(k,i)
		if T[j] = k
			T[j] = DELETED
			return j
		i = i + 1
	until T[j] = NIL OR i = m
	return NIL

Funkcje haszujące

Adresowanie liniowe

h(k,i)
	return (h'(k) + i) MOD m

Adresowanie kwadratowe

h(k,i)
	return (h'(k) + c₁i + c₂i²) MOD m

Adresowanie dwukrotne

h(k,i)
	return (h₁(k) + ih₂(k)) MOD m