Chcę zaimplementować tabelę mieszania przy użyciu drzew wyszukiwania binarnego, aby zmniejszyć złożoność wyszukiwania w procesie oddzielnego łączenia łańcuchów od O (n) (przy użyciu listy połączonej) do O (log n) (przy użyciu BST). Czy można to zrobić, a jeśli tak, to w jaki sposób? Łatwiej byłoby zrozumieć, jeśli rozwiązanie jest krok po kroku, implementacja logiki.
Chcę skrócić czas wyszukiwania w tablicy mieszającej (kompilacja przy użyciu osobnego łączenia), ale jednocześnie nie chcę, aby czas wstawiania był dłuższy. W moim projekcie nie mogę zmienić funkcji skrótu w celu ograniczenia kolizji. Ale ze względu na skalowalność dochodzi do kolizji. Próbuję znaleźć rozwiązanie, aby móc jakoś pracować z najlepszym czasem dostępu i wstawiania w przypadku kolizji ... tj. W celu zarządzania bieżącym stanem rzeczy niż restrukturyzacji całego algorytmu. Jeśli się nie rozłoży, będzie musiał dokonać restrukturyzacji. Jakieś pomysły?
Odpowiedzi:
To, o co prosisz, jest możliwe, biorąc pod uwagę twoje ograniczenia.
Analiza
Siłą tabeli haszującej jest jej szybkie wyszukiwanie i szybkość wstawiania. Aby uzyskać tę prędkość, należy porzucić pozory porządku w tabeli: tzn. Wszystkie wpisy są pomieszane. Listę można zaakceptować jako pozycję tabeli, ponieważ podczas gdy przejście to O (n), listy są zwykle krótkie, zakładając, że tabela skrótów jest wystarczająco duża, a obiekty przechowywane w tabeli są mieszane przy użyciu algorytmu haszowania dobrej jakości.
Drzewo wyszukiwania binarnego (BST) ma szybkie wstawianie i wyszukiwanie w O (log 2 n). Nakłada również ograniczenie na elementy, które przechowuje: musi być jakiś sposób na uporządkowanie elementów. Biorąc pod uwagę dwa elementy A i B przechowywane w drzewie, musi istnieć możliwość ustalenia, czy A występuje przed B lub czy mają równoważną kolejność.
Tabela skrótów nie nakłada takich ograniczeń: elementy tabeli skrótów muszą mieć dwie właściwości. Po pierwsze, musi istnieć sposób ustalenia, czy są one równoważne; po drugie, musi istnieć sposób obliczenia deterministycznego kodu skrótu. Zamówienie nie jest wymagane.
Jeśli elementy tablicy skrótów mają kolejność, możesz użyć BST jako wpisu tablicy skrótów do przechowywania obiektów z tym samym kodem skrótu (kolizje). Jednak ze względu na wyszukiwanie i wstawianie BST z logarytmem O (log 2 n) oznacza to, że najgorszy przypadek dla całej struktury (tablica skrótu plus BST) jest technicznie lepszy niż użycie listy jako pozycji tabeli. W zależności od implementacji BST będzie wymagało więcej miejsca niż lista, ale prawdopodobnie niewiele więcej.
Należy pamiętać, że zwykle obciążenie ogólne i zachowanie BST nie przynosi niczego w rzeczywistości w sytuacjach rzeczywistych, takich jak segmenty tabeli mieszania, dlatego teoretycznie słaba wydajność listy jest akceptowalna. Innymi słowy, tabela skrótów kompensuje słabość listy, umieszczając mniej elementów na każdej liście (segmencie). Jednak : problem wyraźnie stwierdził, że tablica skrótów nie może się powiększyć, a kolizje występują częściej niż jest to typowe w tabeli skrótów.
Realizacja
Nie zamierzam tu umieszczać kodu, bo szczerze mówiąc, nie jest to naprawdę konieczne, a ty i tak nie podałeś języka.
Chciałbym po prostu skopiować dowolną standardową tabelę skrótów zawartą w standardowej bibliotece języka do nowej klasy, a następnie zmienić typ wiadra tabeli z listy na drzewo. W zależności od języka i standardowej biblioteki może to być bardzo trywialna rzecz.
Zwykle nie zalecałbym takiego kopiowania i wklejania. Jednakże, jest to łatwy sposób, aby uzyskać strukturę danych bitwy przetestowane bardzo szybko.
źródło
Korzystanie z drzewa binarnego do obsługi kolizji w tabeli skrótów jest nie tylko możliwe - zostało już wykonane.
Walter Bright jest najlepiej znany jako wynalazca języka programowania D , ale napisał również wariant ECMAScript o nazwie DMDScript . W przeszłości nagłówek DMDScript (lub być może przodek - wydaje mi się, że pamiętam nazwę DScript) był taki, że jego tabele hasht zwykle przewyższały te w wielu podobnych językach. Powód - obsługa kolizji przy użyciu drzew binarnych.
Nie pamiętam dokładnie, skąd to pochodzi, ale użyte drzewa były naiwnymi drzewami podwójnymi, bez częściowego schematu równowagi (nie AVL, czerwono-czarny itp.), Co ma sens, ponieważ zakładanie, że sama tablica haszująca zmienia rozmiar, gdy robi się przepełniona i nie ma absurdalnie nieprawdopodobnych wskaźników kolizji haszujących, drzewa binarne powinny być zawsze małe. Zasadniczo najgorszy przypadek jest nadal taki sam, jak używanie połączonej listy do obsługi kolizji (z wyjątkiem płacenia ceny dwóch wskaźników na węzeł zamiast jednego), ale przeciętny przypadek zmniejsza liczbę wyszukiwań w każdym segmencie mieszania.
źródło