nesco, я об этом уже несколько постов подряд талдычу Первый (цепочка): медленный поиск, быстрое добавление. Второй (таблица) - быстрый поиск, медленное добавление (опять же, выделение блоками несколько сгладит эффект). Есть подозрение, что можно с помощью дерева сделать достаточно быстрым и поиск, и добавление (двоичное дерево, движение от старшего разряда индекса к младшему, "листья" - адреса блоков), и вроде плата (память/быстродействие) не очень большая будет.