Hirano: ページの作成:「==Background== The struct that provides user access to dictionary data structure. This dictionary is actually an array of linked lists managed by a simple hash table.…」

2026-05-26T04:17:33Z

ページの作成:「==Background== The struct that provides user access to dictionary data structure. This dictionary is actually an array of linked lists managed by a simple hash table.…」

新規ページ

==Background==

The struct that provides user access to dictionary data structure.
This dictionary is actually an array of linked lists managed by a simple hash table.

==Module structure==

<source lang="fortran">

!!! Module for dictionary struct.
!
! Note:
! Use is made of a hash table with each table corresponding
! to a linked list. This should speed up most
! operations.
!

MODULE dictionary_module
USE list_data_module,ONLY: LIST_DATA
USE linked_list_module,ONLY: linked_list_struct
IMPLICIT NONE

TYPE dictionary_struct
INTEGER,PRIVATE :: hash_size !! The size of hash_table.
TYPE(linked_list_struct),PRIVATE,ALLOCATABLE :: table(:)
CONTAINS
PROCEDURE :: init !!! ([hash_size])
!!! Initialize the dictionary struct.
!!! "hash_size" determines the size of hash table.
!!! Default value of hash_size is 100.
PROCEDURE,PRIVATE :: hashkey !!! RESULT(key)
!!! Calculates the hashkey for the given key.

PROCEDURE :: has !!! (key) RESULT(T/F)
!!! Check if the dict has term with given key.
!!! Return .TRUE. if the key exists.
!!! Return .FALSE. otherwise.
PROCEDURE :: get !!! (key) RESULT(DATA)
!!! Get the value of given key.
!!! If the key doesn't exist, give a warning message
!!! and return a value of "NaN".
PROCEDURE :: add !!! (DATA) RESULT(T/F)
!!! Add new term to dictionary.
!!! If the key already exists, return .FALSE.
!!! and overwrite the value as the new one.
!!! Otherwise, return .TRUE. and add the term.
PROCEDURE :: add_no_overwrite !!! (DATA) RESULT(T/F)
!!! Same as add, except no overwriting.
PROCEDURE :: delete !!! (key) RESULT(T/F)
!!! Delete a term with given key from the dictionary.
!!! Returns .TRUE. if the key is found and deleted.
PROCEDURE :: dict2list !!!() RESULT(list)
!!! Converts the data stored in the dictionary into
!!! linked list. This kind of operation is needed if
!!! you want to iterate through the dictionary to find
!!! something whose key is unknown.
!!! Beaware that the list here has to be initialized
!!! before this function is called.
PROCEDURE :: dict2list_sort_key !!!() RESULT(list)
!!! Same as dict2list,except that the list is sorted by the
!!! value of data%val in ascending order.
PROCEDURE :: dict2list_sort_val !!!() RESULT(list)
!!! Same as dict2list,except that the list is sorted by the
!!! value of data%val in ascending order.

FINAL :: destroy !!!() destructor.
END TYPE dictionary_struct

CONTAINS

</source>

==Hash key generation algorithm==

<source lang="fortran">
! Calculate the hash key for hash table.
!
INTEGER FUNCTION hashkey( self,key )
IMPLICIT NONE
CLASS(dictionary_struct),INTENT(IN) :: self
INTEGER, INTENT(in) :: key

IF (.NOT.(ALLOCATED(self%table))) RETURN
hashkey = MOD( key, self%hash_size ) + 1

END FUNCTION hashkey
</source>

Dictionary data structure - 版の履歴

Hirano: ページの作成:「==Background== The struct that provides user access to dictionary data structure. This dictionary is actually an array of linked lists managed by a simple hash table.…」