В этом и суть. Она не читает память в строку, а использует хэш функцию для быстрого получения номера ячейки, откуда брать данные. И происходит это за О1, а не О(n) для чтения всей памяти. Кстати, важный момент. Тк мы храним в мапе адрес!!! бакетов, то конструкция вида m1:=m2 вызывает копирование адреса в новую область памяти. И изменение m2[a] приведет к изменению по адресу бакета, следовательно m1 формально будет изменена.(формально, тк на самом деле будет изменен бакет, а не сама мапа). На этом моменте нужно быть очень аккуратным, поверьте моим страданиям:(
И добавление за logN при балансировке:)
В этом и суть. Она не читает память в строку, а использует хэш функцию для быстрого получения номера ячейки, откуда брать данные. И происходит это за О1, а не О(n) для чтения всей памяти.
Кстати, важный момент. Тк мы храним в мапе адрес!!! бакетов, то конструкция вида m1:=m2 вызывает копирование адреса в новую область памяти. И изменение m2[a] приведет к изменению по адресу бакета, следовательно m1 формально будет изменена.(формально, тк на самом деле будет изменен бакет, а не сама мапа). На этом моменте нужно быть очень аккуратным, поверьте моим страданиям:(