Wie generiert der Google URL Shortener einen 5-stelligen Hash ohne Kollisionen?

Sie verfügen über eine Datenbank, in der alle zuvor generierten URLs und die längere URL aufgezeichnet werden, auf die sich jede dieser URLs bezieht. Es ist einfach sicherzustellen, dass neu generierte URLs nicht bereits in dieser Tabelle vorhanden sind. Ein wenig schwierig zu skalieren (sie haben sicherlich mehrere Server, so dass jeder einen Eimer mit Werten zugewiesen werden muss, aus denen er an die Benutzer ausgeben kann). Wenn sie jemals 916,132,832 URLs generieren, fügen sie einfach ein anderes Zeichen hinzu.

1. Es speichert die bisher verwendeten langen URLs. Das bedeutet, wenn jemand eine kurze URL erstellt, wenn der Ort, auf den er verweist, bereits eine kurze URL hat, gibt er ihnen die bereits vorhandene kurze URL.

2. Tatsächlich wäre es ineffizient, ein System zu haben, das für die Erstellung von "Hashes" basierend auf einem gegebenen Datensatz vorgesehen ist. Vielmehr ist die kurze URL einfach eine zufällige Menge von Zeichen, die bereits als zehn Ziffern identifiziert wurden, plus 26 Kleinbuchstaben plus 26 Großbuchstaben = 916132832 Permutationen (keine Kombinationen). Zufällige kurze URLs sind der effizienteste Weg, um es zum Laufen zu bringen, und deshalb sind sie immer unterschiedlich (obwohl ich denke, dass es eine andere Komponente im Algorithmus geben könnte wie die Tageszeit, aber ich denke nicht, dass es das wert ist. ... Es macht keinen Sinn, es so komplex zu machen, all diese Rechenleistung auszugeben, nur um eine alberne 5-stellige Zeichenkette zu erstellen, die jeder Affe per Knopfdruck auf einem Permutationsrechner tun kann.