Что такое метод колизий, про что здесь речь?

Это коллизии в хеш-таблице (dict, set). Открытая адресация - это укладка конфликтующих ключей в другие ячейки того же массива при помощи функций рехеширования. Цепочки - это выстраивание связных списков или деревьев из элементов, имеющих одинаковый хеш, т.е. каждая ячейка таблицы хранит ссылку на голову такого списка или дерева.

Пишут , что в Python 2.7 использовался метод открытой адресации, причём, load factor там где-то 2/3, а насколько я помню, при открытой адресации он должен быть не больше 0.1-0.2. Но в 3+ могли это и поменять, всё-таки асимптотика при удалении элементов из такой таблицы - так себе (а если быстро удалять, то поиск будет замедляться и замедляться).

Правда, я смотрю, всё-таки нашлись компетентные люди , пытающиеся приделать к Питону HAMT (в рамках PEP 550 ), но он идёт не в виде стандартного рантайма, а в виде дополнительной библиотеки. PEP 603 предлагает добавить в стандарт языка неизменяемый frozenmap, построенный на HAMT. Последнее обновление - меньше года назад.

Для быстрого доступа к элементам ассоциативных массивов ключи этих массивов хранят либо в виде деревьев, либо в виде хэш-таблиц. Но это в криптографии хэш может быть длиной 512 бит (64 байта). А для быстрого доступа к элементу по ключу хэш ключа должен быть достаточно коротким (значение хэша - индекс в линейном массиве ключей). Но короткий хэш приводит к коллизиям: когда несколько разных значений имеют идентичное значение хэша. Причём коллизии практически гарантированно начинаются, когда в хэш таблице длиной N оказывается всего-то √N значений (посмотри в Вики "парадокс дней рождения").

И для решения проблемы коллизий придумали два основных алгоритма:

Вариант 1 (цепочка): каждое значение хэша - это не единственный элемент, а список. И в этот список заносятся все ключи с совпадающих хэшем. Мы сначала вычисляем хэш ключа и выбираем нужный список, а потом ищем в этом списке искомое значение ключа.

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