||5 months ago|
|README.md||5 months ago|
|main.slo||5 months ago|
|module.json||5 months ago|
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:
(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.
slope version >= 0.8.0