Работа с большой коллекцией

В общем есть вот такой класс:

 class Metric
    {
        public Word Word1;
        public Word Word2;
        public Metric(Word word1, Word word2)
        {
            Word1 = word1;
            Word2 = word2;
        }
        public int Simil;
        public override int GetHashCode()
        {
            return Word1.GetHashCode() + Word2.GetHashCode();
        }
    }
public class Word
{
    public string Text;
    public Word(string text)
    {
        Text = text;
    }
    public override int GetHashCode()
    {
        return Text.GetHashCode();
    }
}

Класс содержит в себе данные о похожести 2-ух слов.

Есть класс, который содержит в себе поле с типом HashSet.

Так вот, когда коллекция достигает размера в несколько миллионов, то становится заметно, что процесс не так шустро, как в самом начале добавления.

Можно ли как-нибудь избежать этого? По идее, LinkedList будет шустрым, но тогда я лишаюсь проверки на уникальность проверяемых пар слов, а это я использую, что бы не пересчитывать одно и тоже повторно.