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ým prvkem těchto tabulek jsou hašovací funkce, protože mají velký vliv na jejich latence. Špatně navržená hašovací funkce může zpomalit hašovaní tvorbou kolizí, což je nepříznivý stav a musí byt řešený na úkor výpočtového času. Neexistuje deterministická 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ý je moderním způsobem řešení kolizí. Jeho hlavní výhodou je konstantní čas vyhledávaní, kterého je dosaženo použitím dvou či více hašovacích funkcí pro hašovací tabulku. Hašovací funkce jsou navrženy automatickým použitím genetického programování z obecný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ěkem v 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"
}