A hash table implementation for the slope programming language
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
sloum 91f5bf5443 Adds namespace support 5 months ago
README.md Adds namespace support 5 months ago
main.slo Adds namespace support 5 months ago
module.json Adds namespace support 5 months ago

README.md

hash-table

As you may have guessed hash-table is a hash table implementation for the slope programming language. It largely consists of one procedure: make-hash-table, which returns a lambda that can handle all hash table operations that are supported: insert, search, delete, keys.

Example Usage

(load-mod "hash-table")

(define my-hash (hash-table::make-hash-table))

(my-hash 'insert "Key1" 1) ; => #t
(my-hash 'search "Key1")   ; => 1
(my-hash 'delete "Key1")   ; => #t
(my-hash 'search "Key1")   ; => 'NOKEY
(my-hash 'insert "Key2" 2) ; => #t
(my-hash 'insert "Key3" 3) ; => #t
(my-hash 'keys)            ; => ("Key3" "Key2")
(my-hash 'search "Key3")   ; => 3
(my-hash 'insert "Key3" 6) ; #t
(my-hash 'search "Key3")   ; => 6

Under the hood

The lambda that is returned by make-hash-table is a closure with access to a number of other lambdas as well as some data. This lets it act like an object. Since slope does not have pointers or reference passing, the table still gets fully re-written on insert and delete. This slows things down a bit compared to, say, C... but is fairly optimized by the underlying Go codebase that the slope interpreter is written in.

The hash table will expand as needed to allow for large tables. However, it will not shrink as items are deleted. As such, be aware of the memory footprint large hash tables that then get many keys removed may have. For most use cases this will not matter. When compared to using associative lists this hash table implementation should, especially on larger tables, be significantly faster retrieving information via 'search than an associative list lookup since an associative list just goes through every item looking for what it wants. Lookups should be O(1) in this hash table implementation. However, inserts are slower than associative lists since in an associative list a new value just gets added to the list and the hash table must find the location for a new hash value and deal with any collisions. Deletions are likely quicker in the hash table than with associative lists, but extensive testing has not been done.

Collisions are solved by open addressing with double hashing.

Requirements

slope version >= 0.8.0