Која је разлика између низа и хасх табеле у програмском језику?


Одговор 1:

Хасх табеле користе низове. Низови имају важно својство за хасх: можете приступити било којем елементу у сталном времену ако знате његов индекс.

Можете користити низове за канте. Рецимо да сте желели да пребројите колико сваког слова у тексту, рецимо, дизајнирате нешто попут Морсеовог кода. Направите низ с 26 уноса (за једноставну римску абецеду без знака). Кад год видите слово, израчунавате индекс и пређете на тај унос у низу.

Хасх табеле то проширују за произвољно дуге тастере. Израчунате хасх кључа и пређете на тај индекс. Проблем је када више тастера има исти хасх. Постоје разни начини суочавања са тим, од којих неки побијају сврху хасх-а (али их је лако имплементирати). Неки од њих не одржавају својство сталног времена, барем у просеку.

Најбоље што сам видео је та додатна рехаша, која, ако се меморија служи пре више деценија, показали су Гоннет и Мунрое да имају просечно нешто више од 4 приступа са фактором оптерећења од 50%, без обзира на величину хасх табле. То, међутим, захтева коришћење правих бројева, а то чини компликованим за имплементацију. Морате некако пронаћи примарне бројеве. Срећом, хасх таблице не постају толико велике да ово постаје смијешно.