Wydajne przeszukiwanie kolekcji obiektów

Witam,
program posiada kolekcję obiektów, która ma stałą zawartość (kilka set tysięcy obiektów).
Druga kolekcja zawiera dane wprowadzone z dużą częstotliwością.
Ta druga kolekcja posiada zdarzenie CollectionChanged, w którym jest sprawdzane czy nowo dodany obiekt istnieje w pierwszej kolekcji (jeśli tak to jest w stosowany sposób odznaczany).

W jaki sposób zrobić takie przeszukiwanie wydajnie, w przypadku gdy częstotliwość wprowadzania nowych danych jest bardzo duża? BackroundWorker?
Proszę o sugestie.

Jeżeli nie trzymasz tych obiektów w bazie danych, to hash mapa powinna być szybsza niż synchronizacja wątków. Dla kilkuset tysięcy elementów narzut pamięci powinien się zmieścić w kilkunastu megabajtach, więc to też nie powinno być problemem. Sprawdź jak to działa, jeżeli będzie zbyt wolne to przenieś do innego wątku.

A czy istnieje możliwość przeniesienia obsługi zdarzenia w osobnym wątku?

Pewnie tak (na C# średnio się znam), ale mógłbyś podać w czym trzymasz te obiekty i jak sprawdzasz czy dany obiekt istnieje w kolekcji.

Dane przechowuje w ObservableCollection.
następnie w poszukiwaniu obiektu iteruje po tej kolekcji

Tego się obawiałem. Twoje działanie jest podobne do robienia wielowątkowego bubble sorta w celu szybkiego sortowania. Taki sposób wyszukiwania nie nadaje się w twoim problemie. Zrób sobie do głównej kolekcji (tej, w której sprawdzasz występowanie elementu) dodatkowy HashSet (http://msdn.microsoft.com/en-us/library/bb495294.aspx) i sprawdzanie występowania będzie kilka rzędów wielkości szybsze niż przy obecnym rozwiązaniu (podejrzewam, że przy kilkuset tysiącach to będzie co najmniej 10 000 razy szybsze). Wtedy żadne wątki nie będą Ci potrzebne.

Myślałem o dodatkowym wątku, po aby to przeszukiwanie nie blokowało interakcji użytkownika z aplikacją...

Jeszcze jedno. Weź się za naukę chociaż podstaw algorytmiki i struktur danych, bez tego nie da się nic sensownego nawet w najłatwiejszym języku programowania napisać.

nie musisz mi tłumaczyć podstaw struktur danych, wiem że iteracja nie jest czymś optymalnym w tym przypadku
Twoje rozwiązanie jest nie do końca takie jakie oczekiwałem, ciągłe przeszukiwanie w głównym wątku unieruchomi program dla użytkownika...

Jeżeli twoja aplikacja jest w stanie nadążyć z tym przeszukaniem używając tej metody w trakcie normalnego działania programu to używając HashSetu nie będziesz musiał tworzyć nowego wątku bo użytkownik nie zauważy tego przeszukania. Jak nadal program będzie blokowany, to dopiero wtedy oddeleguj to do oddzielnego wątku. Przy takiej ilości dodawanych obiektów (podejrzewam, że około 1000 na sekundę by coś takiego spowodowało) twoje przeszukiwanie by trwało godzinami.

Czyli Twoim zdaniem 10 przeszukiwań na sekundę w kilkuset tysięcznej kolekcji (hashmap) nie nie będzie problemem?

Na pewno dla tej ilości danych będzie zdecydowanie szybsze niż przeszukiwanie liniowe. Dodatkowo szybkość przeszukiwania będzie w miarę stała przy zwiększaniu się liczby elementów w przeszukiwanej tablicy, dopóki nie będziesz musiał swapować pamięci. Jeżeli dalej by występowało blokowanie głównego wątku (np. ilość danych do sprawdzenia jest tak duża), to można by to przenieść na inny wątek, ale już z wyszukiwaniem które będzie działa w sensownym czasie. Przy kilkuset tysiącach elementów musisz patrzeć na używane struktury danych i złożoności operacji wykonywanych przy ich użyciu.

@lukasz1987 - mieszasz dwie rzeczy:

1. szybkość algorytmu (przeszukiwania kolekcji), o której pisze @Zjarek;
2. responsywność aplikacji i odizolowanie logiki od GUI (bo obliczenia mogą GUI "blokować").

Najpierw użyj optymalnego algorytmu wyszukiwania (1), potem baw się w BackgroundWorkery i ProgresBary (2).