Поиск нужных данных в массиве из структур на Си и возможность многопоточности в Си

Собственно изучая разные структуры данных, одно из последних это хеш таблицы. Построены на бинарных деревьях, разных списков. Где хэш функция делит данные, грубо говоря на 10 потоков, дописывая цепочки коллизиями. И у меня возникла идея =) В моем проекте 1.500.000 русских слов в массиве структур.

struct MyWords{
  int hash;
  char len;
  char word[36];
}

Естественно поиск по хеш коду занимает не определенное время. Но появилась идея, еще без реализации в коде, искать следующим образом. Поиск одновременно с 4 позиций.

1)с начала (0-375000).
2)с с середины(750.000-375001) к началу.
3)с середины к концу (750001-1.125.000)
4) с конца к середине (1.500.000-1.250.001)

Теоретически данные будут найдены быстрее чем даже деление хеш функцией на 10 цепочек (Hash % 10). А если эти функции поиска включить в разные потоки (видел на С++ примеры многопоточности, на Си пока не встречал).Так же пишут что если запустить 4 потока, пока они все не закончат, продолжения не будет! Тогда ОБЛОМ :( Изучая strtok написано что из-за многопоточности используйте strtok_s и strtok_r. Значит некая автоматическая многопоточность используется, нужно КАК-ТО ПОДСТРОИТЬ механизм ;) Хотелось бы реализовать, хотя бы без потоков. Но как вызвать одновременно 4 функции? =) В общем нужны идеи по реализации такого алгоритма.