Detail publikace
Evolutionary design of hash functions for IP address hashing using genetic programming
Dobai Roland, Ing., Ph.D. (CK-SZZ)
Hash function, Hash table, Cuckoo hashing, Evolutionary design, Genetic programming
Hašovacítabulky jsou základní vyhledávací datové struktury. Klíčovýmprvkem těchto tabulek jsou hašovací funkce, protože mají velkývliv na jejich latence. Špatně navržená hašovací funkce můžezpomalit hašovaní tvorbou kolizí, což je nepříznivý stav a musíbyt řešený na úkor výpočtového času. Neexistujedeterministická metoda pro návrh dobře fungující hašovacífunkce. Návrhář spoléhá pouze na jeho/její zkoušenosti,vědomosti a intuice. Tento článek je orientovaný na evolučnínávrh hašovacích funkcí pro Kukaččí hašování, který jemoderním způsobem řešení kolizí. Jeho hlavní výhodou jekonstantní čas vyhledávaní, kterého je dosaženo použitím dvou čivíce hašovacích funkcí pro hašovací tabulku. Hašovací funkcejsou navrženy automatickým použitím genetického programování zobecných operací jako například násobení nebo bitový posuv.Evolučně navážené funkce jsou 2.7-7 krát rychlejší, umožňujíuložení o 1-1,6% více klíčů a jsou konstruovány z ménějednoduchých operací v porovnaní s řešením vytvořeným člověkemv problematice hašování IP adres.
@inproceedings{BUT144406,
author="Marek {Kidoň} and Roland {Dobai}",
title="Evolutionary design of hash functions for IP address hashing using genetic programming",
booktitle="2017 IEEE Congress on Evolutionary Computation (CEC)",
year="2017",
pages="1720--1727",
publisher="Institute of Electrical and Electronics Engineers",
address="San Sebastian",
doi="10.1109/CEC.2017.7969509",
isbn="978-1-5090-4601-0"
}