Как возможны «неблокирующие» структуры данных?

Мне трудно понять, как любая структура данных может быть "неблокирующей".

Допустим, вы создаете «неблокирующую» хеш-таблицу. В какой-то момент ваша хэш-таблица становится слишком полной, поэтому вам приходится повторно хэшировать в большую таблицу.

Это означает, что вам необходимо выделить память, которая является глобальным ресурсом. Таким образом, кажется, что вы должныполучить какую-то блокировку, чтобы предотвратить глобальное повреждение кучи... независимо от возможных проблем с самой вашей структурой данных!
Но тогда это означает, что все остальные потоки должны блокироваться, пока вы выделяете память...

Что я здесь упускаю?
(Как) вы можете выделить память, не блокируя другой поток, который делает то же самое?