Hash Table Ontology

AI SEARCH

FLOW ALGEBRA — HASH TABLE ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/data-structures/hash-table-ontology.html

FLOW HASH_TABLE_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Data Structures"
    ONTOLOGY = "Hash Table Ontology"
    PURPOSE = "Formalise hash tables, keys, values, hash functions, buckets, slots, collisions, probing, chaining, load factors, resizing, lookup, insertion, deletion, invariants and complexity."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    HASH_TABLE
    HASH_MAP
    HASH_SET
    OPEN_ADDRESSING_HASH_TABLE
    CHAINED_HASH_TABLE
    CUCKOO_HASH_TABLE
    ROBIN_HOOD_HASH_TABLE
    PERFECT_HASH_TABLE
    MUTABLE_HASH_TABLE
    IMMUTABLE_HASH_TABLE
    PERSISTENT_HASH_TABLE
    KEY
    VALUE
    KEY_VALUE_PAIR
    ENTRY
    HASH_FUNCTION
    HASH_VALUE
    HASH_CODE
    BUCKET
    SLOT
    BUCKET_INDEX
    TABLE_INDEX
    CAPACITY
    SIZE
    LOAD_FACTOR
    LOAD_FACTOR_THRESHOLD
    COLLISION
    COLLISION_RESOLUTION
    SEPARATE_CHAINING
    OPEN_ADDRESSING
    LINEAR_PROBING
    QUADRATIC_PROBING
    DOUBLE_HASHING
    PROBE_SEQUENCE
    TOMBSTONE
    EMPTY_SLOT
    OCCUPIED_SLOT
    DELETED_SLOT
    CHAIN
    NODE
    EQUALITY_FUNCTION
    KEY_COMPARISON
    OPERATION
    CREATE
    INSERT
    PUT
    UPDATE
    LOOKUP
    GET
    SEARCH
    CONTAINS
    DELETE
    REMOVE
    RESIZE
    REHASH
    CLEAR
    ITERATE
    TRAVERSE
    ALLOCATION
    DEALLOCATION
    INVARIANT
    KEY_UNIQUENESS_INVARIANT
    BUCKET_MAPPING_INVARIANT
    PROBE_INVARIANT
    LOAD_FACTOR_INVARIANT
    TABLE_STATE
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    BEST_CASE
    AVERAGE_CASE
    WORST_CASE
    MEMORY
    IMPLEMENTATION
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION
    ERROR
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    IMPLEMENTS
    PART_OF
    CONTAINS
    HAS_KEY
    HAS_VALUE
    HAS_ENTRY
    HAS_HASH_FUNCTION
    HASHES_TO
    MAPS_TO
    STORED_IN
    HAS_BUCKET
    HAS_SLOT
    HAS_INDEX
    HAS_CAPACITY
    HAS_SIZE
    HAS_LOAD_FACTOR
    HAS_THRESHOLD
    COLLIDES_WITH
    RESOLVES_COLLISION_BY
    CHAINS_WITH
    PROBES
    COMPARES
    INSERTS
    PUTS
    UPDATES
    LOOKS_UP
    GETS
    SEARCHES
    CONTAINS_KEY
    DELETES
    REMOVES
    RESIZES
    REHASHES
    CLEARS
    ITERATES
    ALLOCATES
    DEALLOCATES
    HAS_STATE
    TRANSITIONS_TO
    HAS_INVARIANT
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    HAS_IMPLEMENTATION
    HAS_CONFIGURATION
    DEPENDS_ON
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    HASH_TABLE_SPECIFICATIONS
    HASH_TABLE_IMPLEMENTATIONS
    SOURCE_CODE
    KEY_AND_VALUE_DATA
    HASH_FUNCTION_DEFINITIONS
    HASH_VALUES
    BUCKET_AND_SLOT_DATA
    CAPACITY_AND_SIZE_DATA
    LOAD_FACTOR_DATA
    COLLISION_TRACES
    PROBE_TRACES
    CHAIN_DATA
    INSERTION_TRACES
    LOOKUP_TRACES
    DELETION_TRACES
    RESIZE_AND_REHASH_TRACES
    INVARIANT_DEFINITIONS
    COMPLEXITY_ANALYSES
    MEMORY_DATA
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_HASH_TABLE_IDENTIFIERS
    NORMALISE_HASH_TABLE_TYPES
    NORMALISE_KEY_AND_VALUE_TYPES
    NORMALISE_HASH_FUNCTION_IDENTIFIERS
    NORMALISE_HASH_VALUES
    NORMALISE_BUCKET_AND_SLOT_IDENTIFIERS
    NORMALISE_TABLE_INDICES
    NORMALISE_SIZE_CAPACITY_AND_LOAD_FACTOR
    NORMALISE_COLLISION_STRATEGY_NAMES
    NORMALISE_PROBING_STRATEGIES
    NORMALISE_OPERATION_NAMES
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_LANGUAGE_AND_RUNTIME_CONTEXT
    RESOLVE_TABLE_ENTRY_AND_KEY_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS HASH_TABLE_REASONING_PIPELINE {
    HASH_TABLE_REFERENCE
      -> TABLE_IDENTIFICATION
      -> TABLE_TYPE_RESOLUTION
      -> HASH_FUNCTION_RESOLUTION
      -> KEY_VALUE_AND_ENTRY_MAPPING
      -> BUCKET_OR_SLOT_MAPPING
      -> COLLISION_STRATEGY_MAPPING
      -> OPERATION_MAPPING
      -> INVARIANT_ANALYSIS
      -> COMPLEXITY_ANALYSIS
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS HASH_MAPPING_REASONING {
    KEY
      -> HASH_FUNCTION

    HASH_FUNCTION(KEY)
      -> HASH_VALUE

    HASH_VALUE + TABLE_CAPACITY
      -> INITIAL_BUCKET_OR_SLOT_INDEX

    INITIAL_INDEX
      -> TARGET_BUCKET_OR_PROBE_START
  }

  PROCESS CHAINING_REASONING {
    KEY
      -> BUCKET_INDEX

    BUCKET_INDEX
      -> CHAIN

    CHAIN
      -> ENTRY_SEQUENCE

    LOOKUP
      -> KEY_COMPARISON_WITH_CHAIN_ENTRIES

    INSERT_COLLISION
      -> ADD_ENTRY_TO_CHAIN

    DELETE
      -> REMOVE_MATCHING_ENTRY_FROM_CHAIN
  }

  PROCESS OPEN_ADDRESSING_REASONING {
    KEY
      -> INITIAL_SLOT

    INITIAL_SLOT
      -> SLOT_STATE

    OCCUPIED_BY_DIFFERENT_KEY
      -> PROBE_SEQUENCE

    PROBE_SEQUENCE
      -> NEXT_CANDIDATE_SLOT

    EMPTY_OR_MATCHING_SLOT
      -> INSERT_UPDATE_OR_LOOKUP_RESULT

    DELETE
      -> TOMBSTONE_OR_IMPLEMENTATION_SPECIFIC_REPAIR
  }

  PROCESS LOOKUP_REASONING {
    LOOKUP(KEY)
      -> HASH_MAPPING

    HASH_MAPPING
      -> COLLISION_STRATEGY

    COLLISION_STRATEGY
      -> CANDIDATE_ENTRIES

    CANDIDATE_ENTRY
      -> KEY_EQUALITY_CHECK

    MATCH
      -> RETURN_VALUE_OR_ENTRY

    SEARCH_EXHAUSTED
      -> NOT_FOUND
  }

  PROCESS INSERTION_REASONING {
    INSERT(KEY, VALUE)
      -> HASH_MAPPING

    CANDIDATE_LOCATION
      -> EXISTING_KEY_CHECK

    EXISTING_KEY
      -> UPDATE_VALUE_IF_MAP_SEMANTICS

    NEW_KEY
      -> COLLISION_RESOLUTION
      -> INSERT_ENTRY

    RESULT
      -> SIZE_UPDATE
      -> LOAD_FACTOR_RECOMPUTATION
      -> RESIZE_CHECK
  }

  PROCESS DELETION_REASONING {
    DELETE(KEY)
      -> LOOKUP_ENTRY

    ENTRY_FOUND
      -> REMOVE_ENTRY_OR_MARK_DELETED

    REMOVE_OR_MARK
      -> SIZE_DECREMENT

    OPEN_ADDRESSING
      -> PRESERVE_PROBE_CHAIN_REACHABILITY

    RESULT
      -> INVARIANT_CHECK
  }

  PROCESS RESIZE_REASONING {
    LOAD_FACTOR_OR_POLICY_TRIGGER
      -> NEW_CAPACITY

    NEW_CAPACITY
      -> ALLOCATE_NEW_TABLE

    EXISTING_ENTRIES
      -> RECOMPUTE_BUCKET_OR_SLOT_USING_NEW_CAPACITY

    REINSERT_OR_REHASH_ENTRIES
      -> NEW_TABLE_STATE

    NEW_TABLE_STATE
      -> REPLACE_OLD_TABLE
  }

  PROCESS LOAD_FACTOR_REASONING {
    SIZE + CAPACITY
      -> LOAD_FACTOR = SIZE / CAPACITY

    LOAD_FACTOR
      -> THRESHOLD_COMPARISON

    THRESHOLD_EXCEEDED
      -> RESIZE_OR_REHASH_POLICY

    LOAD_FACTOR
      -> COLLISION_AND_PERFORMANCE_CONTEXT
  }

  PROCESS INVARIANT_REASONING {
    TABLE_STATE
      -> KEY_UNIQUENESS_CHECK_IF_MAP_OR_SET_REQUIRES

    EACH_ENTRY
      -> HASH_AND_COLLISION_STRATEGY_REACHABILITY_CHECK

    OPEN_ADDRESSING_TABLE
      -> PROBE_INVARIANT

    TABLE_STATE
      -> SIZE_CAPACITY_AND_LOAD_FACTOR_CONSISTENCY

    POST_OPERATION_STATE
      -> ALL_REQUIRED_INVARIANTS_CHECK
  }

  PROCESS COMPLEXITY_REASONING {
    HASH_TABLE + OPERATION
      -> SIZE_CAPACITY_LOAD_FACTOR_AND_COLLISION_CONTEXT

    HASH_FUNCTION
      -> HASH_COST

    LOOKUP_INSERT_DELETE
      -> BUCKET_CHAIN_LENGTH_OR_PROBE_LENGTH

    RESIZE
      -> ENTRY_REHASH_COST

    OPERATION_COST
      -> BEST_AVERAGE_AND_WORST_CASE

    STORAGE
      -> SPACE_COMPLEXITY
  }

  PROCESS PERSISTENCE_REASONING {
    PERSISTENT_HASH_TABLE_STATE(T1)
      + UPDATE
      -> NEW_TABLE_STATE(T2)

    T1
      -> PRESERVED

    T1 + T2
      -> STRUCTURAL_SHARING_IF_IMPLEMENTED
  }

  RULES {
    IF KEY_IS_USED
    THEN PRESERVE HASH_FUNCTION_AND_KEY_EQUALITY_SEMANTICS

    IF TWO_KEYS_HAVE_SAME_HASH_VALUE
    THEN DO_NOT ASSERT KEYS_ARE_EQUAL

    IF KEYS_ARE_EQUAL_UNDER_TABLE_SEMANTICS
    THEN REQUIRE HASH_CONSISTENCY_WHERE_IMPLEMENTATION_CONTRACT_REQUIRES

    IF COLLISION_OCCURS
    THEN APPLY CONFIGURED_COLLISION_RESOLUTION_STRATEGY

    IF TABLE_CAPACITY_CHANGES
    THEN RECOMPUTE_BUCKET_OR_SLOT_MAPPING_AS_REQUIRED

    IF OPEN_ADDRESSING_DELETE_OCCURS
    THEN PRESERVE_LOOKUP_REACHABILITY_FOR_OTHER_KEYS

    IF LOAD_FACTOR_IS_REPORTED
    THEN PRESERVE SIZE_AND_CAPACITY_CONTEXT

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND HASH_TABLE_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        TABLE_IDENTITY_CERTAINTY,
        TABLE_TYPE_CERTAINTY,
        HASH_FUNCTION_CERTAINTY,
        KEY_EQUALITY_CERTAINTY,
        ENTRY_AND_BUCKET_COMPLETENESS,
        COLLISION_TRACE_COMPLETENESS,
        OPERATION_TRACE_COMPLETENESS,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF HASH_FUNCTION_OR_EQUALITY_SEMANTICS_IS_UNKNOWN
    THEN REDUCE_KEY_MAPPING_CONFIDENCE

    IF COLLISION_STRATEGY_IS_UNKNOWN
    THEN REDUCE_LOOKUP_AND_UPDATE_CONFIDENCE

    IF COMPLETE_TABLE_STATE_AND_OPERATION_TRACE_CONFIRM_INVARIANTS
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        HASH_TABLE_IDENTIFIER,
        TABLE_TYPE,
        KEY_TYPE,
        VALUE_TYPE,
        HASH_FUNCTION,
        EQUALITY_SEMANTICS,
        CONFIGURATION
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    HASH_TABLE != HASH_FUNCTION
    HASH_VALUE != KEY
    HASH_VALUE != UNIQUE_IDENTIFIER
    HASH_COLLISION != DUPLICATE_KEY
    BUCKET != ENTRY
    SLOT != VALUE
    HASH_MAP != HASH_SET
    OPEN_ADDRESSING != SEPARATE_CHAINING
    LINEAR_PROBING != QUADRATIC_PROBING
    TOMBSTONE != EMPTY_SLOT
    SIZE != CAPACITY
    LOAD_FACTOR != COLLISION_RATE
    AVERAGE_CASE_COMPLEXITY != WORST_CASE_COMPLEXITY
    CONSTANT_EXPECTED_LOOKUP != GUARANTEED_CONSTANT_WORST_CASE
    RESIZE != SIMPLE_MEMORY_EXTENSION_IN_ALL_IMPLEMENTATIONS
    KEY_EQUALITY_AND_HASH_SEMANTICS_MUST_BE_CONSISTENT_WITH_IMPLEMENTATION_CONTRACT
    PERFORMANCE_DEPENDS_ON_HASH_QUALITY_LOAD_FACTOR_COLLISION_STRATEGY_AND_INPUT_DISTRIBUTION
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_HASH_TABLE_IDENTIFIER
    CHECK_TABLE_TYPE
    CHECK_KEY_AND_VALUE_TYPES
    CHECK_HASH_FUNCTION
    CHECK_KEY_EQUALITY_SEMANTICS
    CHECK_ENTRIES
    CHECK_BUCKET_OR_SLOT_MAPPING
    CHECK_COLLISION_STRATEGY
    CHECK_PROBE_SEQUENCE_IF_APPLICABLE
    CHECK_CHAIN_RELATIONS_IF_APPLICABLE
    CHECK_SIZE_AND_CAPACITY
    CHECK_LOAD_FACTOR
    CHECK_INSERTION
    CHECK_LOOKUP
    CHECK_DELETION
    CHECK_RESIZE_AND_REHASH
    CHECK_INVARIANTS
    CHECK_COMPLEXITY_CONTEXT
    CHECK_PERSISTENCE
    CHECK_LANGUAGE_RUNTIME_AND_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_HASH_TABLE_ENTITIES
    TABLE_TYPE_RELATIONS
    KEY_VALUE_AND_ENTRY_RELATIONS
    HASH_FUNCTION_RELATIONS
    HASH_VALUE_RELATIONS
    BUCKET_AND_SLOT_RELATIONS
    COLLISION_RELATIONS
    CHAINING_RELATIONS
    PROBING_RELATIONS
    LOOKUP_RELATIONS
    INSERTION_AND_UPDATE_RELATIONS
    DELETION_RELATIONS
    RESIZE_AND_REHASH_RELATIONS
    LOAD_FACTOR_RELATIONS
    HASH_TABLE_STATE_TRANSITIONS
    INVARIANT_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    PERSISTENCE_AND_STRUCTURAL_SHARING_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON HASH_TABLE_OPERATION {
      NORMALISE
      RESOLVE_TABLE_ENTRY_AND_KEY_IDENTITIES
      UPDATE_ENTRY_SET
      UPDATE_BUCKET_OR_SLOT_STATE
      UPDATE_SIZE_AND_LOAD_FACTOR
      APPLY_RESIZE_OR_REHASH_IF_REQUIRED
      RECHECK_INVARIANTS
      UPDATE_CONFIDENCE
    }

    ON HASH_FUNCTION_COLLISION_POLICY_OR_CONFIGURATION_CHANGE {
      UPDATE_IMPLEMENTATION_CONTEXT
      RECOMPUTE_ENTRY_MAPPING
      REASSESS_COMPLEXITY
      RECHECK_SEMANTIC_EQUIVALENCE
      RECOMPUTE_AFFECTED_RELATIONS
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON ONTOLOGY_REVISION {
      REMAP_TERMS
      CHECK_SEMANTIC_EQUIVALENCE
      IDENTIFY_DEPRECATED_TERMS
      MIGRATE_RELATIONSHIPS
      PRESERVE_PRIOR_VERSION_REFERENCES
    }
  }

  FLOW_HASH {
    HASH_INPUT =
      CANONICALISE(
        ENTITY_TYPES,
        RELATIONSHIPS,
        RULES,
        CONFIDENCE,
        SEMANTIC_EQUIVALENCE,
        REASONING_CONSTRAINTS,
        UPDATE_MODEL
      )

    FLOW_HASH = SHA256(HASH_INPUT)
  }

  AI_CONSUMPTION {
    INDEX {
      ONTOLOGY
      ENTITY_TYPES
      RELATIONSHIPS
      RULES
      OUTPUTS
    }

    RETRIEVE {
      BY_HASH_TABLE
      BY_TABLE_TYPE
      BY_KEY
      BY_VALUE
      BY_ENTRY
      BY_HASH_FUNCTION
      BY_BUCKET
      BY_SLOT
      BY_COLLISION
      BY_PROBE
      BY_LOAD_FACTOR
      BY_OPERATION
      BY_COMPLEXITY
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_HASH_MAPPING
      ANALYSE_SEPARATE_CHAINING
      ANALYSE_OPEN_ADDRESSING
      TRACE_LOOKUPS
      TRACE_INSERTIONS
      TRACE_DELETIONS
      ANALYSE_RESIZE_AND_REHASH
      ANALYSE_LOAD_FACTOR
      CHECK_HASH_TABLE_INVARIANTS
      ANALYSE_COMPLEXITY
      ANALYSE_PERSISTENCE
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_HASH_TABLE_FROM_HASH_FUNCTION
      DISTINGUISH_HASH_COLLISION_FROM_DUPLICATE_KEY
      DISTINGUISH_OPEN_ADDRESSING_FROM_SEPARATE_CHAINING
      PRESERVE_KEY_EQUALITY_HASH_FUNCTION_LOAD_FACTOR_COLLISION_POLICY_IMPLEMENTATION_AND_RUNTIME_CONTEXT
      DISTINGUISH_EXPECTED_FROM_WORST_CASE_COMPLEXITY
      PRESERVE_HASH_TABLE_INVARIANTS_AND_VERSIONED_STATES
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_HASH_TABLE_INFERENCE
    }
  }

  TERMINAL {
    RESULT =
      VALIDATED(
        SEMANTICALLY_NORMALISED(
          EVIDENCE_LINKED(
            CONFIDENCE_AWARE(
              HASH_TABLE_KNOWLEDGE
            )
          )
        )
      )
  }
}

END FLOW