Каква е разликата между масив и хеш таблица в език за програмиране?


Отговор 1:

Хеш таблиците използват масиви. Масивите имат важно свойство за хеширане: можете да получите достъп до всеки елемент за постоянно, ако знаете неговия индекс.

Можете да използвате масиви за кофи. Да речем, че сте искали да преброите колко от всяка буква в даден текст, да речем, за проектиране на нещо като код на Морс. Правиш масив с 26 записа (за простата нецентрирана римска азбука). Всеки път, когато видите буква, изчислявате индекса и отивате на този запис в масива.

Таблиците с хеш разширяват това за произволно дълги клавиши. Изчисляваш хеш на ключа и отиваш на този индекс. Проблемът е, когато няколко клавиша имат един и същ хеш. Има различни начини за справяне с това, някои от които побеждават целта на хеша (но са лесни за изпълнение). Някои от тях не поддържат и поддържат свойството за постоянно време, поне средно.

Най-доброто, което съм виждал е, че добавянето на хеш рехаш, което ако паметта служи от преди десетилетия, Gonnet и Munroe доказаха, че имат средно малко повече от 4 достъпа с 50% коефициент на натоварване, независимо от размера на хеш-маса. Това обаче изисква използването на прости числа и това го прави труден за изпълнение. Трябва по някакъв начин да намерите основните числа. За щастие хеш таблиците не стават толкова големи, че това става нелепо.