I want to implement a simple hash table in Fortran - in the first place, to learn a little bit about hash tables and their organization, second place, to flex my Fortran muscles a little bit.
My first guess was the Fortran Wiki: Hash tables in Fortran Wiki, which I personally didn’t find helpful - except the hint at Kernighan’s Practice of Programming and the transfer procedure.
I ended for reference with the MUSL implementation of the POSIX hash table management: hsearch.c\search\src - musl - musl - an implementation of the standard library for Linux-based systems, search.h\include - musl - musl - an implementation of the standard library for Linux-based systems.
!! use iso_fortran_env, only: i64 => INT64 integer(i64) function hash_key(key) result (hash) character(len=*), intent(in) :: key integer :: i hash = 0 do i = 1, len(key) hash = 31 * hash + ichar(key(i), i64) end do end function hash_key subroutine hash_table_insert (table, key, data) class(hash_table_t), target, intent(inout) :: table character(len=*), intent(in) :: key class(*), pointer, intent(in) :: data integer(i64) :: hash hash = hash_key(key) block type(hash_table_entry_t), pointer :: table_entry integer(i64) :: i, j, table_index i = hash j = 1 do table_index = iand(i, int(table%n_entries, i64)) + 1 table_entry => table%entries(table_index) if (.not. allocated(table_entry%key) .or. table_entry%key == key) exit j = j + 1 i = i + j end do print *, "FOUND EMPTY BUCKET", table_index table_entry%key = key table_entry%data => data end block end subroutine hash_table_insert
Here my question, they tend towards a more general hash implementation, maybe you can hint me to some nice sources:
- Instead of using
character(len=*), intent(in) :: keycould I use unlimited polymorphism and transfer it to an integer array? To my understanding, I would not transfer the actual content of the target, but only the unlimited polymorphism pointer and make hash out of the pointer itself?
- If I would use unlimited polymorphism, how do I infer the correct size for transfer?
storage_sizedivided by the bit-size of an specific integer-kind?
- Integer arithmetic: The standard does not define how an overflow has to be handled. I know howto to “emulate” unsigned integer arithmetic with either larger integer kinds or using a module 2^30, but I don’t see how this may help me in this case.
Thanks for your help! The forum is a great source :).