Hashing - techfak.uni-bielefeld.de · Bielefeld hat ca. 300.000 Einwohner, dann gibt es vielleicht 200.000 Telefonnummern. Davon bestellt jeder fünfte eine Pizza – bleiben 40.000

Hashing

Algorithmen und Datenstrukturen II 1

Einführendes Beispiel

Ein Pizza-Lieferservice in Bielefeld speichert die Daten seiner Kunden: Name,Vorname, Adresse und Telefonnummer. Wenn ein Kunde seine Bestellungtelefonisch aufgibt, um dann mit der Pizza beliefert zu werden, dann muss er seineTelefonnummer angeben, da er über diese Nummer eindeutig identifiziert werdenkann.


Telefonnummer Name Vorname PLZ Straße

00000000 Müller Heinz 33615 Unistraße 15

00000001 Schmidt Werner 33615 Grünweg 1

00000002 Schultz Hans 33602 Arndtstraße 12

. . . . . . . . . . . . . . .

99999997 Meier Franz 33609 Kirchweg 4

99999998 Neumann Herbert 33612 Jägerallee 15

99999999 Schröder Georg 33647 Mühlweg 2


Bielefeld hat ca. 300.000 Einwohner, dann gibt es vielleicht 200.000Telefonnummern. Davon bestellt jeder fünfte eine Pizza – bleiben 40.000potentielle Einträge, verteilt auf mehrere Pizza-Lieferservices. Optimistisch geschätztwird unsere Pizzeria also ca. 10.000 Kunden haben.


Modulo

x mod y liefert als Ergebnis den Rest der ganzzahligen Division x/y.

Beispielsweise ergibt 117 mod 20 = 17, da 117 = 5 · 20 + 17.


Hash-Funktion

h(Telefonnummer) = Telefonnummer mod Tabellenlänge,

oder allgemein:

h(k) = k mod m

mit h für Hashfunktion, k für key und m für Tabellenlänge.


Kollisionen

z.B. ist 01063852 mod 10000 = 08153852 mod 10000 = 3852.


Allgemeine Definitionen

Formal gesehen ist Hashing ein abstrakter Datentyp, der die Operationen insert,delete und search auf (dynamischen) Mengen effizient unterstützt.


Direkte Adressierung



pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppp

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

qqqq

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq qqqq

v vvv

v

v

vv v

vppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

U

2

8

5

3

0

1

2

3

4

5

7

8

9

6

1

4

0

7

6

(Universum der Schlussel)

K

T

(Aktuelle Schlussel)

9


Hashing



pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppp

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

v

vqqqq

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qqqqv

vv

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppp

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

h(k1)

h(k4)

h(k2) = h(k5)

h(k3)

(Aktuelle Schlussel)K

T

(Universum der Schlussel)U

m− 1

0

k1

k4

k3

k2k5


Typische Hashfunktion

h(k) = k mod m.


Strategien zur Behandlung von Kollisionen


Direkte Verkettung

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

...................................................................................................................................................

vv

v u

upppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp........................................

........................................

........................................

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq

qqqqqqqqqqqqqqqqqqqqqqqqq

k4

k5

k2k2 k5

k4


worst-case Laufzeiten

insert: O(1) (neues Element vor die Liste hängen)search: O(n) (n = Länge der Liste)delete: O(1) (vorausgesetzt, man verwendet doppelt verkettete Listen und hat das

Element schon gefunden)


Open Hashing

Beim Open Hashing werden alle Einträge in der Hashtabelle gehalten. Ist eineKomponente der Tabelle schon belegt, so wird ein freier Platz für einen weiterenEintrag gesucht.


Open Hashing, lineare Verschiebung

...................................................................................................................................................

...................................................................................................................................................v

vvpppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp p p p p p p p p p p p p p ppppppppppppppppppppppppppppppppppppppppp

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq

qqqqqqqqqqqqqqqqqqqqqqqqqpppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

k4

k5

k2


Lineare Verschiebung

Falls h(k) bereits durch einen anderen Schlüssel besetzt ist, wird versucht, k in denAdressen h(k) + 1, h(k) + 2, . . . unterzubringen (Abbildung ??). Präziser gesagt,wird folgende Hashfunktion verwendet:

h′(k, i) =(h(k) + i

)mod m mit i = 0, 1, 2, . . . ,m− 1.


Hash-Insert mit linearer Verschiebung

Hash-Insert(T, k)

1 i← 02 repeat

3 j ← h′(k, i)4 if T [j] = NIL then

5 T [j]← k

6 return j

7 i← i + 18 until i = m

9 error “hash table overflow”


Hash-Search mit linearer Verschiebung

Hash-Search(T, k)

1 i← 02 repeat

3 j ← h′(k, i)4 if T [j] = k then

5 return j

6 i← i + 17 until T [j] = NIL or i = m

8 error NIL


Quadratische Verschiebung

Es wird die Hashfunktion

h′(k, i) = (h(k) + c1i + c2i2) mod m mit i = 0, 1, 2, . . . ,m− 1

verwendet. Dabei sind c1, c2 ∈ N und c2 6= 0 geeignete Konstanten (s. Cormen etal. [?]).


Double Hashing

Die Hashfunktion h′ wird definiert durch

h′(k, i) = (h1(k) + i · h2(k)) mod m mit i = 0, 1, 2, . . . ,m− 1,

wobei h1 und h2 Hashfunktionen sind. Die Verschiebung wird dabei durch einezweite Hashfunktion realisiert. D.h. es wird zweimal, also doppelt, gehasht.


Beispiel lineare Verschiebung

01

0

1

2

3

4

-insert 11

01

11

0

1

2

3

4

-insert 10

01

1110

0

1

2

3

4

-delete 1

0d

1110

0

1

2

3

4

-search 10


Man erkennt: Gelöschte Felder müssen markiert werden, so dass einSuchalgorithmus nicht abbricht, obwohl das Element doch in der Liste gewesenwäre. Natürlich kann in die gelöschten Felder wieder etwas eingefügt werden.Dieses Problem muss in der obigen Implementierung zusätzlich berücksichtigtwerden.


Ladefaktor

Der Ladefaktor α für eine Hashtabelle T ist definiert als nm , wobei n die Anzahl der

gespeicherten Schlüssel und m die Kapazität der Tabelle sind. TheoretischeUntersuchungen und praktische Messungen haben ergeben, dass der Ladefaktoreiner Hashtabelle den Wert 0.8 nicht überschreiten sollte (d.h. die Hashtabelle darfhöchstens zu 80% gefüllt werden). Ist der Ladefaktor ≤ 0.8, so treten beim Suchenim Durchschnitt ≤ 3 Kollisionen auf. Bei einem höheren Ladefaktor steigt die Zahlder Kollisionen rasch an.


Die Klasse Hashtable in Java

Die Klasse java.util.Hashtable implementiert alle Methoden der abstraktenKlasse java.util.Dictionary (vgl. Aufgabe ??). Außerdem enthält Hashtablenoch folgende Methoden


public synchronized boolean containsKey(Object key)

Es wird true zurückgegeben gdw. die Hashtabelle ein Element unter keyverzeichnet hat.

public synchronized boolean contains(Object element)

Gdw. das angegebene element ein Element der Hashtabelle ist, wird true

zurückgegeben. Diese Operation ist teurer als die containsKey-Methode, daHashtabellen nur beim Suchen nach Schlüsseln effizient sind.

public synchronized void clear()Alle Schlüssel in der Hashtabelle werden gelöscht. Wenn es keine Referenzenmehr auf die Elemente gibt, werden sie vom Garbage-Collector aus demSpeicher entfernt.


public synchronized Object clone()Es wird ein Klon der Hashtabelle erzeugt. Die Elemente und Schlüssel selbstwerden aber nicht geklont.


Konstruktoren der Klasse Hashtable

public Hashtable()Es wird eine neue, leere Hashtabelle mit einer voreingestellten Anfangskapazitätvon 11 und einem Ladefaktor von 0.75 erzeugt.

public Hashtable(int initialCapacity)

Eine neue, leere Hashtabelle mit der Anfangskapazität initialCapacity unddem Ladefaktor 0.75 wird generiert.

public Hashtable(int initialCapacity, float loadFactor)

Es wird eine neue, leere Hastabelle erzeugt, die eine Anfangskapazität derGröße initialCapacity und einen Ladefaktor von loadFactor besitzt. DerLadefaktor ist eine Zahl zwischen 0.0 und 1.0 und definiert den Beginn einesrehashings der Tabelle in eine größere.


Name-Wert-Paare


class Pair {

private String name;

private Object value;

public Pair(String name, Object value) {

this.name = name;

this.value = value;

}

public String name() {

return name;

}

public Object value() {

return value;

}


public Object value(Object newValue) {

Object oldValue = value;

value = newValue;

return oldValue;

}

}


Interface Dic

interface Dic {

void add(Pair newPair);

Pair find(String pairName);

Pair delete(String pairName);

}


Implementierung von Dic


import java.util.Hashtable;

class DicImpl implements Dic {

protected Hashtable pairTable = new Hashtable();

public void add(Pair newPair) {

pairTable.put(newPair.name(), newPair);

}

public Pair find(String name) {

return (Pair) pairTable.get(name);

}

public Pair delete(String name) {


return (Pair) pairTable.remove(name);

}

}


Documents

Hashing - techfak.uni-bielefeld.de · Bielefeld hat ca. 300.000 Einwohner, dann gibt es vielleicht 200.000 Telefonnummern. Davon bestellt jeder fünfte eine Pizza – bleiben 40.000