Co to jest tabela skrótów?

Tabela mieszająca jest zdefiniowana jako struktura danych używana do szybkiego wstawiania, wyszukiwania i usuwania par klucz-wartość. Działa na koncepcja mieszania , gdzie każdy klucz jest tłumaczony przez funkcję skrótu na odrębny indeks w tablicy. Indeks pełni funkcję miejsca przechowywania pasującej wartości. Krótko mówiąc, odwzorowuje klucze na wartość.

Co to jest współczynnik obciążenia?

Współczynnik obciążenia tablicy mieszającej jest określany na podstawie liczby przechowywanych w niej elementów w stosunku do wielkości tabeli. Jeśli współczynnik obciążenia jest wysoki, tabela może być zaśmiecona, a czas wyszukiwania i kolizje będą dłuższe. Idealny współczynnik obciążenia można utrzymać, stosując dobrą funkcję skrótu i ​​odpowiednią zmianę rozmiaru tabeli.

Co to jest funkcja mieszająca?

Funkcja, która tłumaczy klucze na indeksy tablicy, nazywana jest funkcją skrótu. Klucze powinny być równomiernie rozmieszczone w całej tablicy za pomocą przyzwoitej funkcji skrótu, aby ograniczyć kolizje i zapewnić szybkie prędkości wyszukiwania.

• Założenie dotyczące wszechświata całkowitego: Zakłada się, że klucze są liczbami całkowitymi z pewnego zakresu, zgodnie z założeniem wszechświata całkowitego. Umożliwia to stosowanie podstawowych operacji mieszania, takich jak mieszanie dzielenia i mnożenia.
• Haszowanie według podziału: Ta prosta technika mieszania wykorzystuje pozostałą wartość klucza po podzieleniu jej przez rozmiar tablicy jako indeks. Gdy rozmiar tablicy jest liczbą pierwszą, a klucze są równomiernie rozmieszczone, działa dobrze.
• Haszowanie przez mnożenie: Ta prosta operacja mieszania mnoży klucz przez stałą z zakresu od 0 do 1 przed pobraniem części ułamkowej wyniku. Następnie indeks wyznacza się mnożąc składnik ułamkowy przez rozmiar tablicy. Działa również skutecznie, gdy klawisze są równomiernie rozmieszczone.

Wybór funkcji skrótu :

Wybór przyzwoitej funkcji skrótu opiera się na właściwościach kluczy i zamierzonej funkcjonalności tablicy skrótów. Kluczowe jest użycie funkcji, która równomiernie rozprowadza klawisze i ogranicza kolizje.

Kryteria na podstawie których wybierana jest funkcja mieszająca:

• Aby mieć pewność, że liczba kolizji będzie ograniczona do minimum, dobra funkcja mieszająca powinna równomiernie rozmieszczać klucze w całej tablicy mieszającej. Oznacza to, że dla wszystkich par kluczy prawdopodobieństwo, że dwa klucze znajdą się na tej samej pozycji w tabeli, powinno być raczej stałe.
• Aby umożliwić szybkie mieszanie i odzyskiwanie klucza, funkcja mieszająca powinna być wydajna obliczeniowo.
• Wydedukowanie klucza na podstawie jego wartości skrótu powinno być trudne. W rezultacie próby odgadnięcia klucza przy użyciu wartości skrótu mają mniejsze szanse powodzenia.
• Funkcja skrótu powinna być wystarczająco elastyczna, aby można ją było dostosowywać w miarę zmian haszowanych danych. Na przykład funkcja mieszająca musi nadal działać poprawnie, jeśli klucze podlegające mieszaniu zmieniają się pod względem rozmiaru lub formatu.

Techniki rozwiązywania kolizji :

Kolizje mają miejsce, gdy dwa lub więcej kluczy wskazuje na ten sam indeks tablicy. Łańcuchy, otwarte adresowanie i podwójne mieszanie to kilka technik rozwiązywania kolizji.

• Adresowanie otwarte : kolizje są obsługiwane poprzez wyszukiwanie następującego pustego miejsca w tabeli. Jeżeli pierwszy slot jest już zajęty, funkcja mieszająca jest stosowana do kolejnych slotów, aż jeden pozostanie pusty. Istnieją różne sposoby wykorzystania tego podejścia, w tym podwójne mieszanie, sondowanie liniowe i sondowanie kwadratowe.
• Oddzielne łączenie : W oddzielnym łańcuchu istnieje połączona lista obiektów, które hashują do każdego slotu w tablicy mieszającej. Na połączonej liście znajdują się dwa klucze, jeśli są powiązane z tym samym gniazdem. Ta metoda jest dość prosta w użyciu i może poradzić sobie z kilkoma kolizjami.
• Mieszanie Robin Hooda: Aby zmniejszyć długość łańcucha, kolizje w mieszaniu Robin Hooda są rozwiązywane poprzez wyłączanie klawiszy. Algorytm porównuje odległość pomiędzy szczeliną a zajętą ​​szczeliną dwóch kluczy, jeśli nowy klucz łączy się z już zajętą ​​szczeliną. Istniejący klucz zostaje zamieniony na nowy, jeśli jest bliżej idealnego gniazda. To przybliża istniejący klucz do idealnego gniazda. Ta metoda ma tendencję do zmniejszania liczby kolizji i średniej długości łańcucha.

Dynamiczna zmiana rozmiaru:

Ta funkcja umożliwia rozszerzanie lub kurczenie tablicy mieszającej w odpowiedzi na zmiany liczby elementów zawartych w tabeli. Zapewnia to idealny współczynnik obciążenia i szybki czas wyszukiwania.

Implementacje tablicy mieszającej

Python, Java, C++ i Ruby to tylko niektóre z języków programowania obsługujących tablice mieszające. Oprócz tego, że często znajdują się w standardowej bibliotece, można ich używać jako dostosowanej struktury danych.

Przykład – Policz znaki w String geeksforgeeks.

W tym przykładzie używamy techniki mieszającej do przechowywania liczby ciągów.

wstaw znak wodny w słowie

#include  using namespace std; int main() {  //initialize a string  string s='geeksforgeeks';    // Using an array to store the count of each alphabet   // by mapping the character to an index value  int arr[26]={0};    //Storing the count  for(int i=0;i

public class CharacterCount {  public static void main(String[] args) {  // Initialize a string  String s = 'geeksforgeeks';  // Using an array to store the count of each alphabet  // by mapping the character to an index value  int[] arr = new int[26];  // Storing the count  for (int i = 0; i < s.length(); i++) {  arr[s.charAt(i) - 'a']++;  }  // Search the count of the character  char ch = 'e';  // Get count  System.out.println('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>

# Initialize a string s = 'geeksforgeeks' # Using a list to store the count of each alphabet # by mapping the character to an index value arr = [0] * 26 # Storing the count for i in range(len(s)): arr[ord(s[i]) - ord('a')] += 1 # Search the count of the character ch = 'e' # Get count print('The count of ', ch, ' is ', arr[ord(ch) - ord('a')])>

using System; class Program {  static void Main(string[] args) {  //initialize a string  string s = 'geeksforgeeks';  // Using an array to store the count of each alphabet   // by mapping the character to an index value  int[] arr = new int[26];  //Storing the count  for (int i = 0; i < s.Length; i++) {  arr[s[i] - 'a']++;  }  //Search the count of the character  char ch = 'e';  // get count  Console.WriteLine('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>

// Initialize a string const s = 'geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value const arr = Array(26).fill(0); // Storing the count for (let i = 0; i < s.length; i++) {  arr[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Search the count of the character const ch = 'e'; // Get count console.log(`The count of ${ch} is ${arr[ch.charCodeAt(0) - 'a'.charCodeAt(0)]}`);>

Wyjście:

The count of e is 4>

Analiza złożoności tabeli mieszającej:

W przypadku operacji wyszukiwania, wstawiania i usuwania tabele skrótów mają złożoność czasową średniego przypadku wynoszącą O(1). Jednak w najgorszym przypadku operacje te mogą wymagać czasu O(n), gdzie n jest liczbą elementów w tabeli.

Zastosowania tabeli skrótów:

• Tabele skrótów są często używane do indeksowania i przeszukiwania ogromnych ilości danych. Wyszukiwarka może używać tabeli skrótów do przechowywania zaindeksowanych stron internetowych.
• Dane są zwykle buforowane w pamięci za pomocą tablic skrótów, co umożliwia szybki dostęp do często używanych informacji.
• Funkcje skrótu są często używane w kryptografii do tworzenia podpisów cyfrowych, sprawdzania poprawności danych i gwarantowania integralności danych.
• Tabele skrótów można wykorzystać do implementacji indeksów baz danych, umożliwiając szybki dostęp do danych w oparciu o wartości kluczy.